Задача изоморфизма порождённому подграфу

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Задача изоморфизма порождённому подграфу является NP-полной задачей разрешимости в теории сложности и теории графов. Задача заключается в поиске данного графа как порождённого подграфа другого, большего графа.

Формулировка проблемы

[править | править код]

Формально, задача принимает в качестве входа два графа и , где число вершин в меньше либо равно числу вершин . изоморфен порождённому подграфу графа , если существует инъекция f, которая отображает вершины графа в вершине графа так, что для всех пар вершин x, y в V1, ребро (x, y) присутствует в E1 тогда и только тогда, когда ребро присутствует в E2. Ответ на задачу решения да, если эта функция f существует, и нет в противном случае.

Задача отличается от задачи изоморфизма подграфу в том, что из отсутствия ребра в G1 следует, что соответствующее ребро в G2 должно также отсутствовать. При изоморфизме подграфу эти «лишние» рёбра в G2 могут присутствовать.

Вычислительная сложность

[править | править код]

Сложность задачи изоморфизма порождённому подграфу отделяет внешнепланарные графы от их обобщения, параллельно-последовательных графов — она может быть решена за полиномиальное время для 2-связных внешнепланарных графов, но NP-полна для 2-связных параллельно-последовательных графов[1][2].

Специальные случаи

[править | править код]

Специальный случай поиска длинного пути как порождённого подграфа гиперкуба хорошо изучен и называется задачей о змее в коробке[3]. Задача о наибольшем независимом множестве является также задачей изоморфизма порождённому подграфу, в которой ищется большое независимое множество как порождённый подграф большего графа, а задача о наибольшей клике является задачей изоморфизма порождённому подграфу, в которой ищется большая клика графа как порождённого подграфа большего графа.

Отличие от задачи изоморфизма подграфа

[править | править код]

Хотя задача изоморфизма порождённому подграфу кажется лишь слегка отличающейся от задачи изоморфизма подграфу, ограничение словом «порождённому» вызывает достаточно большие изменения, чтобы заметить их с точки зрения вычислительной сложности.

Например, задача об изоморфизме подграфу является NP-полной на связных собственных интервальных графах и на связных двудольных графах перестановок[4], но задача изоморфизма порождённому подграфу может быть решена за полиномиальное время на этих двух классах[5].

Более того, задача об изоморфизме порождённому поддереву (то есть, задача об изоморфизме порождённого подграфа, где тип графа G2 ограничен деревом) может быть решена за полиномиальное время на интервальных графах, в то время как задача об изоморфизме поддереву является NP-полной на собственных интервальных графах[6].

Примечания

[править | править код]

Литература

[править | править код]
  • Maciej M. Sysło. The subgraph isomorphism problem for outerplanar graphs // Theoretical Computer Science. — 1982. — Т. 17, вып. 1. — С. 91–97. — doi:10.1016/0304-3975(82)90133-5.
  • David S. Johnson. The NP-completeness column: an ongoing guide // Journal of Algorithms. — 1985. — Т. 6, вып. 3. — С. 434–451. — doi:10.1016/0196-6774(85)90012-4.
  • Ramanujacharyulu C., Menon V. V. A note on the snake-in-the-box problem // Publ. Inst. Statist. Univ. Paris. — 1964. — Т. 13. — С. 131–135.
  • Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno. Subgraph isomorphism in graph classes // Discrete Mathematics. — 2012. — Ноябрь (т. 312, вып. 21). — doi:10.1016/j.disc.2012.07.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.