Введение
Нерешенная проблема в теории вычислительной сложности
Проблема изоморфизма графов — это вычислительная задача определения, изоморфны ли два конечных графа. Неизвестно, может ли эта проблема быть решена за полиномиальное время, и она также не является NP-полной, поэтому она может относиться к классу вычислительной сложности NP-промежуточный. Известно, что проблема изоморфизма графов находится в нижней иерархии класса NP, что означает, что она не является NP-полной, если только полиномиальная иерархия времени не схлопнется до своего второго уровня. В то же время, изоморфизм для многих специальных классов графов может быть решен за полиномиальное время, и на практике изоморфизм графов часто можно эффективно вычислять. Эта проблема является частным случаем проблемы изоморфизма подграфов, которая заключается в определении, содержит ли данный граф G подграф, изоморфный другому данному графу H; эта проблема известна как NP-полная. Также известно, что это частный случай проблемы скрытых неабелевых подгрупп над симметрической группой. В области распознавания изображений она известна как точное сопоставление графов.
Состояние техники
В ноябре 2015 года Ласло Бабаи объявил о квазиполиномиальном алгоритме времени для всех графов, то есть с временем работы для некоторой фиксированной константы. 4 января 2017 года Бабаи отозвал утверждение о квазиполиномиальности и вместо этого заявил о субэкспоненциальной временной сложности после того, как Харальд Хельфготт обнаружил ошибку в доказательстве. 9 января 2017 года Бабаи объявил о коррекции (опубликована полностью 19 января) и восстановил утверждение о квазиполиномиальности, которое было подтверждено Хельфготтом. Хельфготт также утверждает, что можно взять 1/c = 3, таким образом, время работы составляет 2^(O((log n)^3)). До этого лучшим известным теоретическим алгоритмом был алгоритм, основанный на более ранних работах в сочетании с алгоритмом вычисления субфакториала В. Н. Земляченко. Этот алгоритм имеет время работы 2^O для графов с n вершинами и опирается на классификацию конечных простых групп. Без этой теоремы классификации, немного более слабое ограничение было получено сначала для сильно регулярных графов, а затем расширено на общие графы. Улучшение показателя для сильно регулярных графов было выполнено. Для гиперграфов ограниченного ранга субэкспоненциальная верхняя граница, соответствующая случаю графов, была получена. Существует несколько конкурирующих практических алгоритмов для изоморфизма графов, таких как алгоритмы, разработанные, , и. Хотя они, по-видимому, хорошо работают на случайных графах, основным недостатком этих алгоритмов является их экспоненциальное время работы в худшем случае. Задача об изоморфизме графов вычислительно эквивалентна задаче вычисления группы автоморфизмов графа и является более слабой, чем задача об изоморфизме группы перестановок и задача об пересечении группы перестановок. Для последних двух задач были получены границы сложности, аналогичные границе для изоморфизма графов.
was obtained first for strongly regular graphs by , and then extended to general graphs by Improvement of the exponent for strongly regular graphs was done by For hypergraphs of bounded rank, a subexponential upper bound matching the case of graphs was obtained by
There are several competing practical algorithms for graph isomorphism, such as those due to , , , and While they seem to perform well on random graphs, a major drawback of these algorithms is their exponential time performance in the worst case. The graph isomorphism problem is computationally equivalent to the problem of computing the automorphism group of a graph, and is weaker than the permutation group isomorphism problem and the permutation group intersection problem. For the latter two problems, obtained complexity bounds similar to that for graph isomorphism.
Класс сложности GI
Поскольку проблема изоморфизма графов не известна как NP-полная и не известна как разрешимая за полиномиальное время, исследователи стремились получить представление об этой проблеме, определив новый класс GI – множество задач, полиномиально сводимых по Тьюрингу к проблеме изоморфизма графов. Если проблема изоморфизма графов действительно разрешима за полиномиальное время, то GI будет равна P. С другой стороны, если проблема является NP-полной, то GI будет равна NP, и все задачи в NP будут разрешимы за квазиполиномиальное время. Как это обычно бывает для классов сложности в иерархии полиномиального времени, задача называется GI-трудной, если существует полиномиальная редукция по Тьюрингу из любой задачи в GI к этой задаче, то есть, полиномиальное решение GI-трудной задачи даст полиномиальное решение проблемы изоморфизма графов (и, следовательно, для всех задач в GI). Задача называется полной для GI, или GI-полной, если она одновременно GI-трудная и полиномиальное решение проблемы GI даст полиномиальное решение проблемы изоморфизма графов. Проблема изоморфизма графов содержится как в NP, так и в co-AM. GI содержится в и является низким для Parity P, а также содержится в потенциально гораздо меньшем классе SPP. Тот факт, что она лежит в Parity P, означает, что проблема изоморфизма графов не сложнее, чем определение того, имеет ли полиномиальная недетерминированная машина Тьюринга четное или нечетное количество принимающих путей. GI также содержится в и является низким для ZPPNP. Это по сути означает, что эффективный алгоритм Лас-Вегаса с доступом к NP-оракулу может решать проблему изоморфизма графов настолько легко, что не получает никакой выгоды от возможности делать это за постоянное время.
The graph isomorphism problem is contained in both NP and co AM. GI is contained in and low for Parity P, as well as contained in the potentially much smaller class SPP. That it lies in Parity P means that the graph isomorphism problem is no harder than determining whether a polynomial time nondeterministic Turing machine has an even or odd number of accepting paths. GI is also contained in and low for ZPPNP. This essentially means that an efficient Las Vegas algorithm with access to an NP oracle can solve graph isomorphism so easily that it gains no power from being given the ability to do so in constant time.
Класса графиков с полным ГИ
Класс графов называется GI-полным, если задача распознавания изоморфизма для графов из этого подкласса является GI-полной задачей. Следующие классы являются GI-полными: задача определения, являются ли два выпуклых многогранника, заданные либо V-описанием, либо H-описанием, проективно или аффинно изоморфными. Последнее означает существование проективного или аффинного преобразования между пространствами, содержащими эти многогранники (не обязательно одной и той же размерности), которое индуцирует биекцию между многогранниками.
The problem of deciding whether two convex polytopes given by either the V description or H description are projectively or affinely isomorphic. The latter means existence of a projective or affine map between the spaces that contain the two polytopes (not necessarily of the same dimension) which induces a bijection between the polytopes.
Приложения
Графы широко используются для кодирования структурной информации во многих областях, включая компьютерное зрение и распознавание образов, а сопоставление графов, то есть выявление сходства между графами, является важным инструментом в этих областях. В этих областях задача об изоморфизме графов известна как точное совпадение графов. В хемоинформатике и математической химии проверка изоморфизма графов используется для идентификации химического соединения в химической базе данных. Также, в органической математической химии проверка изоморфизма графов полезна для генерации молекулярных графов и компьютерного синтеза. Поиск в химических базах данных является примером графической интеллектуальной обработки данных, где часто применяется подход канонизации графов. В частности, ряд идентификаторов химических веществ, таких как SMILES и InChI, разработан для обеспечения стандартного и удобного для чтения способа кодирования молекулярной информации и облегчения поиска такой информации в базах данных и в сети Интернет, используют этап канонизации в своих вычислениях, который по сути является канонизацией графа, представляющего молекулу. В автоматизированном проектировании электронных схем изоморфизм графов лежит в основе этапа проектирования Layout Versus Schematic (LVS), который представляет собой проверку соответствия электрических схем, заданных принципиальной схемой и компоновочным решением интегральной схемы.
Исследования и монографии
(Перевод с языка: Записки Научных Семинаров Ленинградского Отделения Математического Института им. В. А. Стеклова АН СССР (Записи семинаров Ленинградского отделения Стекловского института математики АН СССР), том 118, с. 83–158, 1982) (Краткий обзор открытых вопросов, связанных с проблемой изоморфизма для графов, колец и групп.) (С обложки книги: Книга посвящена проблеме вычислительной сложности и представляет несколько недавних результатов, которые позволяют лучше понять относительное положение этой проблемы в классе NP, а также в других классах сложности.) (В этом 24-м выпуске колонки рассматривается современное состояние открытых проблем из книги "Компьютеры и неразрешимость" и предыдущих выпусков, в частности, проблема изоморфизма графов.)
Программное обеспечение
Изоморфизм графов, обзор реализаций, репозиторий алгоритмов Стоуни-Брук.