Induced subgraph isomorphism problem
Encyclopedia
In complexity theory
and graph theory
, induced subgraph isomorphism is an NP-complete
decision problem
that involves finding a given graph as an induced subgraph of a larger graph.
Formally, the problem takes as input two graph
s G1=(V1, E1) and G2=(V2, E2), where the number of vertices in V1 can be assumed to be less than or equal to the number of vertices in V2. G1 is isomorphic
to an induced subgraph of G2 if there is an injective function
f which maps the vertices of G1 to vertices of G2 such that for all pairs of vertices x, y in V1, edge (x, y) is in E1 if and only if the edge (f(x), f(y)) is in E2. 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 that the absence of an edge in G1 implies that the corresponding edge in G2 must also be absent. In subgraph isomorphism, these "extra" edges in G2 may be present.
The special case of finding a long path
as an induced subgraph of a hypercube has been particularly well-studied, and is called the snake-in-the-box
problem. The maximum independent set problem 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 as an induced subgraph of a larger graph.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, induced subgraph isomorphism is an NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
that involves finding a given graph as an induced subgraph of a larger graph.
Formally, the problem takes as input two graph
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
s G1=(V1, E1) and G2=(V2, E2), where the number of vertices in V1 can be assumed to be less than or equal to the number of vertices in V2. G1 is isomorphic
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
to an induced subgraph of G2 if there is an injective function
Injective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
f which maps the vertices of G1 to vertices of G2 such that for all pairs of vertices x, y in V1, edge (x, y) is in E1 if and only if the edge (f(x), f(y)) is in E2. The answer to the decision problem is yes if this function f exists, and no otherwise.
This is different from the subgraph isomorphism problem
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....
in that the absence of an edge in G1 implies that the corresponding edge in G2 must also be absent. In subgraph isomorphism, these "extra" edges in G2 may be present.
The special case of finding a long path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
as an induced subgraph of a hypercube has been particularly well-studied, and is called the snake-in-the-box
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 gets to a new corner, the previous corner and all of...
problem. The maximum independent set problem is also an induced subgraph isomorphism problem in which one seeks to find a large independent set
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
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 as an induced subgraph of a larger graph.