Открытые проблемы, связанные с изоморфизмом графа

18

В настоящее время я делаю обзор литературы по проблеме изоморфизма графов (GI).

Я хотел бы знать некоторые открытые вопросы, связанные со следующим

  1. Каковы параметры графика, для которых фиксированная возможность отслеживания GI является открытой проблемой.

  2. Каковы параметры графа, фиксируя их полиномиальной разрешимостью GI, неизвестно.

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

Спасибо.

graph-isomorphism fixed-parameter-tractable Кумар
источник
3
Я не знаю каких-либо окончательных ответов на ваши вопросы. Если вы найдете частичные ответы (что может потребовать просмотра десятков опубликованных исследовательских работ), было бы здорово, если бы вы могли дать ссылку на созданное вами резюме или дать его основные моменты в качестве ответа.
Андрас Саламон
Вопрос 3, вопрос. для многих классов графов проверенными GI полную, вопрос «является not- X графы GI полным?» открытый? Имеет ли это смысл? связанный cs.se вопросИксИкс
vzn

Ответы:

13

По первому вопросу: Изоморфизм графов рассматривался как минимум для следующих параметров, для которых возможность определения с фиксированными параметрами все еще открыта.

  • pathwidth / treewidth (см. [2], здесь задавался вопрос ), может быть решен: http://arxiv.org/abs/1404.0818
  • ширина / полоса пропускания [1]
  • размер набора удаления вершин treewidth-k (номер набора вершин обратной связи в [7])
  • ширина расстояния дерева / пути (см. [1]), ширина расстояния связанного дерева (см. [3], однако вы можете довольно близко подойти к последнему, см. раздел 6.4 моей дипломной работы ) : решено Ю. Отачи и Р Швейцер: http://arxiv.org/abs/1403.7238
  • ширина клика / глубина куста (или глубина SC) (см. [ 4 ])
  • максимальная степень [5]
  • род [6] / номер пересечения [8]

Обратите внимание, что для некоторых из них ведутся активные исследования.

[1]: К. Ямазаки, Х. Л. Бодлендер, Б. де Флюитер и Д. М. Тиликос. Изоморфизм для графов ограниченной ширины расстояния. Алгоритмика 24.2 (1999)

[2]: HL Bodlaender. Полиномиальные алгоритмы для изоморфизма графов и хроматического индекса на частичных деревьях. Журнал Алгоритмов 11.4 (1990)

[3]: Ю. Отачи. Изоморфизм для графов ограниченной ширины связного пути-расстояния-ширины. Алгоритмы и вычисления. Springer, 2012

[ 4 ]: http://www.fi.muni.cz/~hlineny/res-en.html#recent

[5]: Л. Бабай и Э. М. Лукс. Каноническая маркировка графиков. STOC '83.

[6]: И.С. Филотти и Дж. Н. Майер. Алгоритм полиномиального времени для определения изоморфизма графов фиксированного рода. STOC '80 / Г. Миллер. Тестирование изоморфизма графов ограниченного рода. STOC '80

[7]: С. Крач и П. Швейцер. Изоморфизм графов ограниченного числа множеств вершин обратной связи. SWAT 2010

[8]: http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf

frafl
источник
1
Что касается активных соответствующих исследований в этой области, я бы предложил несколько дополнительных ссылок. [A] В данном документе, представленном в IPEC 2012, показано, что изоморфизм графа является параметром с фиксированным параметром в глубине дерева графа, который является параметром, связанным с шириной дерева. [B] Эта статья здесь показывает , что изоморфизм графов для аккордовых графов FPT в размере наибольшей симплициальной компоненты.
Адам Буланд
3
Sграмм
@ Adam Bouland Существуют ли алгоритмы FPT или полиномиального времени для графа изоморфизма для ограниченной ширины полосы.
Кумар
1
@Kumar Это разрешимое время, но не известно, чтобы быть FPT. Смотри Yamazaki et al. [1] в ответ фрафл.
Йота Отачи
13

Для второго вопроса: Фиксирование ширины ранга (эквивалентно, фиксация ширины клика), разрешимость полиномиального времени GI не известна. Недавно Мамаду Канте поставил открытый вопрос, можно ли решить проблему изоморфизма графов за полиномиальное время для графов ограниченной линейной ширины ранга .

Г. Баум
источник
5

По третьему вопросу: обзорная работа Брандштадта, Ле и Спинрада «Классы графов: обзор», SIAM, 1999 г., содержит несколько классов графов, для которых G-полнота неизвестна. Одним из таких классов являются трапециевидные графы . Другой класс - это круговые дуговые графы, которые упоминаются как открытая проблема во введении Уэхары статьи « Трактабельности и недостижимости на геометрических графах пересечений ».

РЕДАКТИРОВАТЬ : Проблема Изоморфизм графов для турниров, как известно, не GI-полная.

Мухаммед Аль-Туркистани
источник
4

По третьему вопросу вы также можете взглянуть на www.graphclasses.org : запустите Java-апплет и выберите Проблемы -> Граничные / Открытые задачи -> Изоморфизм графов.

Вы получите огромный список классов графов, для которых статус проблемы GI неизвестен ISGCI (он может быть в P или GI-завершенном); вероятно, для некоторых из них GI-полнота уже исчерпана или просто еще не изучена; но это хорошая отправная точка для поиска статей о них.

Марцио де Биаси
источник