Is there an article stating that MCS is solvable in polynomial-time for planar molecular graphs? The subgraph isomorphism problem is NP-complete even for connected planar graphs of bounded-degree. Hence, planarity (also combined with the bounded-degree property of molecular graphs) seems not be sufficient to attain a polynomial-time MCS algorithm (unless P=NP).
Hi nlskrg,Researching now, I see that the MCS is polynomial for outerplanar graphs, and for trees, but it is NP for planar graphs. One paper says "The maximum common subgraph problem is NP-hard even for planar graphs of bounded degree 3 (Garey and Johnson, 1979) "Thanks for the correction!
Post a Comment