Gibt es ein Problem, das für kubische Grafiken einfach, für Grafiken mit maximalem Grad 3 jedoch schwierig ist?

22

Kubische Graphen sind Graphen, bei denen jeder Scheitelpunkt Grad 3 hat. Sie wurden eingehend untersucht, und ich bin mir bewusst, dass einige NP-harte Probleme auch auf Unterklassen von kubischen Graphen beschränkt bleiben, andere jedoch einfacher werden. Eine Superklasse von kubischen Graphen ist die Klasse von Graphen mit maximalem Grad .Δ≤3

Gibt es ein Problem, das in der Polynomzeit für kubische Graphen gelöst werden kann, das jedoch für Graphen mit maximalem Grad NP-schwer ist ?Δ≤3

graph-theory graph-algorithms np-hardness Vinicius dos Santos
quelle
2
Eine entartete Antwort, die zeigt, dass es unterschiedliche Komplexitäten geben kann (obwohl keine NP-schwer ist): Das Finden von ist eine konstante Zeit in kubischen Graphen, aber linear in Graphen mit . :-)δΔ≤3
William Macrae
Guter Punkt. :-)
Vinicius dos Santos
Bei einer schlechten Auswahl von Kodierungen kann es sogar hart sein, wenn , aber es ist viel wertvoller, ein Problem zu finden, das nicht auf einer schlechten Kodierung beruht, und noch besser, wenn dieses Problem ein gutes ist. studierte eine. NPΔ≤3
William Macrae
1
Um Williams Kommentar zu erweitern, hier ist ein künstliches Problem. Stellt die Gradfolge von , die als Codierung einer Instanz von 3-SAT interpretiert wird, in einem Graphen eine erfüllbare Instanz dar? GGG n (Angenommen, die Kodierung ist so, dass die Sequenz mit allen drei Graden eine zufriedenstellende Zuordnung für jede .) :-)n
Neal Young,
Weitere Anregungen finden Sie auch unter cstheory.stackexchange.com/questions/1215/… .
Jukka Suomela

Antworten:

21

Hier ist eine einigermaßen natürliche: Bestimmen Sie an einer Eingabe , ob G einen verbundenen regulären Teilgraphen mit mindestens k Kanten hat. Für 3-reguläre Graphen ist dies trivial, aber wenn der maximale Grad 3 ist und die Eingabe verbunden ist, kein Baum und nicht regulär, dann ist der größte solche Subgraph der längste Zyklus, so dass das Problem NP-vollständig ist.(G,k)Gk

David Eppstein
quelle
"... dann ist die Lösung entweder der längste Zyklus oder eine maximale Übereinstimmung ...". Wie hängt Ihr Anspruch von k ab? Es ist nicht für alle k wahr.
Tyson Williams
1
@Tyson, es muss nur schwer sein, damit ein schwer ist, oder? ZB nehme k = n . David, müssen Sie festlegen, dass der Subgraph verbunden werden soll? (Andernfalls weist jede Zyklusabdeckung (nicht nur ein Hamilton-Zyklus) n Kanten auf, und die Bestimmung der Existenz einer Zyklusabdeckung erfolgt in S. )kk=nnP
Neal Young,
1
David, eine maximale Übereinstimmung (mit einer Größe größer als 1) in G ist kein zusammenhängender Untergraph von G. Wollen Sie sagen, "... entweder der längste Zyklus oder eine einzelne Kante, ..."?
Tyson Williams
2
OK OK. Heute scheint mir kein guter Tag zu sein, um rigoros zu sein - wahrscheinlich zu viel Truthahn. Ich habe eine Sprache hinzugefügt, um diesen Sonderfall auszuschließen.
David Eppstein
3
@YininCao Da der Graph verbunden, aber nicht regulär ist, gibt es keine Möglichkeit, einen 3-regulären Subgraphen auszuwählen. Angenommen, es wäre so. Dann gibt es einen Scheitelpunkt, der nicht ausgewählt wurde, da der Graph nicht regelmäßig ist. Da der Graph verbunden ist, ist dieser Vertex mit einem ausgewählten 3-regulären Vertex verbunden. Das heißt aber, es gibt einen Scheitelpunkt 4. Grades, einen Widerspruch.
Tyson Williams