In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both G and H, and that has as many vertices as possible.
Finding this graph is NP-hard. In the associated decision problem, the input is two graphs G and H and a number k. The problem is to decide whether G and H have a common induced subgraph with at least k vertices. This problem is NP-complete.[1] It is a generalization of the induced subgraph isomorphism problem, which arises when k equals the number of vertices in the smaller of G and H, so that this entire graph must appear as an induced subgraph of the other graph.
Based on hardness of approximation results for the maximum independent set problem, the maximum common induced subgraph problem is also hard to approximate.[2] This implies that, unless P = NP, there is no approximation algorithm that, in polynomial time on -vertex graphs, always finds a solution within a factor of of optimal, for any .[3]
One possible solution for this problem is to build a modular product graph of G and H. In this graph, the largest clique corresponds to a maximum common induced subgraph of G and H. Therefore, algorithms for finding maximum cliques can be used to find the maximum common induced subgraph.[4] Moreover, a modified maximum-clique algorithm can be used to find a maximum common connected subgraph.[5]
The McSplit algorithm (along with its McSplit↓ variant) is a forward checking algorithm that does not use the clique encoding, but uses a compact data structure to keep track of the vertices in graph H to which each vertex in graph G may be mapped. Both versions of the McSplit algorithm outperform the clique encoding for many graph classes.[6] A more efficient implementation of McSplit is McSplitDAL+PR, which combines a Reinforcement Learning agent with some heuristic scores computed with the PageRank algorithm.[7]
Maximum common induced subgraph algorithms have a long tradition in cheminformatics and pharmacophore mapping.[8]
See also edit
References edit
- ^ Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.4: GT48, pg.202.
- ^ Kann, Viggo (1992), "On the approximability of the maximum common subgraph problem", STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992, Proceedings, Lecture Notes in Computer Science, vol. 577, Springer Science $\mathplus$ Business Media, pp. 375–388, doi:10.1007/3-540-55210-3_198, ISBN 978-3-540-55210-9.
- ^ Zuckerman, D. (2006), "Linear degree extractors and the inapproximability of max clique and chromatic number", Proc. 38th ACM Symp. Theory of Computing, pp. 681–690, doi:10.1145/1132516.1132612, ISBN 1-59593-134-1, S2CID 5713815, ECCC TR05-100.
- ^ Barrow, H.; Burstall, R. (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Information Processing Letters, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1.
- ^ McCreesh, Ciaran; Ndiaye, Samba Ndojh; Prosser, Patrick; Solnon, Christine (2016), "Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems" (PDF), Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings, Lecture Notes in Computer Science, vol. 9892, Springer International Publishing, pp. 350–368, doi:10.1007/978-3-319-44953-1_23, ISBN 978-3-319-44952-4, S2CID 215812381
- ^ McCreesh, Ciaran; Prosser, Patrick; Trimble, James (2017), "A Partitioning Algorithm for Maximum Common Subgraph Problems", Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, {IJCAI} 2017, Melbourne, Australia, August 19-25, 2017, ijcai.org, pp. 712–719, doi:10.24963/ijcai.2017/99, ISBN 9780999241103
- ^ Calabrese, Andrea; Cardone, Lorenzo; Licata, Salvatore; Porro, Marco; Quer, Stefano (2023). A Web Scraping Algorithm to Improve the Computation of the Maximum Common Subgraph. SCITEPRESS - Science and Technology Publications. pp. 197–206. doi:10.5220/0012130800003538. ISBN 978-989-758-665-1.
- ^ Raymond, John W.; Willett, Peter (2002), "Maximum common subgraph isomorphism algorithms for the matching of chemical structures" (PDF), Journal of Computer-Aided Molecular Design, 16 (7): 521–533, Bibcode:2002JCAMD..16..521R, doi:10.1023/A:1021271615909, PMID 12510884, S2CID 5202419.