On Jun 15, 2023, at 18:20, S Joshua Swamidass <[email protected]> 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 [email protected] _______________________________________________ Rdkit-discuss mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/rdkit-discuss
