Re: [Rdkit-discuss] question on complexity of cannonization

[Andrew D. <da...@da...>]

On Jun 15, 2023, at 18:20, S Joshua Swamidass <swa...@gm...> 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...@da...