Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

Альтернатива сокращение от гамильтонова цикла задачи переводит график G , который должен быть проверен на гамильтоновость в пару графов G и 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]

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

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

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

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

Приложения [ править ]

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

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

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

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

См. Также [ править ]

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

Примечания [ править ]

  1. ^ В оригинальнойстатье Кука (1971) , в которой доказана теорема Кука – Левина, уже показано, что изоморфизм подграфов является NP-полным, с использованием редукции из 3-SAT с участием клик.
  2. ^ а б Эппштейн (1999) ; Нешетржил и Оссона де Мендес (2012)
  3. ^ Вегенер, Инго (2005), Теория сложности: изучение пределов эффективных алгоритмов , Springer, стр. 81, ISBN 9783540210450.
  4. ^ де ла Игера, Колин; Жаноде, Жан-Кристоф; Самуэль, Эмили; Дамианд, Гийом; Solnon, Christine (2013), "полиномиальные алгоритмы для открытой плоских графов и подграфа изоморфизмов" (PDF) , теоретическая информатика , 498 : 76-99, DOI : 10.1016 / j.tcs.2013.05.026 , MR 3083515 , известен с середины 70-х годов проблема изоморфизма разрешима за полиномиальное время для плоских графов. Однако также было отмечено, что проблема субизоморфизма все еще является N P-полной, в частности, потому, что проблема гамильтонова цикла является NP-полной для плоских графов.  
  5. ^ Здесь Ω использует обозначение Большой Омеги .
  6. ^ Ульманн (1976)
  7. ^ Kuramochi & Karypis (2001) .
  8. ^ Pržulj, Corneil & Jurisica (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

Ссылки [ править ]

  • Cook, SA (1971), "Сложность процедур доказательства теорем" , Proc. Третий ACM симпозиум по теории вычислений ., Стр 151-158, DOI : 10,1145 / 800157,805047.
  • Эппштейн, Дэвид (1999), «Изоморфизм подграфов в плоских графах и связанные проблемы» (PDF) , Журнал алгоритмов и приложений графов , 3 (3): 1–27, arXiv : cs.DS / 9911003 , doi : 10.7155 / jgaa .00014.
  • Гарей, Майкл Р .; Джонсон, Дэвид С. (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
  • Курамоти, Мичихиро; Карипис, Джордж (2001), «Частое обнаружение подграфов», 1-я Международная конференция IEEE по интеллектуальному анализу данных , стр. 313, CiteSeerX  10.1.1.22.4992 , DOI : 10,1109 / ICDM.2001.989534 , ISBN 978-0-7695-1119-1.
  • Ольрих, Майлз; Эбелинг, Карл; Джинтинг, Эка; Sather, Лиза (1993), «SubGemini: определение подсхемы , используя быстрый алгоритм подграфа изоморфизма», Труды 30 - я международной конференцию Design Automation , стр 31-37,. Дои : 10,1145 / 157485,164556 , ISBN 978-0-89791-577-9.
  • Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «18.3 Проблема изоморфизма подграфов и булевы запросы», разреженность: графы, структуры и алгоритмы , алгоритмы и комбинаторика, 28 , Springer, стр. 400–401, doi : 10.1007 / 978-3 -642-27875-4 , ISBN 978-3-642-27874-7, MR  2920058.
  • Pržulj, N .; Corneil, DG ; Юрисица, И. (2006), "Эффективная оценка частотных распределений графлетов в сетях белок-белковых взаимодействий", Биоинформатика , 22 (8): 974–980, DOI : 10.1093 / биоинформатика / btl030 , PMID  16452112.
  • Snijders, TAB; Паттисон, ЧП; Робинс, G .; Handcock, MS (2006), "Новые спецификации для моделей экспоненциального случайных графов", социологическая методология , 36 (1): 99-153, CiteSeerX  10.1.1.62.7975 , DOI : 10.1111 / j.1467-9531.2006.00176.x.
  • Ульман, Джулиан Р. (1976), "Алгоритм подграфа изоморфизма", Журнал ACM , 23 (1): 31-42, DOI : 10,1145 / 321921,321925.
  • Джамил, Хасан (2011), «Вычисление изоморфных запросов к подграфам с использованием структурной унификации и минимальных графовых структур», 26-й симпозиум ACM по прикладным вычислениям , стр. 1058–1063.
  • Ульманн, Джулиан Р. (2010), «Битовые векторные алгоритмы для удовлетворения двоичных ограничений и изоморфизма подграфов», Журнал экспериментальной алгоритмики , 15 : 1.1, CiteSeerX  10.1.1.681.8766 , doi : 10.1145 / 1671970.1921702.
  • Корделла, Луиджи П. (2004), «Алгоритм изоморфизма (под) графов для сопоставления больших графов», IEEE Transactions on Pattern Analysis and Machine Intelligence , 26 (10): 1367–1372, CiteSeerX  10.1.1.101.5342 , doi : 10.1109 / тпами.2004.75 , PMID  15641723
  • Bonnici, V .; Giugno, Р. (2013), "Подграф изоморфизм алгоритм и его применение в биохимические данные", BMC биоинформатика , 14 (Suppl7) (13): S13, DOI : 10,1186 / 1471-2105-14-s7-S13 , ПКА  3633016 , PMID  23815292
  • Карлетти, В .; Foggia, P .; Saggese, A .; Венто, М. (2018), «Проблема временной сложности изоморфизма точных подграфов для огромных и плотных графов с помощью VF3», IEEE Transactions on Pattern Analysis and Machine Intelligence , 40 (4): 804–818, doi : 10.1109 / TPAMI. 2017.2696940