Проблема изоморфизма графов
Нерешенная проблема в теории сложности вычислений

Нерешенная проблема в информатике :
Можно ли решить задачу изоморфизма графов за полиномиальное время?
(еще нерешенные проблемы в информатике)

Проблема изоморфизма графов — это вычислительная задача определения того, являются ли два конечных графа изоморфными . [ 1]

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

Эта задача является частным случаем задачи изоморфизма подграфов [ 5] , которая спрашивает, содержит ли заданный граф G подграф, изоморфный другому заданному графу H ; известно, что эта задача является NP-полной. Известно также, что она является частным случаем задачи неабелевой скрытой подгруппы над симметрической группой [6] .

В области распознавания изображений это известно как точное сопоставление графов. [7]

Уровень развития

В ноябре 2015 года Ласло Бабай объявил о квазиполиномиальном алгоритме для всех графов, то есть о алгоритме со временем выполнения для некоторого фиксированного . [8] [9] [10] [11] 4 января 2017 года Бабай отказался от квазиполиномиального утверждения и вместо этого заявил о субэкспоненциальной временной границе после того, как Харальд Хельфготт обнаружил ошибку в доказательстве. 9 января 2017 года Бабай объявил об исправлении (опубликованном полностью 19 января) и восстановил квазиполиномиальное утверждение, а Хельфготт подтвердил исправление. [12] [13] Хельфготт далее утверждает, что можно взять c = 3 , поэтому время выполнения равно 2 O((log n ) 3 ) . [14] [15] 2 О ( ( бревно ⁡ н ) с ) {\displaystyle 2^{O((\log n)^{c})}} с > 0 {\displaystyle c>0}

До этого наилучшим принятым теоретическим алгоритмом был алгоритм Бабая и Люкса (1983), основанный на более ранней работе Люкса (1982) в сочетании с субфакторным алгоритмом В. Н. Земляченко (Земляченко, Корнеенко и Тышкевич 1985). Алгоритм имеет время выполнения 2 O( √ n  log  n ) для графов с n вершинами и опирается на классификацию конечных простых групп . Без этой теоремы классификации немного более слабая граница 2 O( √ n  log 2  n ) была получена сначала для сильно регулярных графов Ласло Бабаем (  1980), а затем распространена на общие графы Бабаем и Люксом (1983). Улучшение показателя √ n для сильно регулярных графов было сделано Шпильманом (1996). Для гиперграфов ограниченного ранга субэкспоненциальная верхняя граница, соответствующая случаю графов, была получена Бабаем и Коденотти (2008).

Существует несколько конкурирующих практических алгоритмов для изоморфизма графов, например, те, что были предложены Маккеем (1981), Шмидтом и Дрюффелем (1976), Ульманом (1976) и Стойчевым (2019). Хотя они, по-видимому, хорошо работают на случайных графах , основным недостатком этих алгоритмов является их экспоненциальная производительность в худшем случае . [16]

Проблема изоморфизма графов вычислительно эквивалентна проблеме вычисления группы автоморфизмов графа, [17] [18] [19] и слабее, чем проблема изоморфизма группы перестановок и проблема пересечения группы перестановок. Для последних двух проблем Бабай, Кантор и Люкс (1983) получили оценки сложности, аналогичные оценкам для изоморфизма графов.

Решенные особые случаи

Ряд важных частных случаев проблемы изоморфизма графов имеют эффективные решения за полиномиальное время:

Класс сложности GI

Поскольку проблема изоморфизма графов не известна ни как NP-полная, ни как разрешимая, исследователи попытались проникнуть в суть проблемы, определив новый класс GI , множество проблем с полиномиальным временем сведения по Тьюрингу к проблеме изоморфизма графов. [33] Если бы проблема изоморфизма графов действительно была разрешима за полиномиальное время, GI было бы равно P. С другой стороны, если проблема является NP-полной, GI было бы равно NP , и все проблемы из NP были бы разрешимы за квазиполиномиальное время.

Как это принято для классов сложности в иерархии полиномиального времени , задача называется GI-трудной , если существует полиномиальное по времени сведение Тьюринга от любой задачи в GI к этой задаче, т. е. полиномиальное по времени решение GI-трудной задачи даст полиномиальное по времени решение проблемы изоморфизма графов (и, следовательно, всех задач в GI ). Задача называется полной для GI , или GI-полной , если она является как GI-трудной, так и полиномиальное по времени решение задачи GI даст полиномиальное по времени решение . X {\displaystyle X} X {\displaystyle X}

