Kann ein natürliches Graphproblem allgemein schwierig sein?

Gibt es ein natürliches vollständiges Graphproblem, das N P- vollständig bleibt, selbst wenn es auf eine in der Polynomzeit erkennbare Graphklasse beschränkt ist? Um degenerierte Fälle zu vermeiden, betrachten wir nur dichte Graphenklassen, in denen die Anzahl der nicht isomorphen ≤ n- Vertex-Graphen exponentiell mit n wächst .$\mathsf{NP}$$\mathsf{NP}$$\leq n$$n$

Anmerkungen:

(1) Sowohl eine "Ja" - als auch eine "Nein" -Antwort wäre sehr interessant. Wenn die Antwort ja lautet, hätten wir eine natürliche -vollständige Grapheneigenschaft, die als universell hart bezeichnet werden könnte, da sie die Härte auch dann beibehält, wenn sie auf eine vernünftige Graphklasse beschränkt ist. Wenn die Antwort Nein lautet, würde dies bedeuten, dass jede natürliche N P -vollständige Diagrammeigenschaft für eine nichttriviale Diagrammklasse einfach gemacht werden kann.$\mathsf{NP}$$\mathsf{NP}$

(2) Es ist wichtig, nur polynomialzeiterkennbare Graphklassen zu berücksichtigen, um auszuschließen, dass die Härte der Eigenschaft einfach auf die Klasse verschoben wird. Beispielsweise wird die 3-FARBBARKEIT trivial, wenn sie auf 3-färbbare Diagramme beschränkt wird.

Die Definition von "natürlich" ist etwas verschwommen, aber es gibt einen trivialen Grund, warum die Antwort hier wahrscheinlich "nein" ist. Angenommen , im Gegenteil , dass es ein solches Problem, . Wenn P nur auf die erste Komponente des bereitgestellten Graphen einwirkt, ist P für die Klasse von Graphen einfach, bei der die erste Komponente eine Instanz von P ist und die zweite Komponente ein Zertifikat von P codiert , das die erste Komponente enthält. Ferner ist diese Klasse von Graphen polytime erkennbar. Dies gilt auch dann, wenn wir einen Teil des Diagramms als "Dies ist ein Zertifikat und nicht Teil der Problemkomponente" bezeichnen können, in dem Sinne, dass wir dieses Zertifikat einschleichen können, ohne die wahre Antwort zu beeinflussen.$P$$P$$P$$P$$P$

Die meisten "natürlichen" Probleme erlauben, soweit ich das beurteilen kann, die Bezeichnung eines solchen Teils des Diagramms. Hier einige Beispiele

• Max Clique: Stellen Sie einfach sicher, dass der Zertifikatteil des Diagramms keine große Clique hat (z. B. codieren Sie ihn mit einem Matching).
• Hamilton-Pfad: Der Endknoten wird durch ein Zertifikatdiagramm ersetzt, das über einen eigenen leicht zu findenden Hamilton-Pfad verfügt
• Hamilton-Schaltung: Wie Hamilton-Pfad, außer dass ein bestimmter Scheitelpunkt durch einen Zertifikatsgraphen ersetzt wird, der einen Hamilton-Zyklus enthält
• Maximaler Schnitt: Dies wirkt sich nicht auf die Lösung aus, solange der Rest des Diagramms keine Kanten aufweist. Wir stellen daher nur sicher, dass der maximale Schnitt hier leicht zu finden ist (z. B. codieren wir mit einem Matching).
• Vertex-Abdeckung: Das Zertifikat wird erneut durch einen Abgleich codiert

Wir stellen sicher, dass der Zertifikatsteil des Diagramms als solches gekennzeichnet ist, damit er im Rest des Diagramms nicht verloren geht (obwohl es für die meisten "natürlichen" Probleme wahrscheinlich einfach genug ist, sie implizit über die Diagrammstruktur zu bestimmen).

$P=NP$