Проблема изоморфизма графов - Graph isomorphism problem

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

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

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

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

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

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

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

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

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

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

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

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

Решенные частные случаи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Признание самодополняемости графа или орграфа.
Проблема клики для класса так называемых М -графов. Показано, что нахождение изоморфизма для n -вершинных графов эквивалентно нахождению n -клики в M -графе размера n ² . Этот факт интересен тем, что задача нахождения ( n - ε ) -клики в M -графе размера n ² является NP-полной для сколь угодно малого положительного ε.
Проблема гомеоморфизма 2-комплексов.

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

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

Приложения

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

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

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

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

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

Примечания

использованная литература

Ахо, Альфред В .; Хопкрофт, Джон ; Ульман, Джеффри Д. (1974), Дизайн и анализ компьютерных алгоритмов , чтение, Массачусетс: Аддисон-Уэсли.
Арвинд, Викраман; Кёблер, Йоханнес (2000), «Изоморфизм графов низкий для результатов ZPP (NP) и других малых размеров», Труды 17-го ежегодного симпозиума по теоретическим аспектам информатики , Lecture Notes in Computer Science , 1770 , Springer-Verlag, pp. . 431-442 , DOI : 10.1007 / 3-540-46541-3_36 , ISBN 3-540-67141-2, MR 1781752.
Арвинд, Викраман; Kurur, Piyush P. (2006), "Graph изоморфизм в SPP", информации и вычислений , 204 (5): 835-852, DOI : 10.1016 / j.ic.2006.02.002 , MR 2226371.
Бабай, Ласло (1980), "О сложности канонической классификации сильно регулярных графов", SIAM журнал по вычислениям , 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.
Бабай, Ласло ; Григорьев, Д.Ю. ; Mount, David M. (1982), «Изоморфизм графов с ограниченной собственным значением кратности», Труды 14 - й ежегодной ACM симпозиум по теории вычислений , С. 310-324,. Дои : 10,1145 / 800070,802206 , ISBN 0-89791-070-2, S2CID 12837287.
Бабай, Ласло ; Кантор, Уильям ; Luks, Евгений (1983), «Вычислительная сложность и классификация конечных простых групп», Труды 24 - го ежегодного симпозиума Основы информатики (FOCS) , стр 162-171,. DOI : 10,1109 / SFCS.1983.10 , S2CID 6670135.
Бабай, Ласло ; Luks, Евгений М. (1983), «Каноническое маркировка графов», Труды Пятнадцатый ежегодный ACM симпозиум по теории вычислений (STOC '83) , стр 171-183,. Дои : 10,1145 / 800061,808746 , ISBN 0-89791-099-0, S2CID 12572142.
Бабай, Ласло (2015), Изоморфизм графов в квазиполиномиальном времени , arXiv : 1512.03547 , Bibcode : 2015arXiv151203547B
Бэрд, HS; Чо, Й.Е. (1975), "Система проверки дизайна художественного произведения" , Труды 12-й конференции по автоматизации проектирования (DAC '75) , Пискатауэй, штат Нью-Джерси, США: IEEE Press, стр. 414–420.
Блюм, Мануэль ; Kannan, Сампатх (1995), "Разработка программы , которые проверяют свою работу" , Журнал ACM , 42 (1): 269-291, CiteSeerX 10.1.1.38.2537 , DOI : 10,1145 / 200836,200880 , S2CID 52151779.
Bodlaender, Ганс (1990), "полиномиальные алгоритмы для изоморфизма графов и хроматического индекса на частичном K -дерев", Journal алгоритмов , 11 (4): 631-643, DOI : 10.1016 / 0196-6774 (90) 90013-5 , Руководство по ремонту 1079454.
Бут, Kellogg S .; Колборн, CJ (1977), Проблемы, полиномиально эквивалентные изоморфизму графов , Технический отчет, CS-77-04, Департамент компьютерных наук, Университет Ватерлоо.
Бут, Kellogg S .; Lueker, Джордж С. (1979), "Линейный алгоритм времени для принятия решения интервального изоморфизма графов" , Журнал ACM , 26 (2): 183-195, DOI : 10,1145 / 322123,322125 , MR 0528025 , S2CID 18859101.
Boucher, C .; Локер, Д. (2006), Полнота изоморфизма графов для совершенных графов и подклассов совершенных графов (PDF) , Технический отчет, CS-2006-32, Департамент компьютерных наук, Университет Ватерлоо.
Чанг, Вентилятор Р.К. (1985), «О Ширина разреза и топологической ширины полосы дерева», SIAM журнал на алгебраических и дискретных методов , 6 (2): 268-277, DOI : 10,1137 / 0606026 , МР 0778007.
Colbourn, CJ (1981), "О проверке изоморфизма графов перестановок", сети , 11 : 13-21, DOI : 10.1002 / net.3230110103 , MR 0608916.
Колборн, Марлен Джонс; Colbourn, Чарльз Дж (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.
Datta, S .; Limaye, N .; Nimbhorkar, P .; Thierauf, T .; Вагнер, Ф. (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 .; Венто, М. (2001), "Сравнение производительности пяти алгоритмов для изоморфизма графов" (PDF) , Proc. 3-й семинар IAPR-TC15 Графические представления в распознавании образов , стр. 188–199.
Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5.
Григорьев, Д.Ю. (1981), «Сложность„диких“матричных задач, изоморфизма алгебр и графов», Записки научных семинаров Ленинградского Otdeleniya Математического института Imeni В. А. Стеклова АН СССР (ЛОМИ) (на русском языке ), 105 : 10-17, 198 , Руководство по ремонту 0628981. Английский перевод в Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
Хопкрофт, Джон ; Wong, J. (1974), «время алгоритм Linear изоморфизма планарных графов», Труды Шестой Ежегодной ACM симпозиум по теории вычислений , стр 172-184,. Дои : 10,1145 / 800119,803896 , S2CID 15561884.
Ирнигер, Кристоф-Андре Марио (2005 г.), Сопоставление графов: фильтрация баз данных графов с использованием машинного обучения , Диссертация на тему: künstlichen Intelligenz, 293 , AKA, ISBN. 1-58603-557-6.
Kaibel, Volker; Шварц, Александр (2003), "О сложности проблем изоморфизма многогранников" , Графы и комбинаторика , 19 (2): 215–230, arXiv : math / 0106093 , doi : 10.1007 / s00373-002-0503-y , MR 1996205 , S2CID 179936 , заархивировано из оригинала 21.07.2015.
Келли, Пол Дж (1957), "Конгруэнтность теорема для деревьев", Тихоокеанский журнал математики , 7 : 961-968, DOI : 10,2140 / pjm.1957.7.961 , MR 0087949.
Кёблер, Йоханнес; Шёнинг, Уве ; Toran, Джакобо (1992), "изоморфизм графов является низким для ПП", вычислительная сложность , 2 (4): 301-330, DOI : 10.1007 / BF01200427 , МР 1215315 , S2CID 8542603.
Кодзэно, Dexter (1978), "Проблема клики эквивалентно изоморфизма графов", ACM SIGACT News , 10 (2): 50-52, DOI : 10,1145 / 990524,990529 , S2CID 52835766.
Luks, Евгений М. (1982), «Изоморфизм графов ограниченной валентности может быть проверен в полиномиальное время», журнал компьютерных и системных наук , 25 : 42-65, DOI : 10,1016 / 0022-0000 (82) 90009-5 , Руководство по ремонту 0685360 , S2CID 2572728.
Люкс, Юджин М. (1986), "Параллельные алгоритмы для групп перестановок и изоморфизм графов", Proc. IEEE Symp. Основы компьютерных наук , стр. 292–302..
Матон, Рудольф (1979), «Заметка о проблеме подсчета изоморфизма графов», Письма об обработке информации , 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,. Дои : 10,1145 / 800141,804670 , ISBN 0-89791-017-6, S2CID 13647304.
Миллер, Гэри Л. (1983), "Проверка изоморфизма и канонические формы для k- сжимаемых графов (обобщение ограниченной валентности и ограниченного рода)", Proc. Int. Конф. по основам теории информатики , Lecture Notes в области компьютерных наук , 158 ., С. 310-327, DOI : 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.
Музычук, Михаил (2004), "Решение проблемы изоморфизма для циркулянтных графов", Тр. Лондонская математика. Soc. , 88 : 1-41, DOI : 10,1112 / s0024611503014412 , MR 2018956.
Narayanamurthy, SM; Равиндран Б. (2008), «О сложности нахождения симметрий в марковских процессах принятия решений» (PDF) , Труды Двадцать пятой Международной конференции по машинному обучению (ICML 2008) , стр. 688–696.
Schmidt, Douglas C .; Druffel, Ларри Е. (1976), "Быстрый алгоритм возвратов испытаний ориентированных графов для изоморфизма с использованием матриц расстояния", Журнал АСМ , 23 (3): 433-445, DOI : 10,1145 / 321958,321963 , МР 0411230 , S2CID 6163956.
Шёнинг, Уве (1987), «Изоморфизм графов находится в низшей иерархии», Труды 4-го ежегодного симпозиума по теоретическим аспектам информатики , стр. 114–124; также Journal of Computer and System Sciences 37 : 312–323, 1988.
Шоу-Тейлор, Джон; Pisanski, Tomaž (1994), "Гомеоморфизм из 2-комплексов изоморфизм графов полный", SIAM журнал по вычислениям , 23 (1): 120-132, DOI : 10,1137 / S0097539791198900 , МР 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.

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

Прочтите, Рональд С.; Corneil, Дерек Г. (1977), "Граф болезнь изоморфизмом", Журнал теории графов , 1 (4): 339-363, DOI : 10.1002 / jgt.3190010410 , МР 0485586.
Гати, Г. (1979), «Дополнительная аннотированная библиография по болезни изоморфизма», Journal of Graph Theory , 3 (2): 95–109, DOI : 10.1002 / jgt.3190030202.
Земляченко В.Н.; Корнеенко Н.М.; Тышкевич, RI (1985), "Graph проблема изоморфизма", журнал математических наук , 29 (4): 1426-1481, DOI : 10.1007 / BF02104746 , S2CID 121818465. ( В переводе с Записки научных семинаров Ленинградского Otdeleniya Математического института им. В. А. Стеклова АН СССР (отчеты Семинары Ленинградское отделение Математического института им Академии наук СССР ), т. 118, стр. 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 г. , извлечено 2010-06- 03.

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

Изоморфизм графов , обзор реализаций, The Stony Brook Algorithm Repository .

Languages

In other projects