Проблема изоморфизма графов содержится как в NP , так и в co- AM . GI содержится в и low для Parity P , а также содержится в потенциально гораздо меньшем классе SPP . [34] То, что он лежит в Parity P, означает, что проблема изоморфизма графов не сложнее, чем определение того, имеет ли недетерминированная машина Тьюринга с полиномиальным временем четное или нечетное количество принимающих путей. GI также содержится в и low для ZPP NP . [35] Это по сути означает, что эффективный алгоритм Лас-Вегаса с доступом к оракулу NP может решить изоморфизм графов настолько легко, что он не получает никакой мощности от предоставления ему возможности делать это за постоянное время.

Проблемы GI-complete и GI-hard

Изоморфизм других объектов

Существует ряд классов математических объектов, для которых проблема изоморфизма является GI-полной проблемой. Некоторые из них представляют собой графы, наделенные дополнительными свойствами или ограничениями: [36]

GI-полные классы графов

Класс графов называется GI-полным, если распознавание изоморфизма для графов из этого подкласса является GI-полной задачей. Следующие классы являются GI-полными: [36]

Многие классы орграфов также являются GI-полными.

Другие проблемы с ЖКТ

Помимо проблем изоморфизма существуют и другие нетривиальные GI-полные проблемы.

  • Нахождение группы автоморфизмов графа . [17]
  • Подсчет автоморфизмов графа. [17]
  • Распознавание самодополнительности графа или орграфа. [42]
  • Задача о клике для класса так называемых M -графов. Показано, что нахождение изоморфизма для n -вершинных графов эквивалентно нахождению n- клики в M -графе размера n 2 . Этот факт интересен, поскольку задача нахождения клики порядка (1 −  ε ) n в M -графе размера n 2 является NP-полной для произвольно малого положительного ε. [43]
  • Проблема гомеоморфизма 2-комплексов. [44]
  • Проблема определимости для логики первого порядка. Входные данные этой проблемы — экземпляр реляционной базы данных I и отношение R , а вопрос, на который нужно ответить, — существует ли запрос первого порядка Q (без констант) такой, что Q, оцененный на I, дает R в качестве ответа. [45]

Проблемы с ЖКТ

  • Задача подсчета числа изоморфизмов между двумя графами по полиномиальному времени эквивалентна задаче определения, существует ли хотя бы один из них. [46]
  • Проблема решения вопроса, являются ли два выпуклых многогранника, заданных либо V-описанием , либо H-описанием, проективно или аффинно изоморфными. Последнее означает существование проективного или аффинного отображения между пространствами, содержащими два многогранника (не обязательно одинаковой размерности), которое индуцирует биекцию между многогранниками. [41]

Проверка программы

Мануэль Блюм и Сампат Каннан (1995) продемонстрировали вероятностный проверяющий инструмент для программ на изоморфизм графов. Предположим, что P — это заявленная процедура полиномиального времени, которая проверяет, являются ли два графа изоморфными, но она не является доверенной. Чтобы проверить, являются ли графы G и H изоморфными:

  • Спросите P, изоморфны ли G и H.
    • Если ответ «да»:
      • Попытайтесь построить изоморфизм, используя P как подпрограмму. Отметьте вершину u в G и v в H и измените графы, чтобы сделать их отличительными (с небольшим локальным изменением). Спросите P , являются ли измененные графы изоморфными. Если нет, измените v на другую вершину. Продолжайте поиск.
      • Либо изоморфизм будет найден (и его можно будет проверить), либо P будет противоречить самому себе.
    • Если ответ «нет»:
      • Выполните следующее 100 раз. Выберите случайным образом G или H и случайным образом переставьте его вершины. Спросите P , изоморфен ли граф G и H. (Как в протоколе AM для неизоморфизма графа).
      • Если какой-либо из тестов не пройден, оцените P как недействительную программу. В противном случае ответьте «нет».

