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

Нерешенная задача в информатике :

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

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

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

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

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

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

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

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

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

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

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

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

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

• Деревья
• Планарные графы (На самом деле изоморфизм планарных графов находится в лог-пространстве , класс, содержащийся в P )
• Интервальные графики
• Графы перестановок
• Циркулянтные графики
• Графы ограниченных параметров
  • Графики ограниченной ширины дерева
  • Графы ограниченного рода (Плоские графы — это графы рода 0.)
  • Графы ограниченной степени
  • Графы с ограниченной собственных значений кратностью
  • k -сжимаемые графы (обобщение ограниченной степени и ограниченного рода)
  • Сохраняющий цвет изоморфизм цветных графов с ограниченной кратностью цветов (т. е. не более k вершин имеют один и тот же цвет при фиксированном k ) находится в классе NC , который является подклассом P

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

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

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

Проблема изоморфизма графов содержится как в NP , так и в co- AM . GI содержится в и низком уровне для Parity P , а также содержится в потенциально гораздо меньшем классе SPP . То, что он находится в четности P, означает, что проблема изоморфизма графов не сложнее, чем определение того, имеет ли недетерминированная машина Тьюринга с полиномиальным временем четное или нечетное количество принимающих путей. GI также содержится в ZPP и является низким ^{НАПРИМЕР} . По сути, это означает, что эффективный алгоритм Лас-Вегаса с доступом к NP -оракулу может решать изоморфизм графов настолько легко, что он не получает никакой пользы от возможности делать это за постоянное время.

GI-полные и GI-сложные задачи

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

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

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

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

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

• связные графы
• графики диаметра 2 и радиуса 1
• ориентированные ациклические графы
• регулярные графики
• двудольные графы без нетривиальных сильно регулярных подграфов
• двудольные графы Эйлера
• двудольные регулярные графы
• линейные графики
• разделить графики
• хордальные графы
• регулярные самодополняющие графы
• многогранные графы общих, простых и симплициальных выпуклых многогранников в произвольных размерностях.

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

Другие проблемы с GI

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

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

GI-сложные проблемы

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

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

