Проблема GI-сложного графа, о которой неизвестно, что

15

Граф Изоморфизм ( ) является хорошим кандидатом для N P -проблемой задачи. N P -intermediate проблемы существуют , если Р не = Н Р . Я ищу естественную проблему, которая трудна для G I при редукции Карпа (графовая задача X такая, что G I < m p X ).GINPNPP=NPGIXGI<pmX

Существует ли естественная проблема -твердого графа, которая не является ни G I -эквивалентной, ни известной как N P -полной?GIGINP

Мухаммед Аль-Туркистани
источник
GI-эквивалент при редукции Карпа.
Мохаммед Аль-Туркистани
1
кандидаты: проблемы между P и NPC
vzn
2
Кажется возможным построить бесконечную иерархию таких проблем, смешивая «только достаточно» Клики с GI, в варианте замедленной диагонализации Ладнера. См. Также аналогичную конструкцию, предложенную Бодирским / Ченом / Гроэ / Терли / Вейером.
Андрас Саламон
Кстати, вы можете изменить заголовок на «Жесткая графическая проблема, которая не является NP-полной». Моей первой мыслью, когда я увидел текущее название, было «Изоморфизм кольца!» но ответ, который вы нашли (я думаю) значительно интереснее.
Джошуа Грохов
@JoshuaGrochow Спасибо за ваш отзыв. Что ты посоветуешь? Обратите внимание, что меня интересуют проблемы с графами.
Мухаммед Аль-Туркистани

Ответы:

8

После тщательного поиска я обнаружил проблему легитимной вершинной колоды (LVD), которая связана со знаменитой гипотезой о восстановлении графа . Колода графа является мульти-набор графиков , Р = { G 1 , G 2 , . , , , G n } такой, что G i изоморфен G - v i ( G - v - граф, полученный из G удалением vG(V,E)F={G1,G2,...,Gn}GiGviGvGvи его инцидентные края). ( )|V|=n

К-ЛЕГИТИМНАЯ проблема вершинного SUBDECK, учитывая мульти-набор графиков , , Решают , есть ли граф G такая , что F является подмножеством его вершины палубы ( к-LVD = { [ G 1 , . . . , С к ] | ( G ) [ [ G 1 , . . . , GF={G1,G2,...,Gk}GF )где K 3{[G1,...,Gk]|(G)[[G1,...,Gk]vertexdeck(G)]}k3

Проблема k-LVD является -твердой и не известна как G I -эквивалентная. Это открытая проблема ли к-LVD является Н Р -полным (для к 3 ). См. Раздел открытых проблем результатов Сложности в реконструкции графа .GIGINPk3

Также в статье предлагается существование проблемы промежуточной сложности между и k-LVD . Проблема в том , LVD = п-LVD , где все п - кандидатов карточки приведены (Вход для LVD является F = { G 1 , G 2 , . . . , G п } ) .GInF={G1,G2,...,Gn})

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

Более простой проблемой может быть WEIGHTED_HYPERGRAPH_ISOMORPHISM. Вам даны два гиперграфа и G 2 на n вершинах с взвешенными гиперграницами, решите, есть ли перестановка вершин p i, превращающая G 1 в G 2 .G1G2npiG1G2


источник