Эта процедура выполняется за полиномиальное время и дает правильный ответ, если P является правильной программой для изоморфизма графов. Если P не является правильной программой, но отвечает правильно на G и H , проверяющий либо даст правильный ответ, либо обнаружит недопустимое поведение P. Если P не является правильной программой и отвечает неправильно на G и H , проверяющий с высокой вероятностью обнаружит недопустимое поведение P или даст неправильный ответ с вероятностью 2 −100 .

Примечательно, что P используется только как черный ящик.

Приложения

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

В хеминформатике и математической химии тестирование изоморфизма графов используется для идентификации химического соединения в химической базе данных . [48] Кроме того, в органической математической химии тестирование изоморфизма графов полезно для генерации молекулярных графов и для компьютерного синтеза .

Поиск в химической базе данных является примером графического интеллектуального анализа данных , где часто используется подход канонизации графа . [49] В частности, ряд идентификаторов химических веществ , таких как SMILES и InChI , разработанных для предоставления стандартного и понятного человеку способа кодирования молекулярной информации и облегчения поиска такой информации в базах данных и в Интернете, используют шаг канонизации в своих вычислениях, который по сути является канонизацией графа, представляющего молекулу.

В автоматизации электронного проектирования изоморфизм графов является основой этапа проектирования схем Layout Versus Schematic (LVS), который заключается в проверке того, являются ли электрические цепи, представленные принципиальной схемой и компоновкой интегральной схемы , одинаковыми. [50]

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

