Editing Subgraph isomorphism problem

{{Short description|Problem in theoretical computer science}}
[[File:Subgraph isomorphism.svg|thumb|160px|Graph <math>G</math> with a subgraph isomorphic to <math>H</math>]]
In [[theoretical computer science]], the '''subgraph isomorphism problem''' is a computational task in which two [[undirected graph|graphs]] <math>G</math> and <math>H</math> are given as input, and one must determine whether <math>G</math> contains a [[Glossary of graph theory#subgraph|subgraph]] that is [[graph isomorphism|isomorphic]] to <math>H</math>.
Subgraph isomorphism is a generalization of both the [[clique problem|maximum clique problem]] and the problem of testing whether a graph contains a [[Hamiltonian cycle]], and is therefore [[NP-complete]].<ref>The original {{harvtxt|Cook|1971}} paper that proves the [[Cook–Levin theorem]] already showed subgraph isomorphism to be NP-complete, using a reduction from [[3-SAT]] involving cliques.</ref> However certain other cases of subgraph isomorphism may be solved in polynomial time.<ref name="e99"/>

Sometimes the name '''subgraph matching''' is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem.

==Decision problem and computational complexity==
{{broader|Computational complexity}}
To prove subgraph isomorphism is NP-complete, it must be formulated as a [[decision problem]].  The input to the decision problem is a pair of graphs <math>G</math> and ''H''. The answer to the problem is positive if ''H'' is isomorphic to a subgraph of ''G'', and negative otherwise.

Formal question:

Let <math>G=(V,E)</math>, <math>H=(V^\prime,E^\prime)</math> be graphs. Is there a subgraph <math>G_0=(V_0,E_0) \mid V_0\subseteq V, E_0\subseteq E\cap(V_0\times V_0)</math> such that <math>G_0\cong H</math>? I. e., does there exist a [[bijection]] <math>f\colon V_0\rightarrow V^\prime</math> such that <math>\{\,v_1,v_2\,\} \in E_0 \iff \{\,f(v_1), f(v_2)\,\} \in E^\prime</math>?

The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the [[clique problem]], an NP-complete decision problem in which the input is a single graph ''G'' and a number ''k'', and the question is whether ''G'' contains a [[complete graph|complete subgraph]] with ''k'' vertices. To translate this to a subgraph isomorphism problem, simply let ''H'' be the complete graph ''K''<sub>''k''</sub>; then the answer to the subgraph isomorphism problem for ''G'' and ''H'' is equal to the answer to the clique problem for ''G'' and ''k''. Since the clique problem is NP-complete, this [[polynomial-time many-one reduction]] shows that subgraph isomorphism is also NP-complete.<ref>{{citation|title=Complexity Theory: Exploring the Limits of Efficient Algorithms|first=Ingo|last=Wegener|publisher=Springer|year=2005|isbn=9783540210450|page=81|url=https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA81}}.</ref>

An alternative reduction from the [[Hamiltonian path problem|Hamiltonian cycle]] problem translates a graph ''G'' which is to be tested for Hamiltonicity into the pair of graphs ''G'' and ''H'', where ''H'' is a cycle having the same number of vertices as ''G''. Because the Hamiltonian cycle problem is NP-complete even for [[planar graphs]], this shows that subgraph isomorphism remains NP-complete even in the planar case.<ref>{{citation
 | last1 = de la Higuera | first1 = Colin
 | last2 = Janodet | first2 = Jean-Christophe
 | last3 = Samuel | first3 = Émilie
 | last4 = Damiand | first4 = Guillaume
 | last5 = Solnon | first5 = Christine
 | doi = 10.1016/j.tcs.2013.05.026
 | journal = Theoretical Computer Science
 | mr = 3083515
 | pages = 76–99
 | title = Polynomial algorithms for open plane graph and subgraph isomorphisms
 | url = https://www.ibisc.univ-evry.fr/~janodet/pub/hjsds13.pdf
 | volume = 498
 | year = 2013
 | quote = It is known since the mid-70's that the isomorphism problem is solvable in polynomial time for plane graphs. However, it has also been noted that the subisomorphism problem is still N P-complete, in particular because the Hamiltonian cycle problem is NP-complete for planar graphs.| doi-access = free
 }}</ref>

Subgraph isomorphism is a generalization of the [[graph isomorphism problem]], which asks whether ''G'' is isomorphic to ''H'': the answer to the graph isomorphism problem is true if and only if ''G'' and ''H'' both have the same numbers of vertices and edges and the subgraph isomorphism problem for ''G'' and ''H'' is true. However the complexity-theoretic status of graph isomorphism remains an open question.

In the context of the [[Aanderaa–Karp–Rosenberg conjecture]] on the [[Implicit graph#Evasiveness|query complexity]] of monotone graph properties, {{harvtxt|Gröger|1992}} showed that any subgraph isomorphism problem has query complexity Ω(''n''<sup>3/2</sup>); that is, solving the subgraph isomorphism requires an algorithm to check the presence or absence in the input of Ω(''n''<sup>3/2</sup>) different edges in the graph.<ref>Here &Omega; invokes [[Big O notation|Big Omega notation]].</ref>

==Algorithms==
{{harvtxt|Ullmann|1976}} describes a recursive backtracking procedure for solving the subgraph isomorphism problem. Although its running time is, in general, exponential, it takes polynomial time for any fixed choice of ''H'' (with a polynomial that depends on the choice of ''H''). When ''G'' is a [[planar graph]] (or more generally a graph of [[bounded expansion]]) and ''H'' is fixed, the running time of subgraph isomorphism can be reduced to [[linear time]].<ref name="e99">{{harvtxt|Eppstein|1999}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}</ref>

{{harvtxt|Ullmann|2010}} is a substantial update to the 1976 subgraph isomorphism algorithm paper.

{{harvtxt|Cordella|2004}} proposed in 2004 another algorithm based on Ullmann's, VF2, which improves the refinement process using different heuristics and uses significantly less memory.

{{harvtxt|Bonnici|Giugno|2013}} proposed a better algorithm, which improves the initial order of the vertices using some heuristics.

The current state of the art solver for moderately-sized, hard instances is the Glasgow Subgraph Solver ({{harvtxt|McCreesh|Prosser|Trimble|2020}}).<ref>For an experimental evaluation, see {{harvtxt|Solnon|2019}}.</ref> This solver adopts a constraint programming approach, using bit-parallel data structures and specialized propagation algorithms for performance. It supports most common variations of the problem and is capable of counting or enumerating solutions as well as deciding whether one exists.

For large graphs, state-of-the art algorithms include CFL-Match and Turboiso, and extensions thereupon such as DAF by {{harvtxt|Han|Kim|Gu|Park|2019}}.

==Applications==
As subgraph isomorphism has been applied in the area of [[cheminformatics]] to find similarities between chemical compounds from their structural formula; often in this area the term [[substructure search]] is used.<ref>{{harvtxt|Ullmann|1976}}</ref> A query structure is often defined graphically using a [[structure editor]] program; [[SMILES]] based database systems typically define queries using [[Smiles arbitrary target specification|SMARTS]], a [[SMILES]] extension.

The closely related problem of counting the number of isomorphic copies of a graph ''H'' in a larger graph ''G'' has been applied to pattern discovery in databases,<ref>{{harvtxt|Kuramochi|Karypis|2001}}.</ref> the [[bioinformatics]] of protein-protein interaction networks,<ref>{{harvtxt|Pržulj|Corneil|Jurisica|2006}}.</ref> and in [[exponential random graph]] methods for mathematically modeling [[social network]]s.<ref>{{harvtxt|Snijders|Pattison|Robins|Handcock|2006}}.</ref>

{{harvtxt|Ohlrich|Ebeling|Ginting|Sather|1993}} describe an application of subgraph isomorphism in the [[computer-aided design]] of [[electronic circuits]]. Subgraph matching is also a substep in [[graph rewriting]] (the most runtime-intensive), and thus offered by [[Graph rewriting#Implementations and applications|graph rewrite tools]].

The problem is also of interest in [[artificial intelligence]], where it is considered part of an array of [[pattern matching]] in graphs problems; an extension of subgraph isomorphism known as [[structure mining|graph mining]] is also of interest in that area.<ref>http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; expanded version at https://e-reports-ext.llnl.gov/pdf/332302.pdf</ref>

==See also==
*[[Frequent subtree mining]]
*[[Induced subgraph isomorphism problem]]
*[[Maximum common edge subgraph problem]]
*[[Maximum common subgraph isomorphism problem]]

==Notes==
{{Reflist}}

==References==
*{{Citation|first=S. A.|last=Cook|authorlink=Stephen Cook|contribution=The complexity of theorem-proving procedures|year=1971|title=Proc. 3rd ACM Symposium on Theory of Computing|pages=151–158|contribution-url=http://4mhz.de/cook.html|doi=10.1145/800157.805047|title-link=Symposium on Theory of Computing|s2cid=7573663 |doi-access=free}}.
*{{Citation|last=Eppstein|first=David|authorlink=David Eppstein|title=Subgraph isomorphism in planar graphs and related problems|journal=[[Journal of Graph Algorithms and Applications]]|volume=3|issue=3|pages=1–27|year=1999|url=http://www.cs.brown.edu/publications/jgaa/accepted/99/Eppstein99.3.3.pdf|arxiv=cs.DS/9911003|doi=10.7155/jgaa.00014|s2cid=2303110 }}.
*{{Citation|author1-link = Michael R. Garey|last1=Garey|first1=Michael R.|author2-link = David S. Johnson | last2=Johnson | first2 = David S. | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 978-0-7167-1045-5|title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness}}. A1.4: GT48, pg.202.
*{{Citation
| volume = 10
| issue = 3
| pages = 119–127
| last = Gröger
| first =  Hans Dietmar
| title = On the randomized complexity of monotone graph properties
| journal = Acta Cybernetica
| year = 1992
| url = http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf
}}.
*{{Citation|
journal=SIGMOD|
first1=Myoungji|
last1=Han |
first2=Hyunjoon|
last2=  Kim |
first3=Geonmo|
last3=  Gu |
first4=Kunsoo|
last4=  Park| 
first5=Wookshin |
last5= Han| 
year=2019|
title=Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together|
doi=10.1145/3299869.3319880|
s2cid=195259296}}
*{{Citation|first1=Michihiro|last1=Kuramochi|first2=George|last2=Karypis|contribution=Frequent subgraph discovery|title=1st IEEE International Conference on Data Mining|year=2001|page=313|doi=10.1109/ICDM.2001.989534|isbn=978-0-7695-1119-1|citeseerx=10.1.1.22.4992|s2cid=8684662 }}.
*{{Citation|first1=Miles|last1=Ohlrich|first2=Carl|last2=Ebeling|first3=Eka|last3=Ginting|first4=Lisa|last4=Sather|contribution=SubGemini: identifying subcircuits using a fast subgraph isomorphism algorithm|title=Proceedings of the 30th international Design Automation Conference|year=1993|pages=31–37|doi=10.1145/157485.164556|isbn=978-0-89791-577-9|s2cid=5889119 |doi-access=free}}.
*{{citation
 | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil
 | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez
 | contribution = 18.3 The subgraph isomorphism problem and Boolean queries
 | doi = 10.1007/978-3-642-27875-4
 | isbn = 978-3-642-27874-7
 | mr = 2920058
 | pages = 400–401
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Sparsity: Graphs, Structures, and Algorithms
 | volume = 28
 | year = 2012 }}.
*{{Citation|first1=N.|last1=Pržulj|first2=D. G.|last2=Corneil|author2-link=Derek Corneil|first3=I.|last3=Jurisica|title=Efficient estimation of graphlet frequency distributions in protein–protein interaction networks|journal=Bioinformatics|volume=22|issue=8|pages=974–980|year=2006|doi=10.1093/bioinformatics/btl030|pmid=16452112|doi-access=free}}.
*{{Citation|first1=T. A. B.|last1=Snijders|first2=P. E.|last2=Pattison|first3=G.|last3=Robins|first4=M. S.|last4=Handcock|title=New specifications for exponential random graph models|journal=Sociological Methodology|volume=36|issue=1|pages=99–153|year=2006|doi=10.1111/j.1467-9531.2006.00176.x|citeseerx=10.1.1.62.7975|s2cid=10800726 }}.
*{{Citation|first=Julian R.|last=Ullmann|year=1976|title=An algorithm for subgraph isomorphism|journal=[[Journal of the ACM]]|volume=23|issue=1|pages=31–42|doi=10.1145/321921.321925|s2cid=17268751 |doi-access=free}}.
*{{Citation|first=Hasan|last=Jamil|contribution=Computing Subgraph Isomorphic Queries using Structural Unification and Minimum Graph Structures|year=2011|title=26th ACM Symposium on Applied Computing|pages=1058–1063}}.
*{{Citation|first=Julian R.|last=Ullmann|year=2010|title=Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism|journal=[[Journal of Experimental Algorithmics]]|volume=15|pages=1.1|doi=10.1145/1671970.1921702|citeseerx=10.1.1.681.8766|s2cid=15021184 }}.
*{{Citation|first=Luigi P.|last=Cordella|year=2004|title=A (sub) graph isomorphism algorithm for matching large graphs|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=26|issue=10|pages=1367–1372|doi=10.1109/tpami.2004.75|citeseerx=10.1.1.101.5342|pmid=15641723|s2cid=833657 }}
*{{Citation|first1=V.|last1=Bonnici|first2=R.|last2=Giugno|year=2013|title=A subgraph isomorphism algorithm and its application to biochemical data|journal=BMC Bioinformatics|volume=14(Suppl7)|issue=13|pages=S13|doi=10.1186/1471-2105-14-s7-s13|pmid=23815292|pmc=3633016 |doi-access=free }}
*{{Citation|first1=V.|last1=Carletti|first2=P.|last2=Foggia|first3=A.|last3=Saggese|first4=M.|last4=Vento|year=2018|title=Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=40|issue=4|pages=804–818|doi=10.1109/TPAMI.2017.2696940|pmid=28436848|s2cid=3709576 }}
*{{Citation
  | last1=Solnon | first1=Christine
  | title=Graph-Based Representations in Pattern Recognition - 12th IAPR-TC-15 International Workshop, GbRPR 2019, Tours, France, June 19-21, 2019, Proceedings
  | chapter=Experimental Evaluation of Subgraph Isomorphism Solvers
  | series=Lecture Notes in Computer Science
 | publisher=Springer
  | year=2019
  | volume=11510
 | pages=1–13
  | doi=10.1007/978-3-030-20081-7_1| isbn=978-3-030-20080-0
 | s2cid=128270779
 | chapter-url=https://hal.archives-ouvertes.fr/hal-02086499/file/paper.pdf
 }}
*{{Citation
  | last1=McCreesh | first1=Ciaran
  | last2=Prosser | first2=Patrick
  | last3=Trimble | first3=James
  | title=Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25-26, 2020, Proceedings
  | chapter=The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants
  | series=Lecture Notes in Computer Science
 | publisher=Springer
  | year=2020
  | volume=12150
 | pages=316–324
  | doi=10.1007/978-3-030-51372-6_19| isbn=978-3-030-51371-9
 | doi-access=free
  }}
{{Authority control}}

{{DEFAULTSORT:Subgraph Isomorphism Problem}}
[[Category:NP-complete problems]]
[[Category:Graph algorithms]]
[[Category:Computational problems in graph theory]]