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

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

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

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

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

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

Позволять $G=(V,E)$ , $H=(V^{\prime },E^{\prime })$ быть графиками. Есть ли подграф $G_{0}=(V_{0},E_{0})\mid V_{0}\subseteq V,E_{0}\subseteq E\cap (V_{0}\times V_{0})$ такой, что $G_{0}\cong H$ ? Т. е. существует ли биекция $f\colon V_{0}\rightarrow V^{\prime }$ такой, что $\{\,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 , который необходимо проверить на гамильтоновость, в пару графов и H , где H — цикл, имеющий то же количество вершин, что и G. 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) предложили лучший алгоритм, который улучшает первоначальный порядок вершин с помощью некоторых эвристик.

Современный решатель для сложных экземпляров среднего размера — это решатель подграфов Глазго ( McCreesh, Prosser & Trimble (2020) ). ^[6] Этот решатель использует подход программирования с ограничениями, используя побитово-параллельные структуры данных и специализированные алгоритмы распространения для повышения производительности. Он поддерживает наиболее распространенные варианты задач и способен подсчитывать или перечислять решения, а также решать, существуют ли они.

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

Приложения

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

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

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

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

См. также

Примечания

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

Ссылки

Кук, С.А. (1971), "Сложность процедур доказательства теорем" , Proc. 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 . А1.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, номер документа : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .
Пржуль, Н.; Корней, Д.Г. ; Юрисица, И. (2006), «Эффективная оценка распределения частот графлетов в сетях белок-белкового взаимодействия», Bioinformatics , 22 (8): 974–980, doi : 10.1093/bioinformatics/btl030 , PMID 16452112 .
Снейдерс, TAB; Паттисон, ЧП; Робинс, Г.; Хэндкок, М.С. (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 .
Ullmann, Julian R. (2010), «Алгоритмы битовых векторов для удовлетворения бинарных ограничений и изоморфизма подграфа», экспериментальных алгоритмиков , 15 : 1,1, Citeseerx 10.1.1.681.8766 , DOI : 10.1145/1671970.1921702 , S21184 Журнал .
Корделла, Луиджи П. (2004), «Алгоритм изоморфизма (суб)графов для сопоставления больших графов», IEEE Transactions on Pattern Analysis and Machine Intelligence , 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 Transactions on Pattern Analysis and Machine Intelligence , 40 (4): 804–818, doi : 10.1109/TPAMI. 2017.2696940 , PMID 28436848 , S2CID 3709576
Солнон, Кристина (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
МакКриш, Кьяран; Проссер, Патрик; Тримбл, Джеймс (2020), «Решатель подграфов Глазго: использование программирования с ограничениями для решения сложных вариантов изоморфизма подграфов», Трансформация графов - 13-я международная конференция, ICGT 2020, проходившая в рамках STAF 2020, Берген, Норвегия, 25-26 июня , 2020, Труды , Конспект лекций по информатике, вып. 12150, Springer, стр. 316–324, номер doi : 10.1007/978-3-030-51372-6_19 , ISBN. 978-3-030-51371-9

[1] В оригинальной статье Кука (1971) , доказывающей теорему Кука – Левина , уже было показано, что изоморфизм подграфов NP-полный, с использованием сокращения из 3-SAT с участием клик.

[e99-2] Перейти обратно: ^а ^б Эппштейн (1999) ; Спаринг и Оссона де Мендес (2012)

[3] Вегенер, Инго (2005), Теория сложности: исследование пределов эффективных алгоритмов , Springer, стр. 81, ISBN 9783540210450 .

[4] де ла Игера, Колин; Жаноде, Жан-Кристоф; Сэмюэл, Эмили; Дамиан, Гийом; Солнон, Кристина (2013), «Полиномиальные алгоритмы для изоморфизмов открытых плоских графов и подграфов» (PDF) , Theoretical Computer Science , 498 : 76–99, doi : 10.1016/j.tcs.2013.05.026 , MR 3083515 , Известно с середины 70-х годов стало известно, что проблема изоморфизма разрешима за полиномиальное время для плоских графов. Однако также было отмечено, что проблема субизоморфизма по-прежнему является N P-полной, в частности потому, что проблема гамильтонова цикла является NP-полной для плоских графов.

[5] Здесь Ω использует нотацию Большой Омеги .

[6] Экспериментальную оценку см. Solnon (2019) .

[7] Ульманн (1976)

[8] Курамочи и Карипис (2001) .

[9] Пржуль, Корнейл и Юришица (2006) .

[10] Снейдерс и др. (2006) .

[11] ttp://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf ; расширенная версия: https://e-reports-ext.llnl.gov/pdf/332302.pdf.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]