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

[Peter S. S. <sh...@gm...>]

Well, if I'm recalling correctly, a highly symmetric structure like
buckminsterfullerene takes a long time to canonicalize.

I don't know what the formal definition of a planar graph is, but I would
guess it's not what chemists mean when they say a molecule is planar.

-P.

On Thu, Jun 15, 2023 at 2:51 PM S Joshua Swamidass <swa...@gm...>
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.
>
> 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 <swa...@gm...>
> 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...@da...>
>> wrote:
>>
>>> 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...
>>>
>>>
>>> _______________________________________________
> Rdkit-discuss mailing list
> Rdk...@li...
> https://lists.sourceforge.net/lists/listinfo/rdkit-discuss
>