2

There's a well-known article for solving graph isomorphism problem in polynomial time. Many other articles on the subject of isomorphism mention it as a possible "alternative", but note that is not applicable in general case and move on presenting their approach.

However, I'm interested in solving subgraph isomorphism in the context of chemical structures. Majority of graphs in this domain are, in fact, of bounded degree. This is a result of chemical properties, where bonds (edges) are result of valence electron pairings. Because there's only limited number of electrons on valence shelve, so is the number of edges limited. I doubt there are chemical structures where atom has more than 7 bonds. Even if such exotic example would arise, it would be easy to identify and use more general algorithm for it.

The problem is I didn't find any practical implementation of the polynomial-time algorithm or any follow up work that would consider the idea from more practical perspective. The established algorithm for subgraph isomorphism in chemoinformatics seems to be VF2. There were some other related questions asking for a more digestible explanation, but I'm specifically looking for implementation and why can't I find any. Is the approach somewhat obsolete, forgotten, too hard to explore, or is there other issue why not use it?

Raven
  • 137
  • 1
  • 3
    The bounded degree graph isomorphism algorithm does not, in general, given an efficient algorithm for bounded-degree subgraph iso. Also, even for graph iso, Luks' algorithm seems to be very impractical compared to existing general software for graph iso. – Joshua Grochow Jan 31 '18 at 16:33
  • Do your subgraphs have a bounded number of vertices? – Samuel Schlesinger Jan 31 '18 at 17:06
  • Or bounded treewidth? – holf Jan 31 '18 at 17:15
  • @SamuelSchlesinger In general no, but there could be a threshold (say 100). There is a screening step before the subgraph algorithm which can tell, whether there's possibility of finding subgraph. The screening is more successful with increasing subgraph size. So smaller subgraphs will comprise most of the algorithm invocations. – Raven Jan 31 '18 at 20:15
  • @holf I'm not sure, they are not trees in general, but molecules tend to form chain structures instead of large clumps. The problem is that they contain cycles. – Raven Jan 31 '18 at 20:16
  • 1
    That does not help very much, it gives you an $O(n^{100})$ time algorithm but that is sadness. On the other hand, @holf seems to have the right idea: this blog post discusses the empirical treewidth of molecules and it seems you can think of it as being essentially bounded. https://nanoexplanations.wordpress.com/2011/02/28/treewidth-of-molecular-graphs/ – Samuel Schlesinger Jan 31 '18 at 20:31
  • @SamuelSchlesinger Thanks for the finding. Anyway, how is this property interesting? – Raven Jan 31 '18 at 23:24
  • Also to note that E M luks algorithm for bounded degree graph uses group theory (Algebra) which will be very to implement. – new Feb 02 '18 at 15:01
  • Many NP-complete problems on graphs with bounded tree width can be solved in polynomial time: https://arxiv.org/abs/cs/9911003; – Samuel Schlesinger Feb 02 '18 at 23:56
  • @SamuelSchlesinger Just to clarify: you mean that many NP-complete problems on graphs with bounded tree width can be solved in polynomial time with fixed input parameters, correct? – delete000 Feb 03 '18 at 18:38

0 Answers0