Jump to content

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

Максимальные длины змей ( L s ) и витков ( L c ) в задаче «змеи в коробке» для размерностей n от 1 до 4

В теории сложности и теории графов индуцированный изоморфизм подграфов — это 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]

  1. ^ Сысло, Мацей М. (1982), «Проблема изоморфизма подграфов для внешнепланарных графов», Theoretical Computer Science , 17 (1): 91–97, doi : 10.1016/0304-3975(82)90133-5 , MR   0644795 .
  2. ^ Джонсон, Дэвид С. (1985), «Колонка NP-полноты: постоянное руководство», Journal of Algorithms , 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. ^ Heggernes, Пинар ; ван 'т Хоф, Пим; Мейстер, Дэниел; Вилланджер, Ингве (11 января 2015 г.). «Индуцированный изоморфизм подграфов на правильных интервалах и двудольных графах перестановок» (PDF) . Теоретическая информатика . 562 : 252–269. дои : 10.1016/j.tcs.2014.10.002 . ISSN   0304-3975 .
  6. ^ Heggernes, Пинар ; ван 'т Хоф, Пим; Миланич, Мартин (2013). Лекрок, Тьерри; Мушард, Лоран (ред.). «Индуцированные поддеревья в интервальных графах» (PDF) . Материалы 24-го Международного семинара по комбинаторным алгоритмам (IWOCA) . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer: 230–243. дои : 10.1007/978-3-642-45278-9_20 . ISBN  978-3-642-45278-9 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f29cb3b6ad6d0e288e926ace84bf25f3__1704158340
URL1:https://arc.ask3.ru/arc/aa/f2/f3/f29cb3b6ad6d0e288e926ace84bf25f3.html
Заголовок, (Title) документа по адресу, URL1:
Induced subgraph isomorphism problem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)