On 16/06/2023 03:49, S Joshua Swamidass wrote:
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.
Dear Joshua,
Some natural product are notoriously complex 3D molecules.
What do you exactly mean by planar?
Many chemical groups are 3D: methyl, adamantane, etc.
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 [1] nor
to be NP-complete [2], and therefore may be in the computational
complexity class [3] NP-intermediate [4]."
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
Links:
------
[1] https://en.wikipedia.org/wiki/Polynomial_time
[2] https://en.wikipedia.org/wiki/NP-complete
[3] https://en.wikipedia.org/wiki/Complexity_class
[4] https://en.wikipedia.org/wiki/NP-intermediate
_______________________________________________
Rdkit-discuss mailing list
Rdkit-discuss@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/rdkit-discuss
_______________________________________________
Rdkit-discuss mailing list
Rdkit-discuss@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/rdkit-discuss
