Ist das Problem der Rückkopplungsscheitelpunktmenge in der Polynomzeit für 3-Grad-Diagramme lösbar?

19

Das Feedback Vertex Set ist NP-vollständig für allgemeine Diagramme. Es ist bekannt, dass es für Graphen mit Grad-8-Begrenzung aufgrund einer Verringerung der Scheitelpunktabdeckung NP-vollständig ist. Der Wikipedia-Artikel besagt, dass es für Graphen mit Grad-3-Begrenzung polyzeitlösbar und für Graphen mit Grad-4-Begrenzung NP-vollständig ist. Aber ich habe nirgendwo einen Beweis dafür finden können. Ist es wahr?

Was ist das Minimum d, so dass FVS in Graden-d-Graphen NP-vollständig ist?

cc.complexity-theory graph-theory graph-algorithms np-hardness bounded-degree Davis Issac
quelle

1

Weiß jemand, ob das Problem bei Grad 4 regulären ungerichteten Graphen schwer ist?

10

Der Algorithmus von Li und Liu ist falsch (er wurde in China veröffentlicht, allerdings in englischer Sprache). Der Algorithmus von Ueno et al. Ist korrekt, und ein ähnlicher Algorithmus findet sich bei Furst et al. 1 . Beide Algorithmen reduzieren das Problem auf das polynomlösbare Matroid-Paritätsproblem [3].

Durch die Reduzierung von VC wird die NP-Härte für Grades-6-Bounded-Graphen sichergestellt! Da ist VC schon NP-hart an kubischen Graphen. Speckenmeyer hat behauptet, dass seine Dissertation [4] den Beweis der NP-Härte von FVS auf planaren Graphen des vierten Grades enthält, aber es ist sehr schwer zu finden (ich bin sehr dankbar, wenn mir jemand, der Zugang zu seiner Dissertation hat, eine Kopie schicken kann) ). Glücklicherweise gibt es in 2 einen neuen Beweis für die NP-Härte von Graphen mit Grad 4-Begrenzung :

Anmerkungen zu 2 : - Tatsächlich hat er bewiesen, dass das Problem APX-hart ist, aber es ist leicht zu überprüfen, dass seine Reduktionen auch für den Nachweis der NP-Härte des Problems gültig sind. - Die Reduzierung gilt NICHT für ebene Graphen.

Merrick L. Furst, Jonathan L. Gross und Lyle A. McGeoch, "Finding a Maximum-Genus-Graph-Einbettung", Journal of the ACM, vol. 35, nein. 3, S. 523–534, 1988. 10.1145 / 44483.44485
Rizzi, R .: Schwach fundamentale Kreislaufbasen sind schwer zu finden. Algorithmica 53 (3), 402-424 (2009) 10.1007 / s00453-007-9112-8
László Lovász, "Das Matroid Matching Problem", in Algebraic Methods in Graph Theory, ser. Colloquia Mathematica Societatis János Bolyai, vol. 25, Szeged, Hungary, 1980, S. 495–517.
Ewald Speckenmeyer, „Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen“, Dissertation, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.

Yixin Cao
quelle

9

Gibt es einen einfachen Grund, warum es "eindeutig falsch" ist?

Suresh Venkat

2

M

$M$

{e_{1}, e_{2}}

$\{e_1,e_2\}$

M^{'}

$M'$

M

$M$

M

$M$

{e_{1}, e_{2}}

$\{e_1,e_2\}$

M

$M$

Yixin Cao

M

$M$

v

$v$

M^{'}

$M'$

v

$v$

M

$M$

9

Die relevanten Referenzen scheinen zu sein:

Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya. Auf dem nicht trennenden Problem der unabhängigen Menge und dem Problem der Rückkopplungsmenge für Graphen, deren Scheitelpunktgrad drei nicht überschreitet. Tagungsband der Ersten Japanischen Konferenz über Graphentheorie und -anwendungen (Hakone, 1986). Diskrete Mathematik. 72 (1988), no. 1-3, 355–360 .

Li, Deming; Liu, Yanpei. Ein Polynomalgorithmus zum Ermitteln der minimalen Rückkopplungsscheitelmenge eines einfachen 3-regulären Graphen. Acta Math. Sci. 19 (1999), no. 4, 375–381.

(Warnung: Ich habe keines von beiden gelesen, aber beide behaupten, das Problem in Polynomzeit zu lösen. Ich halte den Unterschied zwischen 3-regulären und maximalen Grad drei für nicht wichtig für dieses Problem.)

David Eppstein
quelle

Ist das Problem der Rückkopplungsscheitelpunktmenge in der Polynomzeit für 3-Grad-Diagramme lösbar?

Antworten: