The isomorphism problem for a generated subgraph

The isomorphism problem for a generated subgraph is an NP-complete solvability problem in complexity theory and graph theory . The task is to search for a given graph as a generated subgraph of another, larger graph.

Content

1 Problem statement
2 Computational complexity
3 Special cases
4 Difference from the subgraph isomorphism problem
5 notes
6 Literature

Problem

Formally, the task takes two graphs as input $G_{1}=(V_{1},E_{1})$ ${\ displaystyle G_ {1} = (V_ {1}, E_ {1})}$ and $G_{2}=(V_{2},E_{2})$ ${\ displaystyle G_ {2} = (V_ {2}, E_ {2})}$ where the number of vertices in $V_{1}$ ${\ displaystyle V_ {1}}$ less than or equal to the number of vertices $V_{2}$ ${\ displaystyle V_ {2}}$ . $G_{1}$ ${\ displaystyle G_ {1}}$ isomorphic to a generated subgraph of a graph $G_{2}$ ${\ displaystyle G_ {2}}$ if there exists an injection f that displays the vertices of the graph $G_{1}$ ${\ displaystyle G_ {1}}$ at the top of the graph $G_{2}$ ${\ displaystyle G_ {2}}$ so that for all pairs of vertices x , y in V ₁ , the edge ( x , y ) is present in E ₁ if and only if the edge $(f(x),f(y))$ ${\ displaystyle (f (x), f (y))}$ present in E ₂ . The answer to the solution problem is yes, if this function f exists, and no otherwise.

The problem differs from the problem of isomorphism of a subgraph in that the absence of an edge in G ₁ implies that the corresponding edge in G ₂ must also be absent. Under isomorphism of a subgraph, these “extra” edges in G ₂ may be present.

Computational complexity

The complexity of the isomorphism problem for the generated subgraph separates outerplanar graphs from their generalization, parallel-sequential graphs - it can be solved in polynomial time for 2-connected outerplanar graphs, but NP-complete for 2-connected parallel-sequential graphs ^[1] ^[2] .

Special Cases

The special case of searching for a long path as a generated subgraph of a hypercube is well studied and is called the snake in box problem ^[3] . The problem of the largest independent set is also an isomorphism problem to the generated subgraph, in which a large independent set is sought as a generated subgraph of a larger graph, and the problem of the largest clique is the isomorphism problem to the generated subgraph, in which a large clique of the graph is searched as the generated subgraph of a larger graph.

Difference from the subgraph isomorphism problem

Although the problem of isomorphism to the generated subgraph seems only slightly different from the problem of isomorphism to the subgraph, the restriction to the word "generated" causes large enough changes to notice them in terms of computational complexity.

For example, the subgraph isomorphism problem is NP-complete on connected eigenvalue interval graphs and on connected bipartite permutation graphs ^[4] , but the isomorphism problem for the generated subgraph can be solved in polynomial time on these two classes ^[5] .

Moreover, the problem of isomorphism to the generated subtree (i.e., the problem of isomorphism to the generated subgraph, where the type of the graph G _{2 is} bounded by a tree) can be solved in polynomial time on interval graphs, while the problem of the subtree isomorphism is NP-complete on eigenvalues interval graphs ^[6] .

Notes

↑ Sysło, 1982 , p. 91–97.
↑ Johnson, 1985 , p. 434–451.
↑ Ramanujacharyulu, Menon, 1964 , p. 131-135.
↑ Kijima, Otachi, Saitoh, Uno, 2012 , p. 3164-3173.
↑ Heggernes, van't Hofm, Meister, Villanger, 2015 .
↑ Heggernes, van't Hof, Milanič, 2013 .

Literature

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

[_64c200261320e955-1] Sysło, 1982 , p. 91–97.

[_eab7c0bdde44e8c5-2] Johnson, 1985 , p. 434–451.

[_d57b88eeea427267-3] Ramanujacharyulu, Menon, 1964 , p. 131-135.

[_625d621d7aaa0ed8-4] Kijima, Otachi, Saitoh, Uno, 2012 , p. 3164-3173.

[_5ada975181fd0ff6-5] Heggernes, van't Hofm, Meister, Villanger, 2015 .

[_00edccc6fa04f093-6] Heggernes, van't Hof, Milanič, 2013 .