G-trudnym problemem wykres nie wiadomo, że

Wykres Izomorfizm ( ) jest dobrym kandydatem dla N P problemu -intermediate. N P istnieje -intermediate problemy chyba P = N P . Szukam naturalnego problemu, który jest trudny dla G I przy redukcji Karp (Problem graficzny X taki, że G I < m p X ).$GI$$NP$$NP$$P=NP$$GI$$X$$GI <_p^m X$

Czy istnieje naturalna -hard wykres problem, który nie jest ani G I -equivalent ani znany jako$GI$$GI$ -Complete?$NP$

Po obszernych poszukiwaniach znalazłem uzasadniony problem z wierzchołkiem wierzchołka (LVD), który jest związany ze słynną hipotezą Rekonstrukcji Grafu . Pomost grafu to wielu zestaw wykresów F = { G 1 , G 2 , . . . , G n } tak, że G i jest izomorficzny G - v i ( G - V przedstawia wykres uzyskano z $G(V, E)$$F = \{G_1,G_2, . . . , G_n\}$$G_i$$G−v_i$$G-v$$G$ usuwając $v$i jego krawędzie incydentów). ( )$|V|=n$

Problem VERTEX-SUBDECK k uzasadnione, biorąc pod uwagę wiele zestaw wykresów zdecydować, czy jest wykresem G , tak że F jest podzbiorem wierzchołek pokładu ( k LVD = { [ G 1 , . . . , G K ] | ( ∃ G ) [ [ G 1 , . . $F= \{G_1,G_2, . . . , G_k\}$$G$$F$ ) gdzie k ≥ $\{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$$k \ge 3$

Problem k-LVD to twardy i nie jest znany jako G I - równoważny. Jest otwarty problem, czy K-LVD jest N P -Complete (dla k ≥ 3 ). Zobacz sekcję „Otwarte problemy” złożoności wyników w rekonstrukcji wykresu .$GI$$GI$$NP$$k \ge 3$

Ponadto artykuł sugeruje istnienie problemu pośredniej złożoności między i k-LVD . Problemem jest to, LVD = n-LVD którym wszystkie n podano karty kandydujące (wejście LVD jest F = { G 1 , G 2 , . . . , G n } ) .$GI$$n$$F= \{G_1,G_2, . . . , G_n \})$

$G_1$$G_2$$n$$pi$$G_1$$G_2$