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