Apakah ada algoritma waktu poli untuk menentukan apakah grafik hampir bipartit?

Diberikan grafik G yang tidak terarah, kita dapat mengatakan bahwa G hampir bipartit jika menghapus tepi k (atau simpul) akan membuatnya menjadi bipartit.

Apakah ada algoritma waktu poli untuk menentukan apakah grafik tepat atau kira-kira hampir bipartit?

Versi vertex disebut "siklus ganjil transversal"; ini traktat NP-lengkap tapi parameter tetap. Lihat:

Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete issues", Prosiding Simposium ACM ke-10 tentang Teori Komputasi (STOC '78), hlm. 253–264, hal. 10.1145 / 800133.804355 .

Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Menemukan transversal siklus ganjil", Operations Research Letters, 32 (4): 299–301, doi: 10.1016 / j.orl.2003.10.009 .

Hüffner, Falk (2005), "Rekayasa algoritma untuk bipartisasi grafik yang optimal", Algoritma Eksperimental dan Efisien: 240–252, doi: 10.1007 / 11427186_22 .

Versi tepi telah disebut "edge bipartization"; itu juga NP-complete tetapi fixed-parameter trable. Lihat:

Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Algoritma parameter tetap berbasis kompresi untuk set vertex umpan balik dan bipartisasi tepi", JCSS 72 (8): 1386–1396, doi: 10.1016 / j.jcss.2006.02.001 .

(ditambahkan komentar daniello berikut):

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

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

Khot, S., Tentang kekuatan permainan 1-putaran 1-prover yang unik, STOC '02, hlm. 767-775.

Wernicke, S., Tentang kemampuan penelusuran algoritme analisis nukleotida polimorfisme (SNP) tunggal dan masalah terkait. Tesis Master, Wilhelm-Schickard-Institut für Informatik, U. Tübingen (2003)