Проблема изоморфизма индуцированных подграфов

Максимальные длины змей ( L _s ) и катушек ( L _c ) в задаче о змеях в коробке для размерностей n от 1 до 4

В теории сложности и теории графов изоморфизм индуцированных подграфов — это NP-полная задача принятия решений , которая заключается в нахождении заданного графа как индуцированного подграфа большего графа.

Постановка проблемы

Формально задача принимает в качестве входных данных два графа G ₁ =( V ₁ , E ₁ ) и G ₂ = ( V ₂ , E ₂ ), где число вершин в V ₁ можно считать меньшим или равным числу вершин в V ₂ . G ₁ изоморфен индуцированному подграфу G _{2 ,} если существует инъективная функция f , которая отображает вершины G ₁ в вершины G _{2 ,} такая что для всех пар вершин x , y в V ₁ ребро ( x , y ) находится в E ₁ тогда и только тогда, когда ребро ( f ( x ), f ( y )) находится в E ₂ . Ответ на задачу принятия решения — да, если эта функция f существует, и нет в противном случае.

Это отличается от проблемы изоморфизма подграфов тем, что отсутствие ребра в G ₁ подразумевает, что соответствующее ребро в G ₂ также должно отсутствовать. В изоморфизме подграфов эти «лишние» ребра в G ₂ могут присутствовать.

Сложность вычислений

Сложность индуцированного изоморфизма подграфов отделяет внешнепланарные графы от их обобщения последовательно-параллельных графов : она может быть решена за полиномиальное время для 2-связных внешнепланарных графов, но является NP-полной для 2-связных последовательно-параллельных графов. ^{[1] [2]}

Особые случаи

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

Различия с проблемой изоморфизма подграфов

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

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

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

Ссылки

1. Sysło, Maciej M. (1982), «Проблема изоморфизма подграфов для внешнепланарных графов», Theoretical Computer Science , 17 (1): 91–97, doi :10.1016/0304-3975(82)90133-5, MR  0644795.
2. Джонсон, Дэвид С. (1985), «Столбец NP-полноты: постоянное руководство», Журнал алгоритмов , 6 (3): 434–451, doi :10.1016/0196-6774(85)90012-4, MR  0800733.
3. Рамануджачарьюлу, К.; Менон, В.В. (1964), «Заметка о проблеме змеи в коробке», Изд. Института статистики, Париж , 13 : 131–135, MR  0172736.
4. Кидзима, Сюдзи; Отачи, Йота; Сайто, Тошики; Уно, Такеаки (1 ноября 2012 г.). «Изоморфизм подграфов в классах графов». Дискретная математика . 312 (21): 3164–3173. дои : 10.1016/j.disc.2012.07.010 .
5. Хеггернес, Пинар ; ван 'т Хоф, Пим; Майстер, Даниэль; Виллангер, Ингве (2015-01-11). "Индуцированный изоморфизм подграфов на надлежащих интервальных и двудольных графах перестановок" (PDF) . Теоретическая информатика . 562 : 252–269. doi :10.1016/j.tcs.2014.10.002. ISSN  0304-3975.
6. Хеггернес, Пинар ; ван 'т Хоф, Пим; Миланич, Мартин (2013). "Индуцированные поддеревья в интервальных графах" (PDF) . В Lecroq, Тьерри; Мушар, Лоран (ред.). Труды 24-го Международного семинара по комбинаторным алгоритмам (IWOCA) . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. стр. 230–243. doi :10.1007/978-3-642-45278-9_20. ISBN 978-3-642-45278-9.