Induced subgraph isomorphism problem (original) (raw)

From Wikipedia, the free encyclopedia

NP-complete graph problem

Maximum lengths of snakes (_L_s) and coils (_L_c) in the snakes-in-the-box problem for dimensions n from 1 to 4

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.

Computational complexity

[edit]

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.

Differences with the subgraph isomorphism problem

[edit]

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]

  1. ^ 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.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel; Villanger, Yngve (2015-01-11). "Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs" (PDF). Theoretical Computer Science. 562: 252–269. doi:10.1016/j.tcs.2014.10.002. ISSN 0304-3975.
  6. ^ Heggernes, Pinar; van 't Hof, Pim; Milanič, Martin (2013). "Induced Subtrees in Interval Graphs" (PDF). In Lecroq, Thierry; Mouchard, Laurent (eds.). Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA). Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 230–243. doi:10.1007/978-3-642-45278-9_20. ISBN 978-3-642-45278-9.