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

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

Нерешенная проблема в информатике :

Можно ли решить задачу изоморфизма графов за полиномиальное время?

(еще нерешенные проблемы в информатике)

Проблема изоморфизма графов — это вычислительная задача определения того, являются ли два конечных графа изоморфными . [ ^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]} ${\displaystyle 2^{O((\log n)^{c})}}$ ${\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) получили оценки сложности, аналогичные оценкам для изоморфизма графов.

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

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

• Деревья ^{[20] [21]}
• Планарные графы ^[22] (На самом деле, изоморфизм планарных графов находится в логарифмическом пространстве , ^[23] класс, содержащийся в P )
• Интервальные графики ^[24]
• Графы перестановок ^[25]
• Циркулярные графы ^[26]
• Графики с ограниченными параметрами
  • Графы ограниченной ширины дерева ^[27]
  • Графы ограниченного рода ^[28] (Планарные графы — это графы рода 0.)
  • Графы ограниченной степени ^[29]
  • Графы с ограниченной кратностью собственных значений ^[30]
  • k -Стягиваемые графы (обобщение ограниченной степени и ограниченного рода) ^[31]
  • Сохраняющий цвет изоморфизм цветных графов с ограниченной цветовой кратностью (т.е. не более k вершин имеют одинаковый цвет для фиксированного k ) принадлежит классу NC , который является подклассом P ^[32]

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

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

Как это принято для классов сложности в иерархии полиномиального времени , задача называется GI-трудной , если существует полиномиальное по времени сведение Тьюринга от любой задачи в GI к этой задаче, т. е. полиномиальное по времени решение GI-трудной задачи даст полиномиальное по времени решение проблемы изоморфизма графов (и, следовательно, всех задач в GI ). Задача называется полной для GI , или GI-полной , если она является как GI-трудной, так и полиномиальное по времени решение задачи GI даст полиномиальное по времени решение . ${\displaystyle 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]

• диграфы ^[36]
• помеченные графы , при условии, что изоморфизм не требуется для сохранения меток, ^[36] а требуется только отношение эквивалентности , состоящее из пар вершин с одинаковой меткой
• «поляризованные графы» (состоящие из полного графа K _m и пустого графа K _n плюс некоторые ребра, соединяющие их; их изоморфизм должен сохранять разбиение) ^[36]
• 2- цветные графики ^[36]
• явно заданные конечные структуры ^[36]
• мультиграфы ^[36]
• гиперграфы ^[36]
• конечные автоматы ^[36]
• Марковские процессы принятия решений ^[37]
• Коммутативные нильпотентные полугруппы класса 3 (т.е. xyz = 0 для любых элементов x , y , z ) ^[36]
• Ассоциативные алгебры конечного ранга над фиксированным алгебраически замкнутым полем с нулевым квадратом радикала и коммутативным множителем над радикалом. ^{[36] [38]}
• Контекстно-свободные грамматики ^[36]
• игры в нормальной форме ^[39]
• сбалансированные неполные блочные конструкции ^[36]
• Распознавание комбинаторного изоморфизма выпуклых многогранников, представленных инцидентностями вершин и граней. ^[40]

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

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

• связные графы ^[36]
• графики диаметра 2 и радиуса 1 ^[36]
• направленные ациклические графы ^[36]
• регулярные графы ^[36]
• двудольные графы без нетривиальных сильно регулярных подграфов ^[36]
• Двудольные графы Эйлера ^[36]
• двудольные регулярные графы ^[36]
• линейные графики ^[36]
• расщепленные графики ^[24]
• хордовые графы ^[36]
• Регулярные самодополнительные графы ^[36]
• Политопальные графы общих, простых и симплициальных выпуклых политопов в произвольных размерностях. ^[41]

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

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

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

• Нахождение группы автоморфизмов графа . ^[17]
• Подсчет автоморфизмов графа. ^[17]
• Распознавание самодополнительности графа или орграфа. ^[42]
• Задача о клике для класса так называемых M -графов. Показано, что нахождение изоморфизма для n -вершинных графов эквивалентно нахождению n- клики в M -графе размера n ² . Этот факт интересен, поскольку задача нахождения клики порядка (1 −  ε ) n в M -графе размера n ² является 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 ⁻¹⁰⁰ .

Примечательно, что 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. дои : 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. Матон (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. Бут и Люкер (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. Земляченко, Корнеенко и Тышкевич (1985)
37. Нараянамурти и Равиндран (2008).
38. Григорьев (1981).
39. Габарро, Хоаким; Гарсия, Алина; Серна, Мария (2011). «Сложность игрового изоморфизма». Теоретическая информатика . 412 (48): 6675–6695. дои : 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 , МР  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.