Граф Изоморфизм ( ) является хорошим кандидатом для N P -проблемой задачи. N P -intermediate проблемы существуют , если Р не = Н Р . Я ищу естественную проблему, которая трудна для G I при редукции Карпа (графовая задача X такая, что G I < m p X ).
Существует ли естественная проблема -твердого графа, которая не является ни G I -эквивалентной, ни известной как N P -полной?
cc.complexity-theory
graph-theory
graph-isomorphism
np-intermediate
Мухаммед Аль-Туркистани
источник
источник
Ответы:
После тщательного поиска я обнаружил проблему легитимной вершинной колоды (LVD), которая связана со знаменитой гипотезой о восстановлении графа . Колода графа является мульти-набор графиков , Р = { G 1 , G 2 , . , , , G n } такой, что G i изоморфен G - v i ( G - v - граф, полученный из G удалением vG(V,E) F={G1,G2,...,Gn} Gi G−vi G−v G v и его инцидентные края). ( )|V|=n
К-ЛЕГИТИМНАЯ проблема вершинного SUBDECK, учитывая мульти-набор графиков , , Решают , есть ли граф G такая , что F является подмножеством его вершины палубы ( к-LVD = { [ G 1 , . . . , С к ] | ( ∃ G ) [ [ G 1 , . . . , GF={G1,G2,...,Gk} G F )где K ≥ 3{[G1,...,Gk]|(∃G)[[G1,...,Gk]⊆vertex−deck(G)]} k≥3
Проблема k-LVD является -твердой и не известна как G I -эквивалентная. Это открытая проблема ли к-LVD является Н Р -полным (для к ≥ 3 ). См. Раздел открытых проблем результатов Сложности в реконструкции графа .GI GI NP k≥3
Также в статье предлагается существование проблемы промежуточной сложности между и k-LVD . Проблема в том , LVD = п-LVD , где все п - кандидатов карточки приведены (Вход для LVD является F = { G 1 , G 2 , . . . , G п } ) .GI n F={G1,G2,...,Gn})
источник
Более простой проблемой может быть WEIGHTED_HYPERGRAPH_ISOMORPHISM. Вам даны два гиперграфа и G 2 на n вершинах с взвешенными гиперграницами, решите, есть ли перестановка вершин p i, превращающая G 1 в G 2 .G1 G2 n pi G1 G2
источник