Powszechny wgląd w hipotetyczną złożoność problemów graficznych

Natknąłem się na dwa przykłady hipotetycznej twardości niektórych problemów graficznych. Hipotetyczna twardość oznacza, że ​​obalenie niektórych przypuszczeń oznaczałoby zupełność NP odpowiedniego problemu grafowego. Na przykład, hipoteza Barnette'a stwierdza, że ​​każdy 3-połączony sześcienny dwuwymiarowy wykres jest hamiltonianem. Feder i Subi udowodnili, że obalenie przypuszczenia oznaczałoby zupełność NP problemu cyklu hamiltonowskiego na wykresach w klasie przypuszczeń.

5-przepływowa hipoteza Tutte'a stwierdza, że ​​każdy wykres bez mostka ma 5-przepływ nigdzie zerowy. Kochol wykazał, że jeśli hipoteza jest fałszywa, to problem ustalenia, czy wykres sześcienny dopuszcza zerowy przepływ 5, jest NP-zupełny .

Czy istnieją wspólne spostrzeżenia na temat powyższych przypuszczeń, które wyjaśniają hipotetyczną kompletność NP odpowiednich problemów graficznych? Czy istnieją inne przykłady hipotetycznej złożoności w powyższym znaczeniu?

PS To zostało opublikowane na MathoverFlow bez odpowiedzi.

Oto dwa odniesienia do drugiej części pytania.

$g$$g$$g$
$4k$$C_{2k+1}$$g$

$k$$f(k)$$(k,f(k))$$k$$f(k)$$(k,f(k)+1)$$f(k)$ wydaje się nieznane, chociaż podano pewne dane szacunkowe.)

[1] L. Esperet, M. Montassier, P. Ochem i A. Pinlou. Dychotomia złożoności do barwienia rzadkich wykresów. Journal of Graph Theory 73: 85-102, 2012. link + PDF na stronie autora

[2] J. Kratochvil, P. Savicky i Zs. Tuza. Jeszcze jedno wystąpienie zmiennych powoduje, że satysfakcjonujący skok z trywialnego do NP-zupełnego. SIAM Journal on Computing 22: 203-210, 1993. link

Czy istnieją wspólne spostrzeżenia na temat powyższych przypuszczeń, które wyjaśniają hipotetyczną kompletność NP odpowiednich problemów graficznych?

$O(1)$

Powszechnie wiadomo, że problemy naturalne, cykl Hamiltona i nigdzie zerowy przepływ na ogólnych wykresach, są „uporządkowane i potężne” wystarczająco, aby skutecznie „symulować” ślad maszyny Turinga (à la Cook-Levin). Następnie zaczynasz dodawać coraz więcej ograniczeń, dopóki nie uzyskasz „mocy obliczeniowej”.

Dla mnie jest to jak dodawanie coraz większej liczby ograniczeń do wykresu przejścia maszyny Turinga (lub urządzenia do odczytu / zapisu na taśmie), dopóki nie pojawi się coś trywialnego, takiego jak „wykres przejścia nie zawiera cyklu”.

Czy istnieją inne przykłady hipotetycznej złożoności w powyższym znaczeniu?

Jako (prawdopodobnie) „rozwiązany przypadek” mogę wnieść swoje doświadczenie związane z problemem Rzut kością na problem z tabliczką z etykietami .

Kilka lat temu nie było wiadomo, czy w pełni oznakowane tablice mogą zawierać dwa odrębne cykle Hamiltonaina ( ustalono jednoznacznie przypuszczalną hipotezę dla wszystkich desek o długości boku co najwyżej 8). Domotor P. (tutaj użytkownik domotorp) i ja (niezależnie) udowodniliśmy, że takie tablice istnieją, a domysł jest fałszywy (... zauważ, że Joseph O'Rourke nie zaktualizował jeszcze swojej strony :-).

Korzystając z tego faktu, byłem w stanie udowodnić, że toczenie matrycy na całkowicie oznakowaną deskę z otworami jest NP-ukończone ( obudowa bez otworów jest nadal otwarta); chociaż jest to niepublikowany wynik.