В теории сложности и теориях графов , подграф изоморфизм является NP-полной проблема решения , что включает в себя поиск данного графа в качестве индуцированного подграфа большего графа.
Постановка задачи
Формально задача принимает на вход два графа G 1 = ( V 1 , E 1 ) и G 2 = ( V 2 , E 2 ), где количество вершин в V 1 можно считать меньшим или равным количество вершин в V 2 . G 1 является изоморфно к индуцированному подграфу G 2 , если имеется инъективная функция F , которая отображает вершину G 1 с вершинами G 2 такие , что для всех пар вершин х , у в V 1 , ребро ( х , у ) находится в E 1 тогда и только тогда, когда ребро ( f ( x ), f ( y )) находится в E 2 . Ответ на проблему принятия решения - да, если эта функция f существует, и нет в противном случае.
Это отличается от проблемы изоморфизма подграфов тем, что отсутствие ребра в G 1 означает, что соответствующее ребро в G 2 также должно отсутствовать. При изоморфизме подграфов эти «лишние» ребра в G 2 могут присутствовать.
Вычислительная сложность
Сложность индуцированного изоморфизма подграфов отделяет внешнепланарные графы от их обобщающих последовательно-параллельных графов : он может быть решен за полиномиальное время для 2-связных внешнепланарных графов, но является NP-полным для 2-связных последовательно-параллельных графов. [1] [2]
Особые случаи
Частный случай поиска длинного пути как индуцированного подграфа гиперкуба особенно хорошо изучен и называется проблемой змеи в коробке . [3] Задача о максимальном независимом множестве также является проблемой изоморфизма индуцированного подграфа, в которой нужно найти большое независимое множество как индуцированный подграф большего графа, а проблема максимальной клики - это проблема изоморфизма индуцированного подграфа, в которой стремятся найти найти большой кликовый граф как индуцированный подграф большего графа.
Отличия от проблемы изоморфизма подграфов
Хотя проблема индуцированного изоморфизма подграфов кажется лишь немного отличающейся от проблемы изоморфизма подграфов, «индуцированное» ограничение вносит достаточно большие изменения, чтобы мы могли наблюдать различия с точки зрения вычислительной сложности.
Например, проблема изоморфизма подграфов является NP-полной на связных собственных интервальных графах и на связных двудольных графах с перестановками [4], но проблема индуцированного изоморфизма подграфов может быть решена за полиномиальное время на этих двух классах. [5]
Более того, проблема изоморфизма индуцированного поддерева (то есть проблема изоморфизма индуцированного подграфа, где G 1 ограничивается деревом) может быть решена за полиномиальное время на интервальных графах, в то время как проблема изоморфизма поддерева является NP-полной на собственных интервальных графах. [6]
Рекомендации
- ^ Сисло, Мацей М. (1982), "Проблема изоморфизма подграфов для внешнепланарных графов", Теоретическая информатика , 17 (1): 91–97, DOI : 10.1016 / 0304-3975 (82) 90133-5 , MR 0644795.
- ^ Джонсон, Дэвид С. (1985), "NP-полнота колонки: постоянная руководство", журнал алгоритмов , 6 (3): 434-451, DOI : 10,1016 / 0196-6774 (85) 90012-4 , МР 0800733.
- ^ Ramanujacharyulu, C .; Менон, В.В. (1964), "Заметка о проблеме" змея в коробке ", Publ. Inst. Статист. Univ. Париж , 13 : 131–135, MR 0172736.
- ^ Кидзима, Сюдзи; Отачи, Йота; Сайто, Тошики; Уно, Такэаки (1 ноября 2012 г.). «Изоморфизм подграфов в классах графов» . Дискретная математика . 312 (21): 3164–3173. DOI : 10.1016 / j.disc.2012.07.010 .
- ^ Хеггернес, Пинар ; ван 'т Хоф, Пим; Мейстер, Дэниел; Виллангер, Ингве. "Индуцированный изоморфизм подграфов на собственных интервальных и двудольных графах перестановок" (PDF) . отправлено .
- ^ Хеггернес, Пинар ; ван 'т Хоф, Пим; Миланич, Мартин (2013). «Индуцированные поддеревья в интервальных графах» (PDF) . Материалы 24-го международного семинара по комбинаторным алгоритмам (IWOCA) . Появляться.