In complexity theory and

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, induced subgraph isomorphism is an

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

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 of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

that involves finding a given graph as an

induced subgraph In the mathematical field of 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. Defini ...

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 discre ...

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 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 them. The word is ...

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; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...

''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 isomor ...

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 fo ...

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 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 performed by ...

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 * Desire p ...

as an induced subgraph of a

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...

has been particularly well-studied, and is called the

snake-in-the-box The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it g ...

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 In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cli ...

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 d ...

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