G-trudnym problemem wykres nie wiadomo, że


15

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 ).GINPNPP=NPGIXGI<pmX

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


Ekwiwalent GI w ramach redukcji Karp.
Mohammad Al-Turkistany,

1
vzn

2
Wydaje się, że możliwe jest zbudowanie nieskończonej hierarchii takich problemów, łącząc „wystarczającą ilość” Kliki z GI, w wariancie opóźnionej diagonalizacji. Zobacz także podobną konstrukcję sugerowaną przez Bodirsky / Chen / Grohe / Thurley / Weyer.
András Salamon,

Nawiasem mówiąc, możesz zmienić tytuł na „Problem z grafem trudnym dla GI, o którym wiadomo, że nie jest NP-zupełny”. Moją pierwszą myślą, kiedy zobaczyłem obecny tytuł, było „Ring Isomorphism!” ale odpowiedź, którą znalazłeś, jest (myślę) znacznie bardziej interesująca.
Joshua Grochow

@JoshuaGrochow Dziękujemy za opinię. Co sugerujesz? Zauważ, że interesują mnie problemy z wykresem.
Mohammad Al-Turkistany

Odpowiedzi:


8

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}GiGviGvG 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]vertexdeck(G)]}k3

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 .GIGINPk3

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})


0

G1G2npiG1G2

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.