Gemeinsame Einblicke in die hypothetische Komplexität von Graphproblemen

Ich bin auf zwei Beispiele für die hypothetische Härte einiger Graphprobleme gestoßen. Hypothetische Härte bedeutet, dass das Widerlegen einer Vermutung die NP-Vollständigkeit des jeweiligen Graphproblems implizieren würde. Zum Beispiel besagt Barnets Vermutung , dass jeder 3-verbundene kubische planare zweigliedrige Graph Hamiltonian ist. Feder und Subi haben bewiesen, dass das Widerlegen der Vermutung die NP-Vollständigkeit des Hamiltonschen Zyklusproblems auf Graphen in der Klasse der Vermutung implizieren würde.

Tuttes 5-Flow-Vermutung besagt, dass jeder brückenlose Graph einen Nirgendwo-Null-5-Flow hat. Kochol zeigte, dass das Problem der Bestimmung, ob ein kubischer Graph einen Nirgendwo-Null-5-Fluss zulässt, NP-vollständig ist , wenn die Vermutung falsch ist .

Gibt es gemeinsame Einblicke in die obigen Vermutungen, die die hypothetische NP-Vollständigkeit der entsprechenden Graphprobleme erklären? Gibt es andere Beispiele für hypothetische Komplexität im obigen Sinne?

PS Dies wurde auf MathoverFlow gepostet, ohne eine Antwort zu erhalten.

Hier sind zwei Referenzen für den zweiten Teil Ihrer Frage.

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

$k$$f(k)$$(k,f(k))$$k$$f(k)$$(k,f(k)+1)$$f(k)$ scheint unbekannt, obwohl eine Schätzung gegeben ist.)

[1] L. Esperet, M. Montassier, P. Ochem und A. Pinlou. Eine Komplexitätsdichotomie für die Färbung spärlicher Graphen. Journal of Graph Theory 73: 85-102, 2012. Link + PDF auf der Website eines Autors

[2] J. Kratochvil, P. Savicky und Zs. Tuza. Ein weiteres Auftreten von Variablen führt dazu, dass die Erfüllbarkeit von trivial zu NP-vollständig springt. SIAM Journal on Computing 22: 203-210, 1993. Link

Gibt es gemeinsame Einblicke in die obigen Vermutungen, die die hypothetische NP-Vollständigkeit der entsprechenden Graphprobleme erklären?

$O(1)$

Und die allgemeine Erkenntnis ist, dass die natürlichen Probleme, der Hamilton-Zyklus und der Nirgendwo-Null-Fluss in allgemeinen Graphen, "gestreift und leistungsfähig" genug sind, um die Spur einer Turing-Maschine (à la Cook-Levin) effizient zu "simulieren". Dann fügen Sie immer mehr Einschränkungen hinzu, bis Sie überhaupt keine "Rechenleistung" mehr erhalten.

Für mich ist es so, als würde man dem Übergangsgraphen einer Turing-Maschine (oder dem Lese- / Schreibbandgerät) immer mehr Einschränkungen hinzufügen, bis man etwas Triviales wie "Der Übergangsgraph enthält keinen Zyklus" erhält.

Gibt es andere Beispiele für hypothetische Komplexität im obigen Sinne?

Als (wahrscheinlich) "gelöster Fall" kann ich meine Erfahrungen im Zusammenhang mit dem Problem " Rollen eines Würfels über ein beschriftetes Brett " einbringen .

Vor einigen Jahren war nicht bekannt, ob vollständig beschriftete Bretter zwei unterschiedliche Hamiltonain-Zyklen enthalten können ( für alle Bretter mit höchstens 8 Seitenlängen wurde eine eindeutig rollbare Vermutung aufgestellt ). Domotor P. (Benutzer domotorp hier) und ich (unabhängig) haben bewiesen, dass solche Boards existieren und die Vermutung falsch ist (... beachten Sie, dass Joseph O'Rourke seine Seite noch nicht aktualisiert hat :-).

Mit dieser Tatsache konnte ich dann beweisen, dass das Walzen eines Stempels auf einer vollständig beschrifteten Platte mit Löchern NP-vollständig ist (das Gehäuse ohne Löcher ist noch offen). Dies ist jedoch ein unveröffentlichtes Ergebnis.