Проблема изоморфизма подграфов - Википедия - Subgraph isomorphism problem

В теоретическая информатика, то изоморфизм подграфов проблема - это вычислительная задача, в которой два графики грамм и ЧАС даны в качестве входных данных, и необходимо определить, грамм содержит подграф то есть изоморфный к ЧАСИзоморфизм подграфов является обобщением как проблема максимальной клики и проблема проверки того, содержит ли граф Гамильтонов цикл, и поэтому НП-полный.[1] Однако некоторые другие случаи изоморфизма подграфов могут быть решены за полиномиальное время.[2]

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

Проблема решения и вычислительная сложность

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

Формальный вопрос:

Позволять , быть графами. Есть ли подграф такой, что ? Т.е. существует ли биекция такой, что ?

Доказательство NP-полноты изоморфизма подграфов простое и основано на редукции проблема клики, NP-полная задача решения, в которой входом является единственный граф грамм и ряд k, и вопрос в том, грамм содержит полный подграф с k вершины. Чтобы перевести это в проблему изоморфизма подграфов, просто позвольте ЧАС быть полным графом Kk; то ответ на проблему изоморфизма подграфов для грамм и ЧАС равен ответу на проблему клики для грамм и k. Поскольку проблема клики NP-полна, это редукция "много-один" за полиномиальное время показывает, что изоморфизм подграфов также является NP-полным.[3]

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

Изоморфизм подграфов является обобщением проблема изоморфизма графов, который спрашивает, грамм изоморфен ЧАС: ответ на проблему изоморфизма графов верен тогда и только тогда, когда грамм и ЧАС оба имеют одинаковое количество вершин и ребер, и проблема изоморфизма подграфов для грамм и ЧАС правда. Однако теоретико-сложностный статус изоморфизма графов остается открытым вопросом.

В контексте Гипотеза Андераа – Карпа – Розенберга на сложность запроса свойств монотонного графа, Грёгер (1992) показал, что любая проблема изоморфизма подграфов имеет сложность запроса Ω (п3/2); то есть для решения изоморфизма подграфов требуется алгоритм, проверяющий наличие или отсутствие на входе Ω (п3/2) различных ребер в графе.[5]

Алгоритмы

Ульманн (1976) описывает рекурсивную процедуру поиска с возвратом для решения проблемы изоморфизма подграфов. Хотя время его работы, как правило, экспоненциально, для любого фиксированного выбора требуется полиномиальное время. ЧАС (с полиномом, зависящим от выбора ЧАС). Когда грамм это планарный граф (или, в более общем смысле, график ограниченное расширение ) и ЧАС фиксировано, время работы изоморфизма подграфов можно сократить до линейное время.[2]

Ульманн (2010) является существенным обновлением статьи об алгоритме изоморфизма подграфов 1976 года.

Корделла (2004) предложил в 2004 году другой алгоритм, основанный на алгоритме Ульмана, VF2, который улучшает процесс уточнения с использованием различных эвристик и использует значительно меньше памяти.

Бонничи (2013) предложил лучший алгоритм, улучшающий начальный порядок вершин с помощью некоторых эвристик.

Для больших графиков современные алгоритмы включают CFL-Match и Turboiso, а также расширения к ним, такие как DAF by Хан (2019).

Приложения

Поскольку изоморфизм подграфов был применен в области хеминформатика находить сходство между химическими соединениями по их структурной формуле; часто в этой области термин поиск субструктуры используется.[6] Структура запроса часто определяется графически с помощью редактор структуры программа; Улыбки системы баз данных обычно определяют запросы, используя СМАРТС, а Улыбки расширение.

Тесно связанная проблема подсчета количества изоморфных копий графа ЧАС в большем графике грамм был применен для обнаружения шаблонов в базах данных,[7] то биоинформатика сетей белок-белкового взаимодействия,[8] И в экспоненциальный случайный граф методы математического моделирования социальные сети.[9]

Ohlrich et al. (1993) описать приложение изоморфизма подграфов в системы автоматизированного проектирования из электронные схемы. Сопоставление подграфов также является подшагом в переписывание графа (самый ресурсоемкий), поэтому его предлагает инструменты для перезаписи графиков.

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

Смотрите также

Примечания

  1. ^ Оригинал Повар (1971) документ, который доказывает Теорема Кука – Левина уже показал, что изоморфизм подграфов является NP-полным, используя редукцию из 3-СБ с участием клик.
  2. ^ а б Эппштейн (1999); Нешетржил и Оссона де Мендес (2012)
  3. ^ Вегенер, Инго (2005), Теория сложности: изучение границ эффективных алгоритмов, Springer, стр. 81, ISBN  9783540210450.
  4. ^ де ла Игера, Колин; Жаноде, Жан-Кристоф; Самуэль, Эмили; Дамианд, Гийом; Солнон, Кристина (2013), «Полиномиальные алгоритмы для изоморфизмов открытых плоских графов и подграфов» (PDF), Теоретическая информатика, 498: 76–99, Дои:10.1016 / j.tcs.2013.05.026, МИСТЕР  3083515, С середины 70-х годов известно, что проблема изоморфизма разрешима за полиномиальное время для плоских графов. Однако также было отмечено, что проблема субизоморфизма все еще является N P-полной, в частности потому, что проблема гамильтонова цикла является NP-полной для плоских графов.
  5. ^ Здесь Ω вызывает Обозначение Big Omega.
  6. ^ Ульманн (1976)
  7. ^ Курамочи и Карипис (2001).
  8. ^ Пржуль, Корнейл и Юрисица (2006).
  9. ^ Snijders et al. (2006).
  10. ^ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; расширенная версия на https://e-reports-ext.llnl.gov/pdf/332302.pdf

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