Gibt es Poly-Time-Algorithmen, um festzustellen, ob ein Graph fast zweiteilig ist?

Bei einem ungerichteten Graphen G können wir sagen, dass G fast zweiteilig ist, wenn das Löschen von k Kanten (oder Eckpunkten) es zweigeteilt machen würde.

Gibt es Poly-Time-Algorithmen, um festzustellen, ob ein Graph genau oder ungefähr fast zweiteilig ist?

Die Scheitelpunktversion wird als "ungerader Zyklustransversal" bezeichnet. Es ist NP-vollständig, aber mit festen Parametern nachvollziehbar. Sehen:

Yannakakis, Mihalis (1978), "NP-vollständige Probleme beim Löschen von Knoten und Kanten", Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78), S. 253–264, doi: 10.1145 / 800133.804355 .

Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding Odd Cycle Transversals", Operations Research Letters, 32 (4): 299–301, doi: 10.1016 / j.orl.2003.10.009 .

Hüffner, Falk (2005), "Algorithm Engineering for Optimal Graph Bipartization", Experimentelle und Effiziente Algorithmen: 240–252, doi: 10.1007 / 11427186_22 .

Die Edge-Version wurde als "Edge-Bipartization" bezeichnet. Es ist auch NP-vollständig, aber mit festen Parametern nachvollziehbar. Sehen:

Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Komprimierungsbasierte Algorithmen mit festen Parametern für die Rückkopplungsscheitelpunktmenge und Kantenbipartisierung", JCSS 72 (8): 1386–1396, doi: 10.1016 / j.jcss.2006.02.001 .

(hinzugefügt nach Daniellos Kommentar):

$O(\sqrt{\log n})$

$O(\sqrt{\log n})$

Khot, S., Über die Kraft einzigartiger 2-Prover-1-Runden-Spiele, STOC '02, S. 767–775.

Wernicke, S., Zur algorithmischen Traktierbarkeit der SNP-Analyse (Single Nucleotide Polymorphism) und verwandten Problemen. Masterarbeit, Wilhelm-Schickard-Institut für Informatik, U. Tübingen (2003)