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 graphs *G*_{1}=(*V*_{1}, *E*_{1}) and *G*_{2}=(*V*_{2}, *E*_{2}), where the number of vertices in *V*_{1} can be assumed to be less than or equal to the number of vertices in *V*_{2}. *G*_{1} is isomorphic to an induced subgraph of *G*_{2} if there is an injective function *f* which maps the vertices of *G*_{1} to vertices of *G*_{2} such that for all pairs of vertices *x*, *y* in *V*_{1}, edge (*x*, *y*) is in *E*_{1} if and only if the edge (*f*(*x*), *f*(*y*)) is in *E*_{2}. 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 *G*_{1} implies that the corresponding edge in *G*_{2} must also be absent. In subgraph isomorphism, these "extra" edges in *G*_{2} may be present.

The complexity of induced subgraph isomorphism separates outerplanar graphs from their generalization series–parallel graphs: it may be solved in polynomial time for 2-connected outerplanar graphs, but is NP-complete for 2-connected series–parallel graphs.^{ [1] }^{ [2] }

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.^{ [3] } 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.

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,^{ [4] } but the **induced** subgraph isomorphism problem can be solved in polynomial time on these two classes.^{ [5] }

Moreover, the induced subtree isomorphism problem (i.e. the induced subgraph isomorphism problem where *G*_{1} 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.^{ [6] }

In computer science, the **clique problem** is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

This is a **glossary of graph theory**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

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 generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.

In the mathematical area of graph theory, a **clique** is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph *G* is an induced subgraph of *G* that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

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 of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph’s complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

In the mathematical field of graph theory, a **complete bipartite graph** or **biclique** is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

In graph theory, a **perfect graph** is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have .

In the mathematical area of graph theory, a **chordal graph** is one in which all cycles of four or more vertices have a *chord*, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called **rigid circuit graphs** or **triangulated graphs**.

In graph theory, a **cograph**, or **complement-reducible graph**, or ** P_{4}-free graph**, is a graph that can be generated from the single-vertex graph

In graph theory, the **metric dimension** of a graph *G* is the minimum cardinality of a subset *S* of vertices such that all other vertices are uniquely determined by their distances to the vertices in *S*. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

The **graph isomorphism problem** is the computational problem of determining whether two finite graphs are isomorphic.

In graph theory, a **path decomposition** of a graph *G* is, informally, a representation of *G* as a "thickened" path graph, and the **pathwidth** of *G* is a number that measures how much the path was thickened to form *G*. More formally, a path-decomposition is a sequence of subsets of vertices of *G* such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as **interval thickness**, **vertex separation number**, or **node searching number**.

In graph theory, an area of mathematics, a **claw-free graph** is a graph that does not have a claw as an induced subgraph.

In graph theory, the **clique-width** of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations :

- Creation of a new vertex
*v*with label*i* - Disjoint union of two labeled graphs
*G*and*H* - Joining by an edge every vertex labeled
*i*to every vertex labeled*j*, where - Renaming label
*i*to label*j*

In graph theory, a **clique cover** or **partition into cliques** of a given undirected graph is a partition of the vertices of the graph into cliques, subsets of vertices within which every two vertices are adjacent. A **minimum clique cover** is a clique cover that uses as few cliques as possible. The minimum *k* for which a clique cover exists is called the **clique cover number** of the given graph.

In the mathematical area of graph theory, an undirected graph *G* is **strongly chordal** if it is a chordal graph and every cycle of even length in *G* has an *odd chord*, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

In graph theory, the **tree-depth** of a connected undirected graph *G* is a numerical invariant of *G*, the minimum height of a Trémaux tree for a supergraph of *G*. This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth graph width parameter measures how far a graph is from being a tree, this parameter measures how far a graph is from being a star.

In graph theory and computer science, the **graph sandwich problem** is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched" between two other graphs, one of which must be a subgraph and the other of which must be a supergraph of the desired graph.

In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let be an undirected graph and let be a subgraph of . Then the *density* of is defined to be .

In graph theory, the **bipartite half** or **half-square** of a bipartite graph *G* = (*U*,*V*,*E*) is a graph whose vertex set is one of the two sides of the bipartition and in which there is an edge *u*_{i}*u*_{j} for each two vertices *u*_{i} and *u*_{j} in *U* that are at distance two from each other in *G*. That is, in a more compact notation, the bipartite half is *G*^{2}[*U*] where the superscript 2 denotes the square of a graph and the square brackets denote an induced subgraph.

- ↑ Sysło, Maciej M. (1982), "The subgraph isomorphism problem for outerplanar graphs",
*Theoretical Computer Science*,**17**(1): 91–97, doi:10.1016/0304-3975(82)90133-5, MR 0644795 . - ↑ Johnson, David S. (1985), "The NP-completeness column: an ongoing guide",
*Journal of Algorithms*,**6**(3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733 . - ↑ Ramanujacharyulu, C.; Menon, V. V. (1964), "A note on the snake-in-the-box problem",
*Publ. Inst. Statist. Univ. Paris*,**13**: 131–135, MR 0172736 . - ↑ Kijima, Shuji; Otachi, Yota; Saitoh, Toshiki; Uno, Takeaki (1 November 2012). "Subgraph isomorphism in graph classes".
*Discrete Mathematics*.**312**(21): 3164–3173. doi: 10.1016/j.disc.2012.07.010 . - ↑ Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel; Villanger, Yngve. "Induced subgraph isomorphism on proper interval and bipartite permutation graphs" (PDF).
*submitted*. - ↑ Heggernes, Pinar; van 't Hof, Pim; Milanič, Martin (2013). "Induced Subtrees in Interval Graphs" (PDF).
*Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA)*. To appear.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.