Was ist die Komplexität dieses Max-Edge-Subgraph-Problems?

Während ich die Frage diskutiere, die ich hier gestellt habe , stoßen @NealYoung und ich auf ein anderes Problem, nämlich die Beurteilung der Komplexität des folgenden Problems:

Bei einem verbundenen ungerichteten Graphen wird eine Teilmenge der Kanten mit maximaler Größe gefunden, sodass jeder Scheitelpunkt höchstens zwei Grad hat.

Ich habe ein Papier über die Komplexität relativer Probleme gefunden. Die meisten von ihnen haben dem Original mehr Einschränkungen hinzugefügt. FOS03 fügte "ohne ungerade Zyklen" hinzu und bewies, dass es NP-hart ist. CTW07 implizierte, dass die Variante "ohne 3-Zyklus" P ist und sich auf ein anderes Papier bezieht (das ich nicht gefunden habe). Aber ich konnte die Komplexität des ursprünglichen Problems nicht beurteilen. Wie kann man das beurteilen? Vielen Dank.

graph-theory np-hardness cc.complexity-theory RIC_Eien
quelle

Antworten:

Das verallgemeinerte Problem (so dass jeder Scheitelpunkt höchstens einen Grad ) wird als Übereinstimmungsproblem bezeichnet. Kapitel 31 von Schrijvers Buch ist dem Thema gewidmet. Es kann in stark polynomieller Zeit gelöst werden. $v$ $b_v$ $b$

Der Fall, dass für jeden Scheitelpunkt ist, wurde untersucht, insbesondere um Untergrenzen für das Problem des reisenden Verkäufers bereitzustellen . $b_v=2$ $v$

Austin Buchanan
quelle

Ja, ich sehe. Vielen Dank für Ihre Antwort! Vielleicht können Sie auch einen Vorschlag zu der oben verlinkten früheren Frage machen?

RIC_Eien

@ RIC_Eien: Mein Kommentar ist nicht wirklich ernst, aber es scheint, dass Sie mit der Antwort sehr zufrieden sind. Wenn ja, warum können Sie das nicht akzeptieren?

user13667