View source for Maximum common induced subgraph

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]].<ref>{{citation|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} A1.4: GT48, pg.202.</ref> 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.<ref>{{citation
 | last = Kann | first = Viggo
 | contribution = On the approximability of the maximum common subgraph problem
 | doi = 10.1007/3-540-55210-3_198
 | pages = 375–388
 | publisher = Springer Science $\mathplus$ Business Media
 | series = Lecture Notes in Computer Science
 | title = STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992, Proceedings
 | volume = 577
 | isbn = 978-3-540-55210-9
 | year = 1992}}.</ref> This implies that, unless [[P = NP]], there is no [[approximation algorithm]] that, in [[polynomial time]] on <math>n</math>-vertex graphs, always finds a solution within a factor of <math>n^{1-\epsilon}</math> of optimal, for any <math>\epsilon > 0</math>.<ref>{{citation |first=D. |last=Zuckerman |title=[[Symposium on Theory of Computing|Proc. 38th ACM Symp. Theory of Computing]] |pages=681–690 |year=2006 |doi=10.1145/1132516.1132612 |id={{ECCC|2005|05|100}}|chapter=Linear degree extractors and the inapproximability of max clique and chromatic number |isbn=1-59593-134-1|s2cid=5713815 }}.</ref>

One possible solution for this problem is to build a [[Modular product of graphs|modular product graph]] of ''G'' and ''H''.
In this graph, the largest [[Clique (graph theory)|clique]] corresponds to a maximum common induced subgraph of ''G'' and ''H''. Therefore, [[clique problem|algorithms for finding maximum cliques]] can be used to find the maximum common induced subgraph.<ref>{{citation
 | last1 = Barrow | first1 = H.
 | last2 = Burstall | first2 = R. | author2-link = Rod Burstall
 | doi = 10.1016/0020-0190(76)90049-1
 | issue = 4
 | journal = Information Processing Letters
 | pages = 83–84
 | title = Subgraph isomorphism, matching relational structures and maximal cliques
 | volume = 4
 | year = 1976}}.</ref> Moreover, a modified maximum-clique algorithm can be used to find a maximum common ''connected'' subgraph.<ref>{{citation 
  | last1=McCreesh | first1=Ciaran
  | last2=Ndiaye | first2=Samba Ndojh
  | last3=Prosser | first3=Patrick 
  | last4=Solnon | first4=Christine
  | title=Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings
  | chapter=Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems
  | series=Lecture Notes in Computer Science
 | publisher=Springer International Publishing
  | year=2016
  | volume=9892
 | pages=350–368
  | doi=10.1007/978-3-319-44953-1_23| isbn=978-3-319-44952-4
 | s2cid=215812381
 | chapter-url=http://eprints.gla.ac.uk/120631/7/120631.pdf
 }}</ref>

The McSplit algorithm (along with its McSplit↓ variant) is a [[Look-ahead_(backtracking)|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.<ref>{{citation
  | last1=McCreesh | first1=Ciaran
  | last2=Prosser | first2=Patrick
  | last3=Trimble | first3=James
  | title=Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, {IJCAI} 2017, Melbourne, Australia, August 19-25, 2017
  | chapter=A Partitioning Algorithm for Maximum Common Subgraph Problems
  | publisher=ijcai.org
  | year=2017
  | pages=712–719
  | doi=10.24963/ijcai.2017/99| isbn=9780999241103
 | doi-access=free
  }}</ref> A more efficient implementation of McSplit is McSplitDAL+PR, which combines a [[Reinforcement learning|Reinforcement Learning]] agent with some heuristic scores computed with the [[PageRank]] algorithm.<ref>{{Cite book |last1=Calabrese |first1=Andrea |last2=Cardone |first2=Lorenzo |last3=Licata |first3=Salvatore |last4=Porro |first4=Marco |last5=Quer |first5=Stefano |date=2023 |title=A Web Scraping Algorithm to Improve the Computation of the Maximum Common Subgraph |publisher=SCITEPRESS - Science and Technology Publications |pages=197–206 |doi=10.5220/0012130800003538 |isbn=978-989-758-665-1|doi-access=free }}</ref>

== Applications ==
Maximum common induced subgraph algorithms form the basis for both graph differencing and graph alignment. Graph differencing identifies and highlights differences between two graphs by pinpointing changes, additions, or deletions. Graph alignment involves finding correspondences between the vertices and edges of two graphs to identify similar structures.

Maximum common induced subgraph algorithms have a long tradition in [[bioinformatics]], [[cheminformatics]],<ref>{{Cite journal |last1=Schietgat |first1=Leander |last2=Ramon |first2=Jan |last3=Bruynooghe |first3=Maurice |date=2013-12-01 |title=A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics |url=https://doi.org/10.1007/s10472-013-9335-0 |journal=Annals of Mathematics and Artificial Intelligence |language=en |volume=69 |issue=4 |pages=343–376 |doi=10.1007/s10472-013-9335-0 |issn=1573-7470}}</ref><ref>{{Cite journal |last1=Ehrlich |first1=Hans-Christian |last2=Rarey |first2=Matthias |date=2011 |title=Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review |url=https://wires.onlinelibrary.wiley.com/doi/10.1002/wcms.5 |journal=WIREs Computational Molecular Science |language=en |volume=1 |issue=1 |pages=68–79 |doi=10.1002/wcms.5 |issn=1759-0876}}</ref> [[Pharmacophore|pharmacophore mapping]],<ref>{{citation |last1=Raymond |first1=John W. |title=Maximum common subgraph isomorphism algorithms for the matching of chemical structures |journal=Journal of Computer-Aided Molecular Design |volume=16 |issue=7 |pages=521–533 |year=2002 |url=http://eprints.whiterose.ac.uk/3569/1/willetts4.pdf |bibcode=2002JCAMD..16..521R |doi=10.1023/A:1021271615909 |pmid=12510884 |s2cid=5202419 |last2=Willett |first2=Peter}}.</ref> [[pattern recognition]],<ref>{{Cite journal |last1=Conte |first1=D. |last2=Foggia |first2=P. |last3=Sansone |first3=C. |last4=Vento |first4=M. |date=2004 |title=Thirty Years of Graph Matching in Pattern Recognition |url=https://www.worldscientific.com/doi/abs/10.1142/S0218001404003228 |journal=International Journal of Pattern Recognition and Artificial Intelligence |language=en |volume=18 |issue=3 |pages=265–298 |doi=10.1142/S0218001404003228 |issn=0218-0014}}</ref> [[computer vision]], code analysis, compilers, and [[model checking]]. 

The problem is also particularly useful in software engineering and [[model-based systems engineering]], where software code and engineering models (e.g., [[Simulink]], [[Unified Modeling Language|UML diagrams]]) are represented as graph data structures. Graph differencing can be used to detect changes between different versions of software code and models for change auditing, debugging, version control and collaborative team development.

==See also==
*[[Molecule mining]]
*[[Maximum common edge subgraph]]

==References==
{{reflist}}

[[Category:NP-complete problems]]
[[Category:Cheminformatics]]
[[Category:Computational problems in graph theory]]