Incidentally, I came across this O(log N) canonization algorithm for planar graphs: https://arxiv.org/pdf/0809.2319.pdf
I wonder if this algorithm can be adapted for chemistry? Molecules are usually planar, but I believe they occasionally are "nearly" planar, by which I mean planar graphs plus a few edges that break the planarity. And what (generally speaking) is the algorithm used by rdkit? Do we know it's complexity? On Thu, Jun 15, 2023 at 1:38 PM S Joshua Swamidass <swamid...@gmail.com> wrote: > 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
