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

В теоретической информатике проблема изоморфизма подграфов — это вычислительная задача, в которой в качестве входных данных даны два графа G и H , и необходимо определить, содержит ли G подграф , изоморфный H. Изоморфизм подграфов — это обобщение как задачи о максимальной клике , так и задачи проверки того , содержит ли граф гамильтонов цикл , и, следовательно, является NP-полным . ^[1] Однако некоторые другие случаи изоморфизма подграфов могут быть решены за полиномиальное время. ^[2]

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

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

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

Пусть , — графы. Существует ли подграф такой, что ? Т. е. существует ли биекция такая, что ?${\displaystyle G=(V,E)}$${\displaystyle H=(V^{\prime},E^{\prime})}$${\displaystyle G_{0}=(V_{0},E_{0})\mid V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0}) }$${\displaystyle G_{0}\cong H}$ ${\displaystyle f\двоеточие V_{0}\rightarrow V^{\prime }}$${\displaystyle \{\,v_{1},v_{2}\,\}\in E_{0}\iff \{\,f(v_{1}),f(v_{2})\,\ }\in E^{\prime }}$

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

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

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

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

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

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

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

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

Текущим решением для сложных примеров среднего размера является Glasgow Subgraph Solver (McCreesh, Prosser & Trimble (2020)). ^[6] Этот решатель использует подход программирования ограничений, используя параллельные битовые структуры данных и специализированные алгоритмы распространения для повышения производительности. Он поддерживает наиболее распространенные варианты задачи и способен подсчитывать или перечислять решения, а также решать, существует ли одно из них.

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

Как изоморфизм подграфов применялся в области хемоинформатики для поиска сходств между химическими соединениями по их структурной формуле; часто в этой области используется термин « поиск подструктуры» . ^[7] Структура запроса часто определяется графически с помощью программы- редактора структур ; системы баз данных на основе SMILES обычно определяют запросы с помощью SMARTS , расширения SMILES .

Тесно связанная задача подсчета числа изоморфных копий графа H в большем графе G применялась для обнаружения закономерностей в базах данных ^{[8] ,} в биоинформатике сетей белок-белкового взаимодействия ^[9] и в методах экспоненциальных случайных графов для математического моделирования социальных сетей ^[10] .

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

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

• Частая добыча поддеревьев
• Проблема изоморфизма индуцированных подграфов
• Задача о максимальном общем ребре подграфа
• Задача изоморфизма максимального общего подграфа

