Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Not if the number of nodes is high, no. The complexity of the naif algorithm grows exponentially, making it unmanageable very fast.

In order to show that one node in the first graph correspond to a particular node (i.e. is isomorphic) in the second graph, its not enough to check that they have the same number of outgoing edges. You have then to check all the connected nodes, and then make sure that those are also isomorphic to the respective same nodes in the same roles at the other graph.

This makes the problem recursive and dependent on the rest of the graph; you can't simply split the graph and solve each sub-problem fast.



Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: