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 GG(V,E)F={G1,G2,...,Gn}GiG−viG−vG usuwając vi 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={G1,G2,...,Gk}GF ) gdzie k ≥ 3{[G1,...,Gk]|(∃G)[[G1,...,Gk]⊆vertex−deck(G)]}k≥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 .GIGINPk≥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 } ) .GInF={G1,G2,...,Gn})