Примечания

  1. ^ Коблер, Йоханнес; Шёнинг, Уве; Торан, Якобо (2012). Проблема изоморфизма графов: ее структурная сложность . Springer Science & Business Media. стр. 1.
  2. ^ Шёнинг (1987).
  3. ^ Бабай, Ласло; Эрдеш, Пол; Селков, Стэнли М. (1 августа 1980 г.). «Случайный изоморфизм графов». SIAM Journal по вычислительной технике . 9 (3): 628–635 . doi : 10.1137/0209047. ISSN  0097-5397.
  4. ^ Маккей (1981).
  5. ^ Ульман (1976).
  6. ^ Мур, Рассел и Шульман (2008).
  7. ^ Эндика Бенгоэчеа, «Неточное сопоставление графов с использованием оценки алгоритмов распределения», докторская диссертация, 2002 г., Глава 2: Проблема сопоставления графов (получено 28 июня 2017 г.)
  8. ^ "Математик заявляет о прорыве в теории сложности". Science . 10 ноября 2015 г.
  9. ^ Бабай (2015)
  10. ^ Видео первой лекции 2015 года, ссылка на которую находится на домашней странице Бабая
  11. ^ "Проблема изоморфизма графов". Сообщения ACM . Ноябрь 2020 г. Получено 4 мая 2021 г.
  12. ^ Бабай, Ласло (9 января 2017 г.), Обновление изоморфизма графов
  13. ^ Эрика Кларрайх (14 января 2017 г.). «Изоморфизм графов побеждён — снова». Журнал Quanta .
  14. ^ Хелфготт, Харальд (16 января 2017 г.), Изоморфизмы графов в квазиполиномиальных временных интервалах (d'après Babai et Luks, Weisfeiler-Leman...) , arXiv : 1701.04372 , Bibcode : 2017arXiv170104372A
  15. ^ Дона, Даниэль; Баджпай, Джитендра; Хельфготт, Харальд Андрес (12 октября 2017 г.). «Изоморфизмы графов за квазиполиномиальное время». arXiv : 1710.04574 [math.GR].
  16. ^ Фоджа, Сансоне и Венто (2001).
  17. ^ abc Матон (1979).
  18. ^ Luks, Eugene (1993-09-01). "Группы перестановок и вычисления за полиномиальное время". Серия DIMACS по дискретной математике и теоретической информатике . Том 11. Провиденс, Род-Айленд: Американское математическое общество. стр.  139–175 . doi :10.1090/dimacs/011/11. ISBN 978-0-8218-6599-6. ISSN  1052-1798.
  19. ^ Algeboy (https://cs.stackexchange.com/users/90177/algeboy), Изоморфизм графов и группа автоморфизмов, URL (версия: 2018-09-20): https://cs.stackexchange.com/q/97575
  20. ^ Келли (1957).
  21. ^ Ахо, Хопкрофт и Уллман (1974), стр. 84-86.
  22. ^ Хопкрофт и Вонг (1974).
  23. ^ Датта и др. (2009).
  24. ^ ab Бут и Люкер (1979).
  25. ^ Колборн (1981).
  26. ^ Музычук (2004).
  27. ^ Бодлендер (1990).
  28. ^ Миллер 1980; Филотти и Майер 1980.
  29. ^ Люкс (1982).
  30. ^ Бабай, Григорьев и Маунт (1982).
  31. ^ Миллер (1983).
  32. ^ Люкс (1986).
  33. ^ Бут и Колборн 1977; Кёблер, Шёнинг и Торан 1993.
  34. ^ Кёблер, Шёнинг и Торан 1992; Арвинд и Курур 2006 г.
  35. ^ Арвинд и Кёблер (2000).
  36. ^ abcdefghijklmnopqrstu vwx Земляченко, Корнеенко и Тышкевич (1985)
  37. ^ Нараянамурти и Равиндран (2008).
  38. ^ Григорьев (1981).
  39. ^ Габарро, Хоаким; Гарсия, Алина; Серна, Мария (2011). «Сложность игрового изоморфизма». Теоретическая информатика . 412 (48): 6675–6695 . doi :10.1016/j.tcs.2011.07.022. hdl : 2117/91166 .
  40. ^ Джонсон (2005); Кайбель и Шварц (2003).
  41. ^ аб Кайбель и Шварц (2003).
  42. ^ Колборн и Колборн (1978).
  43. ^ Козен (1978).
  44. ^ Шоу-Тейлор и Пизански (1994).
  45. ^ Аренас и Диас (2016).
  46. ^ Матон (1979); Джонсон 2005.
  47. ^ Эндика Бенгоэчеа, доктор философии, Аннотация
  48. ^ Ирнигер (2005).
  49. ^ Кук и Холдер (2007).
  50. ^ Бэрд и Чо (1975).

Ссылки

  • Ахо, Альфред В.; Хопкрофт , Джон ; Ульман, Джеффри Д. (1974), Проектирование и анализ компьютерных алгоритмов , Рединг, Массачусетс: Addison-Wesley.
  • Арвинд, Викраман; Кёблер, Йоханнес (2000), «Изоморфизм графов низок для ZPP(NP) и других результатов с низкими значениями». Труды 17-го ежегодного симпозиума по теоретическим аспектам компьютерной науки, Lecture Notes in Computer Science , т. 1770, Springer-Verlag, стр. 431–442, doi :10.1007/3-540-46541-3_36, ISBN 3-540-67141-2, г-н  1781752.
  • Арвинд, Викраман; Курур, Пиюш П. (2006), «Изоморфизм графов в SPP», Информация и вычисления , 204 (5): 835–852 , doi : 10.1016/j.ic.2006.02.002 , MR  2226371.
  • Аренас, Марсело; Диас, Гонсало И. (2016), «Точная сложность проблемы определимости логики первого порядка», ACM Transactions on Database Systems , 41 (2): 13:1–13:14, doi :10.1145/2886095.
  • Бабай, Ласло (1980), «О сложности канонической разметки сильно регулярных графов», SIAM Journal on Computing , 9 (1): 212– 216, doi :10.1137/0209018, MR  0557839.
  • Бабай, Ласло ; Коденотти, Паоло (2008), «Изоморфизм гиперграфов низкого ранга за умеренно экспоненциальное время» (PDF) , Труды 49-го ежегодного симпозиума IEEE по основам компьютерной науки (FOCS 2008) , IEEE Computer Society, стр.  667–676 , doi :10.1109/FOCS.2008.80, ISBN 978-0-7695-3436-7, S2CID  14025744.
  • Бабай, Ласло ; Григорьев, Д. Ю.; Маунт , Дэвид М. (1982), «Изоморфизм графов с ограниченной кратностью собственных значений», Труды 14-го ежегодного симпозиума ACM по теории вычислений , стр.  310–324 , doi :10.1145/800070.802206, ISBN 0-89791-070-2, S2CID  12837287.
  • Бабай, Ласло ; Кантор, Уильям ; Люкс, Юджин (1983), «Вычислительная сложность и классификация конечных простых групп», Труды 24-го ежегодного симпозиума по основам компьютерной науки (FOCS) , стр.  162–171 , doi :10.1109/SFCS.1983.10, ISBN 0-8186-0508-1, S2CID  6670135.
  • Бабай, Ласло ; Люкс, Юджин М. (1983), «Каноническая маркировка графов», Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '83) , стр.  171–183 , doi : 10.1145/800061.808746 , ISBN 0-89791-099-0, S2CID  12572142.
  • Бабай, Ласло (2015), Изоморфизм графов за квазиполиномиальное время , arXiv : 1512.03547 , Bibcode : 2015arXiv151203547B
  • Бэрд, Х.С.; Чо, Й.Е. (1975), «Система проверки дизайна художественных произведений», Труды 12-й конференции по автоматизации проектирования (DAC '75) , Пискатауэй, Нью-Джерси, США: IEEE Press, стр.  414–420.
  • Блум, Мануэль ; Каннан, Сампат (1995), «Проектирование программ, проверяющих свою работу», Журнал ACM , 42 (1): 269–291 , CiteSeerX  10.1.1.38.2537 , doi :10.1145/200836.200880, S2CID  52151779.
  • Бодлендер, Ганс (1990), «Полиномиальные алгоритмы для изоморфизма графов и хроматического индекса на частичных k -деревьях», Журнал алгоритмов , 11 (4): 631– 643, doi :10.1016/0196-6774(90)90013-5, MR  1079454.
  • Бут, Келлогг С.; Колборн, К.Дж. (1977), Проблемы, полиномиально эквивалентные изоморфизму графов , Технический отчет, т. CS-77-04, Кафедра компьютерных наук, Университет Ватерлоо.
  • Бут, Келлогг С.; Люкер, Джордж С. (1979), «Линейный алгоритм времени для определения изоморфизма интервальных графов», Журнал ACM , 26 (2): 183–195 , doi : 10.1145/322123.322125 , MR  0528025, S2CID  18859101.
  • Буше, К.; Локер, Д. (2006), Полнота изоморфизма графов для совершенных графов и подклассов совершенных графов (PDF) , Технический отчет, т. CS-2006-32, Кафедра компьютерных наук, Университет Ватерлоо.
  • Чунг, Фань Р.К. (1985), «О ширине разреза и топологической пропускной способности дерева», Журнал SIAM по алгебраическим и дискретным методам , 6 (2): 268– 277, doi :10.1137/0606026, MR  0778007.
  • Колборн, CJ (1981), «О проверке изоморфизма графов перестановок», Networks , 11 : 13–21 , doi :10.1002/net.3230110103, MR  0608916.
  • Колборн, Марлен Джонс; Колборн, Чарльз Дж. (1978), «Изоморфизм графов и самодополнительные графы», ACM SIGACT News , 10 (1): 25–29 , doi :10.1145/1008605.1008608, S2CID  35157300.
  • Кук, Дайан Дж.; Холдер, Лоуренс Б. (2007), «Раздел 6.2.1: Каноническая маркировка», Mining Graph Data , Wiley, стр.  120–122 , ISBN 978-0-470-07303-2.
  • Датта, С.; Лимайе, Н.; Нимборкар, П.; Тиерауф, Т.; Вагнер, Ф. (2009), «Изоморфизм планарных графов находится в логарифмическом пространстве», 24-я ежегодная конференция IEEE по вычислительной сложности , 2009 г., стр. 203, arXiv : 0809.2319 , doi : 10.1109/CCC.2009.16, ISBN 978-0-7695-3717-7, S2CID  14836820.
  • Филотти, И. С.; Майер, Джек Н. (1980), «Алгоритм полиномиального времени для определения изоморфизма графов фиксированного рода», Труды 12-го ежегодного симпозиума ACM по теории вычислений, стр.  236–243 , doi :10.1145/800141.804671, ISBN 0-89791-017-6, S2CID  16345164.
  • Foggia, P.; Sansone, C.; Vento, M. (2001), "Сравнение производительности пяти алгоритмов для изоморфизма графов" (PDF) , Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition , стр.  188–199 , архивировано из оригинала (PDF) 24.09.2015 , извлечено 18.12.2009.
  • Гэри, Майкл Р.; Джонсон , Дэвид С. (1979), Компьютеры и неразрешимость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5.
  • Григорьев, Д.Ю. (1981), "Сложность "диких" матричных задач и изоморфизма алгебр и графов", Записки научных семинаров Ленинградского отделения математического института имени В.А. Стеклова Академии наук СССР (ЛОМИ) , 105 : 10–17 , 198, MR  0628981Английский перевод в Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
  • Хопкрофт, Джон ; Вонг, Дж. (1974), «Линейный алгоритм для изоморфизма планарных графов», Труды шестого ежегодного симпозиума ACM по теории вычислений , стр.  172–184 , doi :10.1145/800119.803896, S2CID  15561884.
  • Ирнигер, Кристоф-Андре Марио (2005), Сопоставление графов: фильтрация баз данных графов с использованием машинного обучения , Dissertationen zur künstlichen Intelligenz, vol. 293, АКА, ISBN 1-58603-557-6.
  • Kaibel, Volker; Schwartz, Alexander (2003), "О сложности проблем изоморфизма многогранников", Graphs and Combinatorics , 19 (2): 215– 230, arXiv : math/0106093 , doi :10.1007/s00373-002-0503-y, MR  1996205, S2CID  179936, архивировано из оригинала 21 июля 2015 г..
  • Келли, Пол Дж. (1957), «Теорема сравнения для деревьев», Pacific Journal of Mathematics , 7 : 961–968 , doi : 10.2140/pjm.1957.7.961 , MR  0087949.
  • Кёблер, Йоханнес; Шёнинг, Уве ; Торан, Якобо (1992), «Изоморфизм графов низок для PP», Computational Complexity , 2 (4): 301– 330, doi :10.1007/BF01200427, MR  1215315, S2CID  8542603.
  • Козен, Декстер (1978), «Проблема клики, эквивалентная изоморфизму графов», ACM SIGACT News , 10 (2): 50–52 , doi : 10.1145/990524.990529 , S2CID  52835766.
  • Люкс, Юджин М. (1982), «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время», Журнал компьютерных и системных наук , 25 : 42– 65, doi : 10.1016/0022-0000(82)90009-5 , MR  0685360, S2CID  2572728.
  • Люкс, Юджин М. (1986), «Параллельные алгоритмы для групп перестановок и изоморфизма графов», Труды симпозиума IEEE по основам компьютерной науки , стр.  292–302.
  • Матон, Рудольф (1979), «Заметка о проблеме подсчета изоморфизма графов», Information Processing Letters , 8 (3): 131– 132, doi :10.1016/0020-0190(79)90004-8, MR  0526453.
  • Маккей, Брендан Д. (1981), «Практический изоморфизм графов», 10-я Манитобская конференция по численной математике и вычислениям (Виннипег, 1980) , Congressus Numerantium, т. 30, стр.  45–87 , MR  0635936.
  • Миллер, Гэри (1980), «Проверка изоморфизма графов ограниченного рода», Труды 12-го ежегодного симпозиума ACM по теории вычислений , стр.  225–235 , doi : 10.1145/800141.804670 , ISBN 0-89791-017-6, S2CID  13647304.
  • Миллер, Гэри Л. (1983), «Проверка изоморфизма и канонические формы для k -стягиваемых графов (обобщение ограниченной валентности и ограниченного рода)», Труды Международной конференции по основам компьютерной теории , Конспект лекций по информатике , том 158, стр.  310–327 , doi :10.1007/3-540-12689-9_114, ISBN 978-3-540-12689-8. Полная статья в журнале Information and Control 56 (1–2): 1–20, 1983.
  • Мур, Кристофер ; Рассел, Александр; Шульман, Леонард Дж. (2008), «Симметричная группа не поддается строгой выборке Фурье», SIAM Journal on Computing , 37 (6): 1842– 1864, arXiv : quant-ph/0501056 , doi : 10.1137/050644896, MR  2386215, S2CID  9550284.
  • Музычук, Михаил (2004), "Решение проблемы изоморфизма для циркулянтных графов", Proc. London Math. Soc. , 88 : 1– 41, doi :10.1112/s0024611503014412, MR  2018956, S2CID  16704931.
  • Нараянамурти, SM; Равиндран , B. (2008), «О сложности поиска симметрий в марковских процессах принятия решений» (PDF) , Труды Двадцать пятой Международной конференции по машинному обучению (ICML 2008) , стр.  688–696.
  • Шмидт, Дуглас К.; Дрюффель, Ларри Э. (1976), «Быстрый алгоритм обратного отслеживания для проверки направленных графов на изоморфизм с использованием матриц расстояний», Журнал ACM , 23 (3): 433– 445, doi : 10.1145/321958.321963 , MR  0411230, S2CID  6163956.
  • Шёнинг, Уве (1987), «Изоморфизм графов в низкой иерархии», Труды 4-го ежегодного симпозиума по теоретическим аспектам компьютерной науки , стр.  114–124; также Журнал компьютерных и системных наук 37 : 312–323, 1988.
  • Шоу-Тейлор, Джон; Писански, Томаж (1994), «Гомеоморфизм 2-комплексов является полным изоморфизмом графов», SIAM Journal on Computing , 23 (1): 120– 132, doi :10.1137/S0097539791198900, MR  1258998.
  • Шпильман, Дэниел А. (1996), «Быстрая проверка изоморфизма строго регулярных графов», Труды Двадцать восьмого ежегодного симпозиума ACM по теории вычислений (STOC '96) , ACM, стр.  576–584 , ISBN 978-0-89791-785-8.
  • Ульман, Джулиан Р. (1976), «Алгоритм изоморфизма подграфов» (PDF) , Журнал ACM , 23 : 31–42 , CiteSeerX  10.1.1.361.7741 , doi :10.1145/321921.321925, MR  0495173, S2CID  17268751.

Обзоры и монографии

  • Рид, Рональд К.; Корнейл, Дерек Г. (1977), «Болезнь изоморфизма графов», Журнал теории графов , 1 (4): 339–363 , doi :10.1002/jgt.3190010410, MR  0485586, S2CID  26589776.
  • Гати, Г. (1979), «Дополнительная аннотированная библиография по болезни изоморфизма», Журнал теории графов , 3 (2): 95–109 , doi :10.1002/jgt.3190030202.
  • Земляченко, В. Н.; Корнеенко, Н. М.; Тышкевич, РИ (1985), "Проблема изоморфизма графов", Журнал математических наук , 29 (4): 1426– 1481, doi : 10.1007/BF02104746 , S2CID  121818465. (Перевод из «Записок научных семинаров Ленинградского отделения Математического института им . В.А. Стеклова АН СССР », т. 118, с. 83–158, 1982.)
  • Арвинд, В.; Торан, Якобо (2005), «Тестирование изоморфизма: перспективы и открытые проблемы» ( PDF) , Бюллетень Европейской ассоциации теоретической информатики , 86 : 66–84. (Краткий обзор открытых вопросов, связанных с проблемой изоморфизма графов, колец и групп.)
  • Кёблер, Йоханнес; Шенинг, Уве ; Торан, Хакобо (1993), Проблема изоморфизма графов: ее структурная сложность , Биркхойзер, ISBN 978-0-8176-3680-7. ( С обложки книги : Книга фокусируется на вопросе вычислительной сложности задачи и представляет несколько последних результатов, которые дают лучшее понимание относительного положения задачи в классе NP, а также в других классах сложности.)
  • Джонсон, Дэвид С. (2005), «Столбец NP-полноты», ACM Transactions on Algorithms , 1 (1): 160– 176, doi :10.1145/1077464.1077476, S2CID  12604799(В этом 24-м выпуске колонки обсуждается современное состояние открытых проблем из книги «Компьютеры и неразрешимость» и предыдущих колонок, в частности, по изоморфизму графов.)
  • Торан, Якобо; Вагнер, Фабиан (2009), «Сложность изоморфизма планарных графов» (PDF) , Бюллетень Европейской ассоциации теоретической информатики , 97 , архивировано из оригинала (PDF) 20-09-2010 , извлечено 03-06-2010.
  • Стойчев, Стойчо Д. (2019), «Новые точные и эвристические алгоритмы для группы автоморфизмов графов и изоморфизма графов», Журнал экспериментальной алгоритмики , 24 : 1– 27, doi : 10.1145/3333250, S2CID  202676274.

Программное обеспечение

  • Изоморфизм графов, обзор реализаций, The Stony Brook Algorithm Repository.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Graph_isomorphism_problem&oldid=1268227111#Complexity_class_GI"