In complexity theory and

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, induced subgraph isomorphism is an

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

that involves finding a given graph as an

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

of a larger graph.

Problem statement

Formally, the problem takes as input two

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

s ''G''₁=(''V''₁, ''E''₁) and ''G''₂=(''V''₂, ''E''₂), where the number of vertices in ''V''₁ can be assumed to be less than or equal to the number of vertices in ''V''₂. ''G''₁ is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

to an induced subgraph of ''G''₂ if there is an

injective function In mathematics, an injective function (also known as injection, or one-to-one function ) is a function that maps distinct elements of its domain to distinct elements of its codomain; that is, implies (equivalently by contraposition, impl ...

''f'' which maps the vertices of ''G''₁ to vertices of ''G''₂ such that for all pairs of vertices ''x'', ''y'' in ''V''₁, edge (''x'', ''y'') is in ''E''₁ if and only if the edge (''f''(''x''), ''f''(''y'')) is in ''E''₂. The answer to the decision problem is yes if this function ''f'' exists, and no otherwise. This is different from the

subgraph isomorphism problem In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a gen ...

in that the absence of an edge in ''G''₁ implies that the corresponding edge in ''G''₂ must also be absent. In subgraph isomorphism, these "extra" edges in ''G''₂ may be present.

Computational complexity

The complexity of induced subgraph isomorphism separates

outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two f ...

s from their generalization

series–parallel graph In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. Definition and t ...

s: it may be solved in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

for 2-connected outerplanar graphs, but is NP-complete for 2-connected series–parallel graphs.

Special cases

The special case of finding a long

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desir ...

as an induced subgraph of a

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square ( ) and a cube ( ); the special case for is known as a ''tesseract''. It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel l ...

has been particularly well-studied, and is called the snake-in-the-box problem. The

maximum independent set problem In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two ...

is also an induced subgraph isomorphism problem in which one seeks to find a large independent set as an induced subgraph of a larger graph, and the maximum clique problem is an induced subgraph isomorphism problem in which one seeks to find a large

clique graph In graph theory, a clique graph of an undirected graph is another graph that represents the structure of cliques in . Clique graphs were discussed at least as early as 1968, and a characterization of clique graphs was given in 1971. Formal ...

as an induced subgraph of a larger graph.

Differences with the subgraph isomorphism problem

Although the induced subgraph isomorphism problem seems only slightly different from the subgraph isomorphism problem, the "induced" restriction introduces changes large enough that we can witness differences from a computational complexity point of view. For example, the subgraph isomorphism problem is NP-complete on connected proper interval graphs and on connected bipartite permutation graphs, but the induced subgraph isomorphism problem can be solved in polynomial time on these two classes. Moreover, the induced subtree isomorphism problem (i.e. the induced subgraph isomorphism problem where ''G''₁ is restricted to be a tree) can be solved in polynomial time on interval graphs, while the subtree isomorphism problem is NP-complete on proper interval graphs.

References

{{reflist NP-complete problems Computational problems in graph theory