Мануэль Блюм и Сампат Каннан ( 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 не является правильной программой, но отвечает правильно на и H , программа проверки либо даст правильный ответ, либо обнаружит недопустимое поведение P. G Если P не является правильной программой и отвечает неправильно на G и H , программа проверки обнаружит недопустимое поведение P с высокой вероятностью или ответит неправильно с вероятностью 2. ⁻¹⁰⁰ .

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

Приложения

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

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

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

В автоматизированном проектировании электроники изоморфизм графов лежит в основе этапа проектирования схемы «Компоновка по сравнению со схемой» (LVS), который представляет собой проверку того, ли электрические цепи, представленные схемой и компоновкой интегральной схемы . одинаковы

См. также

• Проблема автоморфизма графа
• Канонизация графа

Ссылки

• Ахо, Альфред В .; Хопкрофт, Джон ; Уллман, Джеффри Д. (1974), Разработка и анализ компьютерных алгоритмов , Ридинг, Массачусетс: Аддисон-Уэсли .
• Арвинд, Викраман; Кёблер, Йоханнес (2000), «Изоморфизм графов низкий для ZPP (NP) и других результатов низкой степени», Труды 17-го ежегодного симпозиума по теоретическим аспектам информатики , Конспекты лекций по информатике , том. 1770, Springer-Verlag, стр. 431–442 , doi : 10.1007/3-540-46541-3_36 , ISBN  3-540-67141-2 , МР   1781752 .
• Арвинд, Викраман; Курур, Пиюш П. (2006), «Изоморфизм графов в SPP», Information and Computation , 204 (5): 835–852, doi : 10.1016/j.ic.2006.02.002 , MR   2226371 .
• Аренас, Марсело; Диас, Гонсало И. (2016), «Точная сложность проблемы определяемости логики первого порядка», Транзакции ACM в системах баз данных , 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, стр. 667–676, дои : 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 , S2CID   6670135 .
• Бабай, Ласло ; Люкс, Юджин М. (1983), «Каноническая маркировка графов», Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '83) , стр. 171–183, doi : 10.1145/800061.808746 , ISBN  0-89791-099-0 , S2CID   12572142 .
• Бабай, Ласло (2015), Изоморфизм графов в квазиполиномиальное время , arXiv : 1512.03547 , Бибкод : 2015arXiv151203547B
• Бэрд, HS; Чо, Ю.Е. (1975), «Система проверки художественного проекта» , Труды 12-й конференции по автоматизации проектирования (DAC '75) , Пискатауэй, Нью-Джерси, США: IEEE Press, стр. 414–420 .
• Блюм, Мануэль ; Каннан, Сампат (1995), «Проектирование программ, проверяющих свою работу» , Journal of the ACM , 42 (1): 269–291, CiteSeerX   10.1.1.38.2537 , doi : 10.1145/200836.200880 , S2CID   52151779 .
• Бодлендер, Ханс (1990), «Полиномиальные алгоритмы для изоморфизма графов и хроматического индекса на частичных k -деревьях», Journal of Algorithms , 11 (4): 631–643, doi : 10.1016/0196-6774(90)90013-5 , МР   1079454 .
• Бут, Келлог С.; Колборн, CJ (1977), Проблемы, полиномиально эквивалентные изоморфизму графов , Технический отчет, том. CS-77-04, факультет компьютерных наук, Университет Ватерлоо .
• Бут, Келлог С.; Люкер, Джордж С. (1979), «Алгоритм с линейным временем для определения изоморфизма интервального графа» , Journal of the ACM , 26 (2): 183–195, doi : 10.1145/322123.322125 , MR   0528025 , S2CID   18859101 .
• Баучер, К.; Локер, Д. (2006), Полнота изоморфизма графов для совершенных графов и подклассов совершенных графов (PDF) , Технический отчет, том. CS-2006-32, Факультет компьютерных наук, Университет Ватерлоо .
• Чунг, Фан Р.К. (1985), «О ширине разреза и топологической пропускной способности дерева», SIAM Journal on Algebraic and Discrete Methods , 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: Каноническая маркировка» , Анализ данных графов , Wiley, стр. 120–122, ISBN  978-0-470-07303-2 .
• Датта, С.; Лимайе, Н.; Нимборкар, П.; Тирауф, Т.; Вагнер, Ф. (2009), «Изоморфизм планарных графов находится в лог-пространстве», 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 .
• Фоджа, П.; Сансоне, К.; Венто, М. (2001), «Сравнение производительности пяти алгоритмов изоморфизма графов» (PDF) , Proc. 3-й семинар IAPR-TC15 «Представления на основе графов в распознавании образов» , стр. 188–199, заархивировано из оригинала (PDF) 24 сентября 2015 г. , получено 18 декабря 2009 г.
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN  978-0-7167-1045-5 .
• Grigor'ev, D. Ju. (1981), "Complexity of 'wild' matrix problems and of the isomorphism of algebras and graphs", Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni V. A. Steklova Akademii Nauk SSSR (LOMI) (in Russian), 105 : 10–17, 198, MR  0628981 . English translation in Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
• Хопкрофт, Джон ; Вонг, Дж. (1974), «Алгоритм линейного времени для изоморфизма плоских графов», Труды шестого ежегодного симпозиума ACM по теории вычислений , стр. 172–184, doi : 10.1145/800119.803896 , S2CID   15561884 .
• Ирнигер, Кристоф-Андре Марио (2005), Сопоставление графов: фильтрация баз данных графов с использованием машинного обучения , Диссертации по искусственному интеллекту, том. 293, АКА, ISBN  1-58603-557-6 .
• Кайбель, Волкер; Шварц, Александр (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), «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время», Journal of Computer and System Sciences , 25 : 42–65, doi : 10.1016/0022-0000(82)90009-5 , МР   0685360 , S2CID   2572728 .
• Лукс, Юджин М. (1986), «Параллельные алгоритмы для групп перестановок и изоморфизма графов», Proc. 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, vol. 30, стр. 45–87, МР   0635936 .
• Миллер, Гэри (1980), «Проверка изоморфизма графов ограниченного рода», Труды 12-го ежегодного симпозиума ACM по теории вычислений , стр. 225–235, doi : 10.1145/800141.804670 , ISBN  0-89791-017-6 , S2CID   13647304 .
• Миллер, Гэри Л. (1983), «Проверка изоморфизма и канонические формы для k -сжимаемых графов (обобщение ограниченной валентности и ограниченного рода)», Proc. Межд. Конф. «Основы теории компьютеров» , Конспекты лекций по информатике , вып. 158, стр. 310–327, номер документа : 10.1007/3-540-12689-9_114 . Полная статья в журнале 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), "Решение проблемы изоморфизма циркулянтных графов", Труды. Лондонская математика. Соц. , 88 : 1–41, doi : 10.1112/s0024611503014412 , MR   2018956 , S2CID   16704931 .
• Нараянамурти, С.М.; Равиндран, Б. (2008), «О сложности поиска симметрии в марковских процессах принятия решений» (PDF) , Материалы двадцать пятой Международной конференции по машинному обучению (ICML 2008) , стр. 688–696 .
• Шмидт, Дуглас К.; Дрюффель, Ларри Э. (1976), «Алгоритм быстрого поиска с возвратом для проверки направленных графов на изоморфизм с использованием матриц расстояний», Journal of the 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   17268 751 .

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

• Прочтите, Рональд К.; Корнейл, Дерек Г. (1977), «Болезнь изоморфизма графов», Journal of Graph Theory , 1 (4): 339–363, doi : 10.1002/jgt.3190010410 , MR   0485586 , S2CID   26589776 .
• Гати, Г. (1979), «Дальнейшая аннотированная библиография по болезни изоморфизма», Journal of Graph Theory , 3 (2): 95–109, doi : 10.1002/jgt.3190030202 .
• Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), "Graph isomorphism problem", Journal of Mathematical Sciences , 29 (4): 1426–1481, doi : 10.1007/BF02104746 , S2CID  121818465 . (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences ), Vol. 118, pp. 83–158, 1982.)
• Арвинд, В.; Торан, Хакобо (2005), «Тестирование изоморфизма: перспективы и открытые проблемы» (PDF) , Бюллетень Европейской ассоциации теоретической информатики , 86 : 66–84 . (Краткий обзор открытых вопросов, связанных с проблемой изоморфизма графов, колец и групп.)
• Кёблер, Йоханнес; Шенинг, Уве ; Торан, Хакобо (1993), Проблема изоморфизма графов: ее структурная сложность , Биркхойзер, ISBN  978-0-8176-3680-7 . ( Из обложки книги : В книге основное внимание уделяется проблеме вычислительной сложности задачи и представлены несколько недавних результатов, которые обеспечивают лучшее понимание относительного положения задачи в классе NP, а также в других классах сложности.)
• Джонсон, Дэвид С. (2005), «Столбец NP-полноты», Транзакции ACM по алгоритмам , 1 (1): 160–176, doi : 10.1145/1077464.1077476 , S2CID   12604799 . (В этом 24-м выпуске колонки обсуждается современное состояние открытых проблем из книги «Компьютеры и трудноразрешимость» и предыдущих колонок, в частности, проблемы изоморфизма графов.)
• Торан, Хакобо; Вагнер, Фабиан (2009), «Сложность изоморфизма планарных графов» (PDF) , Бюллетень Европейской ассоциации теоретической информатики , 97 , заархивировано из оригинала (PDF) 20 сентября 2010 г. , получено 6 июня 2010 г. 03 .
• Стойчев, Стойчо Д. (2019), «Новые точные и эвристические алгоритмы для группы автоморфизмов графов и изоморфизма графов», Журнал экспериментальной алгоритмики , 24 : 1–27, doi : 10.1145/3333250 , S2CID   202676274 .

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

• Изоморфизм графов , обзор реализаций, Репозиторий алгоритмов Стоуни-Брука .