Проблема индуцированного изоморфизма подграфов - Induced subgraph isomorphism problem - Wikipedia

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

Постановка задачи

Формально задача принимает на вход два графики грамм1=(V1, E1) и грамм2=(V2, E2), где количество вершин в V1 можно предположить, что она меньше или равна количеству вершин в V2. грамм1 является изоморфный индуцированному подграфу грамм2 если есть инъективная функция ж который отображает вершины грамм1 в вершины грамм2 такое, что для всех пар вершин Икс, у в V1, край (Икс, у) в E1 тогда и только тогда, когда край (ж(Икс), ж(у)) в E2. Ответ на проблему решения - да, если эта функция ж существует, и иначе нет.

Это отличается от проблема изоморфизма подграфов в том, что отсутствие преимущества в грамм1 следует, что соответствующее ребро в грамм2 также должно отсутствовать. При изоморфизме подграфов эти "лишние" ребра в грамм2 может присутствовать.

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

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

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

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

Отличия от проблемы изоморфизма подграфов

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

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

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

Рекомендации

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