Editing Subgraph isomorphism problem (section)

==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>