News for hackers. Stuff that matters.
Re:Chemical space is really big (2014) by actually_a_dog on Friday June 25, 2021 @08:35PM (#27637927)
> Then there's the problem of figuring out if you've already enumerated a molecule. That problem has no known polynomial-time solution (graph isomorphism), although GDB's low node count mitigates the problem.

It's not just the low vertex count that makes this an easier problem than general GI. The state of the art GI algorithm for general graphs runs in quasipolynomial time 2^{O((log n)^c)}, with c=3 claimed. [0]

However, structural constraints implied by chemical plausibility should (probably[1]) usefully limit the class of graphs that need be considered to those of bounded treewidth. A polynomial time GI algorithm was recently published for graphs of bounded treewidth. [2]

[0]: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Stat...

[1]: If nothing else, maximum degree restrictions imposed by chemical valence should impose a useful upper bound on treewidth. Although I (somewhat surprisingly) can't find a paper offhand stating such an explicit bound for treewidth in terms of maximum degree, I did find one stating an asymptotic bound of (1 - C * exp (-4.06√d)|V| for sufficiently large max degree d, and some constant C, which lends some plausibility to this line of thought: https://journals.plos.org/plosone/article?id=10.1371/journal...

[2]: https://arxiv.org/abs/1803.06858

There are no comments on this comment yet.