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

[Francois B. <ml...@li...>]

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
> <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 [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...@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...
> 
> 
> 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
> Rdk...@li...
> https://lists.sourceforge.net/lists/listinfo/rdkit-discuss