Andrew, Thanks! According to wikipedia (and my recollections of algorithms class)... "The problem is not known to be solvable in polynomial time <https://en.wikipedia.org/wiki/Polynomial_time> nor to be NP-complete <https://en.wikipedia.org/wiki/NP-complete>, and therefore may be in the computational complexity class <https://en.wikipedia.org/wiki/Complexity_class> NP-intermediate <https://en.wikipedia.org/wiki/NP-intermediate>." https://en.wikipedia.org/wiki/Graph_isomorphism_problem
Your reference though is really helpful. The key phrase seems to be "bounded valence" which is certainly true of molecular graphs. Each atom can only bound some fairly low number of other atoms, i.e. bounded valence. That's probably the reason why we do have a polynomial time algorithm... Thank you! Joshua On Thu, Jun 15, 2023 at 1:21 PM Andrew Dalke <da...@dalkescientific.com> wrote: > On Jun 15, 2023, at 18:20, S Joshua Swamidass <swamid...@gmail.com> wrote: > > It's well known that the graph-isomorphism problem is NP > > While P is contained in NP, I don't think that's the NP you mean. > > I suspect you may be thinking of subgraph isomorphism, which is NP-hard. > Graph isomorphism may be quasi-polynomial time, if Babai's (unpublished) > claim is correct. > > Also, "Isomorphism of graphs of bounded valence can be tested in > polynomial time" - > https://www.sciencedirect.com/science/article/pii/0022000082900095 . > > > > So here is my question. What are the cases that are very difficult to > canonize a graph? > > As I recall, handling chirality and other non-local properties is > difficult. I have not worked on this problem. > > Cheers, > > Andrew > da...@dalkescientific.com > > >
_______________________________________________ Rdkit-discuss mailing list Rdkit-discuss@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/rdkit-discuss
