Проблема изоморфизма графов - Википедия - Graph isomorphism problem

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

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

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

Эта проблема - частный случай проблема изоморфизма подграфов,^[3] который спрашивает, может ли данный граф грамм содержит подграф, изоморфный другому заданному графу ЧАС; эта проблема, как известно, NP-полная. Также известно, что это частный случай неабелев проблема скрытой подгруппы над симметричная группа.^[4]

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

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

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

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

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

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

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

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

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

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

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

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

Проблема изоморфизма графов содержится в обоих НП и со-ЯВЛЯЮСЬ. GI содержится в и низкий за Четность P, а также содержится в потенциально гораздо меньшем классе SPP.^[30] То, что он находится в четности P, означает, что проблема изоморфизма графов не сложнее, чем определение того, является ли полиномиальное время недетерминированная машина Тьюринга имеет четное или нечетное количество принимающих путей. GI также содержится в низком уровне для ЗПП^НП.^[31] По сути, это означает, что эффективный Алгоритм Лас-Вегаса с доступом к НП оракул может решить изоморфизм графов настолько легко, что не получит никакой силы от того, что ему дана возможность делать это в постоянное время.

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

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

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

• диграфы^[32]
• помеченные графики, при условии, что изоморфизм не требуется для сохранения меток,^[32] но только отношение эквивалентности состоящий из пар вершин с одинаковой меткой
• «поляризованные графы» (состоящие из полный график K_м и пустой график K_п плюс несколько ребер, соединяющих их; их изоморфизм должен сохранять разбиение)^[32]
• 2-цветные графики^[32]
• явно заданный конечный структуры^[32]
• мультиграфы^[32]
• гиперграфы^[32]
• конечные автоматы^[32]
• Марковские процессы принятия решений^[33]
• коммутативный 3 класс нильпотентный (т.е. xyz = 0 для всех элементов Икс, у, z) полугруппы^[32]
• конечный ранг ассоциативный алгебры над фиксированным алгебраически замкнутым полем с нулевым квадратом радикала и коммутативным множителем над радикалом.^[32][34]
• контекстно-свободные грамматики^[32]
• сбалансированные неполные блочные конструкции^[32]
• Признавая комбинаторный изоморфизм из выпуклые многогранники представлены вершинно-фасеточными инциденциями.^[35]

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

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

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

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

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

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

• Признание самодополнимости графа или орграфа.^[38]
• А проблема клики для класса так называемых M-графы. Показано, что нахождение изоморфизма для п-вершинных графов эквивалентно нахождению п-клик в M-график размера п². Этот факт интересен тем, что проблема поиска (п − ε) -клика в M-график размера п² NP-полна при сколь угодно малых положительных ε.^[39]
• Проблема гомеоморфизма 2-комплексов.^[40]

GI-тяжелые проблемы

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

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

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

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

Эта процедура является полиномиальной и дает правильный ответ, если п - правильная программа для изоморфизма графов. Если п неверная программа, но правильно отвечает на грамм и ЧАС, программа проверки либо выдаст правильный ответ, либо обнаружит недопустимое поведение п.Если п не является правильной программой и неправильно отвечает на грамм и ЧАС, программа проверки обнаружит недопустимое поведение п с большой вероятностью, или ответ неправильный с вероятностью 2⁻¹⁰⁰.

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

Приложения

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

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

Поиск по химической базе данных является примером графического сбор данных, где канонизация графа подход часто используется.^[44] В частности, ряд идентификаторы за химические субстанции, Такие как Улыбки и ИнЧИ, разработанные для обеспечения стандартного и удобочитаемого способа кодирования молекулярной информации и для облегчения поиска такой информации в базах данных и в Интернете, используют этап канонизации в своих вычислениях, который, по сути, является канонизацией графа, представляющего молекулу.

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

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

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

Примечания

Рекомендации