Intheoretical computer science, thesubgraph isomorphism problem is a computational task in which twographs${\displaystyle G}$ and${\displaystyle H}$ are given as input, and one must determine whether${\displaystyle G}$ contains asubgraph that isisomorphic to${\displaystyle H}$.Subgraph isomorphism is a generalization of both themaximum clique problem and the problem of testing whether a graph contains aHamiltonian cycle, and is thereforeNP-complete.^[1] However certain other cases of subgraph isomorphism may be solved in polynomial time.^[2]

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

To prove subgraph isomorphism is NP-complete, it must be formulated as adecision problem. The input to the decision problem is a pair of graphs${\displaystyle G}$ andH. The answer to the problem is positive ifH is isomorphic to a subgraph ofG, and negative otherwise.

Formal question:

Let${\displaystyle G=(V,E)}$,${\displaystyle H=(V^{\mathrm{\prime }},E^{\mathrm{\prime }})}$ be graphs. Is there a subgraph${\displaystyle G_0=(V_0,E_0)\mid V_0\subseteq V,E_0\subseteq E\cap (V_0\times V_0)}$ such that${\displaystyle G_0\cong H}$? I. e., does there exist abijection${\displaystyle f:V_0\to V^{\mathrm{\prime }}}$ such that${\displaystyle \{v_1,v_2\}\in E_0⟺\{f(v_1),f(v_2)\}\in E^{\mathrm{\prime }}}$?

The proof of subgraph isomorphism being NP-complete is simple and based on reduction of theclique problem, an NP-complete decision problem in which the input is a single graphG and a numberk, and the question is whetherG contains acomplete subgraph withk vertices. To translate this to a subgraph isomorphism problem, simply letH be the complete graphK_k; then the answer to the subgraph isomorphism problem forG andH is equal to the answer to the clique problem forG andk. Since the clique problem is NP-complete, thispolynomial-time many-one reduction shows that subgraph isomorphism is also NP-complete.^[3]

An alternative reduction from theHamiltonian cycle problem translates a graphG which is to be tested for Hamiltonicity into the pair of graphsG andH, whereH is a cycle having the same number of vertices asG. Because the Hamiltonian cycle problem is NP-complete even forplanar graphs, this shows that subgraph isomorphism remains NP-complete even in the planar case.^[4]

Subgraph isomorphism is a generalization of thegraph isomorphism problem, which asks whetherG is isomorphic toH: the answer to the graph isomorphism problem is true if and only ifG andH both have the same numbers of vertices and edges and the subgraph isomorphism problem forG andH is true. However the complexity-theoretic status of graph isomorphism remains an open question.

In the context of theAanderaa–Karp–Rosenberg conjecture on thequery complexity of monotone graph properties,Gröger (1992) showed that any subgraph isomorphism problem has query complexity Ω(n^3/2); that is, solving the subgraph isomorphism requires an algorithm to check the presence or absence in the input of Ω(n^3/2) different edges in the graph.^[5]

Ullmann (1976) describes a recursivebacktracking procedure for solving the subgraph isomorphism problem. Although its running time is, in general, exponential, it takes polynomial time for any fixed choice ofH (with a polynomial that depends on the choice ofH). WhenG is aplanar graph (or more generally a graph ofbounded expansion) andH is fixed, the running time of subgraph isomorphism can be reduced tolinear time.^[2]

Ullmann (2010) is a substantial update to the 1976 subgraph isomorphism algorithm paper.

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.

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 (McCreesh, Prosser & Trimble (2020)).^[6] This solver adopts aconstraint 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 byHan et al. (2019).

As subgraph isomorphism has been applied in the area ofcheminformatics to find similarities between chemical compounds from theirstructural formula; often in this area the termsubstructure search is used.^[7] A query structure is often defined graphically using astructure editor program;SMILES based database systems typically define queries usingSMARTS, aSMILES extension.

The closely related problem of counting the number of isomorphic copies of a graphH in a larger graphG has been applied to pattern discovery in databases,^[8] thebioinformatics of protein-protein interaction networks,^[9] and inexponential random graph methods for mathematically modelingsocial networks.^[10]

Ohlrich et al. (1993) describe an application of subgraph isomorphism in thecomputer-aided design ofelectronic circuits. Subgraph matching is also a substep ingraph rewriting (the most runtime-intensive), and thus offered bygraph rewrite tools.

The problem is also of interest inartificial intelligence, where it is considered part of an array ofpattern matching in graphs problems; an extension of subgraph isomorphism known asgraph mining is also of interest in that area.^[11]

• Frequent subtree mining
• Induced subgraph isomorphism problem
• Maximum common edge subgraph problem
• Maximum common subgraph isomorphism problem

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

• NP-complete problems
• Graph algorithms
• Computational problems in graph theory

• Articles with short description
• Short description is different from Wikidata
• CS1: long volume value