Masalah grafik GI-hard tidak dikenal sebagai

Grafik isomorfisma ( ) adalah calon yang baik untuk N P masalah -intermediate. N P masalah -intermediate ada kecuali P = N P . Saya mencari masalah alam yang sulit untuk G Aku di bawah pengurangan Karp (A masalah grafik X sehingga G Saya < m p X ).$GI$$NP$$NP$$P=NP$$GI$$X$$GI <_p^m X$

Apakah ada masalah -hard graph alami yang bukan G I- equivalent atau dikenal sebagai N P -complete?$GI$$GI$$NP$

Setelah pencarian yang ekstensif, saya menemukan masalah Deck Vertex Sah (LVD) yang terkait dengan dugaan Graph Reconstruction . Sebuah dek grafik adalah multi-set grafik F = { G 1 , G 2 , . . . , G n } sedemikian rupa sehingga G i adalah isomorfik ke G - v i ( G - v adalah grafik yang diperoleh dari G dengan menghapus $G(V, E)$$F = \{G_1,G_2, . . . , G_n\}$$G_i$$G−v_i$$G-v$$G$$v$dan tepi insidennya). ( )$|V|=n$

Masalah VERTEX-SUBDECK k-SAH, diberikan multi-set grafik , Putuskan apakah ada grafik G sehingga F merupakan subset dari yang vertex-deck ( k-LVD = { [ G 1 , . . . , G k ] | ( ∃ G ) [ [ G 1 , . . . , $F= \{G_1,G_2, . . . , G_k\}$$G$$F$ ) di mana k ≥ $\{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$$k \ge 3$

Masalah k-LVD adalah -hard dan tidak dikenal sebagai G I- equivalent. Sudah menjadi masalah terbuka apakah k-LVD adalah N P -complete (untuk k ≥ 3 ). Lihat bagian masalah terbuka hasil Kompleksitas dalam rekonstruksi grafik .$GI$$GI$$NP$$k \ge 3$

Juga, makalah ini menyarankan adanya masalah kompleksitas menengah antara dan k-LVD . Masalahnya adalah LVD = n-LVD mana semua n kartu calon diberikan (Input untuk LVD adalah 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$