<p>There's a <a href="https://ac.els-cdn.com/0022000082900095/1-s2.0-0022000082900095-main.pdf?_tid=825d75dc-0697-11e8-a3bb-00000aab0f27&amp;acdnat=1517411023_fa02e0953bc4198a7ee3c9b7efeea6f6" rel="nofollow noreferrer">well-known article</a> 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. </p>

<p>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.</p>

<p>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 <a href="https://pdfs.semanticscholar.org/f3e1/0bd7521ec6263a58fdaa4369dfe8ad50888c.pdf" rel="nofollow noreferrer">VF2</a>. There were some other related <a href="https://cstheory.stackexchange.com/q/12369">questions</a> 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?</p>

CC BY-SA 3.0
2018-01-31T16:33:06.270Z
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
CC BY-SA 3.0
2018-01-31T17:06:46.090Z
Do your subgraphs have a bounded number of vertices?
Samuel Schlesinger
CC BY-SA 3.0
2018-01-31T17:15:50.503Z
Or bounded treewidth?
holf
CC BY-SA 3.0
2018-01-31T20:15:47.743Z
@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
CC BY-SA 3.0
2018-01-31T20:16:12.243Z
@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
CC BY-SA 3.0
2018-01-31T20:31:02.827Z
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
CC BY-SA 3.0
2018-01-31T23:24:26.767Z
@SamuelSchlesinger Thanks for the finding. Anyway, how is this property interesting?
Raven
CC BY-SA 3.0
2018-02-02T15:01:03.073Z
Also to note that E M luks algorithm for bounded degree graph uses group theory (Algebra) which will be very to implement.
new
CC BY-SA 3.0
2018-02-02T23:56:19.763Z
Many NP-complete problems on graphs with bounded tree width can be solved in polynomial time: https://arxiv.org/abs/cs/9911003;
Samuel Schlesinger
CC BY-SA 3.0
2018-02-03T18:38:48.227Z
@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
<reference-request><graph-theory><graph-isomorphism><implementation>
Practical polynomial-time implementation of bounded degree graph isomorphishm
Raven
# Practical polynomial-time implementation of bounded degree graph isomorphishm

(Asked by: username_0 on 2018-01-31)

There's a [well-known article](https://ac.els-cdn.com/0022000082900095/1-s2.0-0022000082900095-main.pdf?_tid=825d75dc-0697-11e8-a3bb-00000aab0f27&acdnat=1517411023_fa02e0953bc4198a7ee3c9b7efeea6f6) 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](https://pdfs.semanticscholar.org/f3e1/0bd7521ec6263a58fdaa4369dfe8ad50888c.pdf). There were some other related [questions](https://cstheory.stackexchange.com/q/12369) 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?

**Tags:** reference-request, graph-theory, graph-isomorphism, implementation

> **Comments:**
> **username_1**: 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.  
> **username_2**: Do your subgraphs have a bounded number of vertices?  
> **username_3**: Or bounded treewidth?  
> **username_0**: @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.  
> **username_0**: @username_3 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.  
> **username_2**: That does not help very much, it gives you an $O(n^{100})$ time algorithm but that is sadness. On the other hand, @username_3 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/  
> **username_0**: @SamuelSchlesinger Thanks for the finding. Anyway, how is this property interesting?  
> **username_4**: Also to note that E M luks algorithm for bounded degree graph uses group theory (Algebra) which will be very to implement.  
> **username_2**: Many NP-complete problems on graphs with bounded tree width can be solved in polynomial time: https://arxiv.org/abs/cs/9911003;  
> **username_5**: @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?  

---

## 0 answers

