Induced subgraph isomorphism problem
In
Problem statement
Formally, the problem takes as input two graphs 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.
Computational complexity
The complexity of induced subgraph isomorphism separates
Special cases
The special case of finding a long
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,[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 G1 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]
References
- MR 0644795.
- MR 0800733.
- MR 0172736.
- .
- ISSN 0304-3975.
- ISBN 978-3-642-45278-9.