• Кук, С.А. (1971), «Сложность процедур доказательства теорем», Труды 3-го симпозиума ACM по теории вычислений , стр.  151–158 , doi : 10.1145/800157.805047 , S2CID  7573663.
• Эппштейн, Дэвид (1999), «Изоморфизм подграфов в планарных графах и связанные с ним проблемы» (PDF) , Журнал графовых алгоритмов и приложений , 3 (3): 1– 27, arXiv : cs.DS/9911003 , doi : 10.7155/jgaa.00014, S2CID  2303110.
• Гэри, Майкл Р.; Джонсон , Дэвид С. (1979), Компьютеры и неразрешимость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5. A1.4: GT48, стр.202.
• Грёгер, Ганс Дитмар (1992), «О рандомизированной сложности свойств монотонных графов» (PDF) , Acta Cybernetica , 10 (3): 119–127.
• Хан, Мёнджи; Ким, Хёнджун; Гу, Джеонмо; Пак, Кунсу; Хан, Укшин (2019), «Эффективное сопоставление подграфов: гармонизация динамического программирования, адаптивного порядка сопоставления и неудавшегося множества», SIGMOD , doi : 10.1145/3299869.3319880, S2CID  195259296
• Курамочи, Мичихиро; Карипис, Джордж (2001), «Частое обнаружение подграфов», 1-я Международная конференция IEEE по интеллектуальному анализу данных , стр. 313, CiteSeerX  10.1.1.22.4992 , doi :10.1109/ICDM.2001.989534, ISBN 978-0-7695-1119-1, S2CID  8684662.
• Ольрих, Майлз; Эбелинг, Карл; Гинтинг, Эка; Сатер, Лиза (1993), «SubGemini: идентификация подсхем с использованием быстрого алгоритма изоморфизма подграфов», Труды 30-й международной конференции по автоматизации проектирования , стр.  31–37 , doi : 10.1145/157485.164556 , ISBN 978-0-89791-577-9, S2CID  5889119.
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), "18.3 Проблема изоморфизма подграфов и булевы запросы", Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Springer, стр.  400–401 , doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058.
• Pržulj, N.; Corneil, DG ; Jurisica, I. (2006), "Эффективная оценка распределений частот графлетов в сетях белок-белкового взаимодействия", Bioinformatics , 22 (8): 974–980 , doi : 10.1093/bioinformatics/btl030 , PMID  16452112.
• Снайдерс, Т.А.Б.; Паттисон, П.Е.; Робинс, Г.; Хэндкок, М.С. (2006), «Новые спецификации для экспоненциальных случайных графовых моделей», Социологическая методология , 36 (1): 99–153 , CiteSeerX  10.1.1.62.7975 , doi :10.1111/j.1467-9531.2006.00176.x, S2CID  10800726.
• Ульман, Джулиан Р. (1976), «Алгоритм изоморфизма подграфов», Журнал ACM , 23 (1): 31– 42, doi : 10.1145/321921.321925 , S2CID  17268751.
• Джамиль, Хасан (2011), «Вычисление изоморфных запросов подграфов с использованием структурной унификации и минимальных структур графа», 26 -й симпозиум ACM по прикладным вычислениям , стр.  1058–1063.
• Ульман, Джулиан Р. (2010), «Бит-векторные алгоритмы для удовлетворения бинарных ограничений и изоморфизма подграфов», Журнал экспериментальной алгоритмики , 15 : 1.1, CiteSeerX  10.1.1.681.8766 , doi : 10.1145/1671970.1921702, S2CID  15021184.
• Корделла, Луиджи П. (2004), «Алгоритм изоморфизма (под)графов для сопоставления больших графов», Труды IEEE по анализу шаблонов и машинному интеллекту , 26 (10): 1367– 1372, CiteSeerX  10.1.1.101.5342 , doi :10.1109/tpami.2004.75, PMID  15641723, S2CID  833657
• Бонничи, В.; Джуньо, Р. (2013), «Алгоритм изоморфизма подграфов и его применение к биохимическим данным», BMC Bioinformatics , 14(Suppl7) (13): S13, doi : 10.1186/1471-2105-14-s7-s13 , PMC  3633016 , PMID  23815292
• Карлетти, В.; Фоджа, П.; Саггезе, А.; Венто, М. (2018), «Проверка временной сложности точного изоморфизма подграфов для огромных и плотных графов с помощью VF3», Труды IEEE по анализу шаблонов и машинному интеллекту , 40 (4): 804–818 , doi :10.1109/TPAMI.2017.2696940, PMID  28436848, S2CID  3709576
• Solnon, Christine (2019), "Экспериментальная оценка решателей изоморфизма подграфов" (PDF) , Графовые представления в распознавании образов - 12-й международный семинар IAPR-TC-15, GbRPR 2019, Тур, Франция, 19-21 июня 2019 г., Труды , Конспект лекций по информатике, т. 11510, Springer, стр.  1– 13, doi :10.1007/978-3-030-20081-7_1, ISBN 978-3-030-20080-0, S2CID  128270779
• McCreesh, Ciaran; Prosser, Patrick; Trimble, James (2020), «The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants», Преобразование графов - 13-я международная конференция, ICGT 2020, проходившая в рамках STAF 2020, Берген, Норвегия, 25-26 июня 2020 г., Труды , Lecture Notes in Computer Science, т. 12150, Springer, стр.  316–324 , doi : 10.1007/978-3-030-51372-6_19 , ISBN 978-3-030-51371-9