Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite.
Are there poly time algorithms to determine if a graph is exactly or approximately almost bipartite?
8
$\begingroup$
$\endgroup$
-
1$\begingroup$ What do you mean by "approximately almost bipartite"? $\endgroup$ – user6973 Aug 28 '16 at 17:01
-
$\begingroup$ It's np-hard for general $k$ because it's basically the max cut problem. I don't think this is research-level $\endgroup$ – Sasho Nikolov Aug 28 '16 at 18:26
-
$\begingroup$ @RickyDemer I meant that the output could be a 1 + eps approximation of the number of edges or vertices needed to make the graph bipartite for example. I would allow some probability is of error too. $\endgroup$ – Lembik Aug 28 '16 at 19:18
16
$\begingroup$
$\endgroup$
The vertex version is called "odd cycle transversal"; it's NP-complete but fixed-parameter tractable. See:
Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78), pp. 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", Experimental and Efficient Algorithms: 240–252, doi:10.1007/11427186_22.
The edge version has been called "edge bipartization"; it's also NP-complete but fixed-parameter tractable. See:
Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization", JCSS 72 (8): 1386–1396, doi:10.1016/j.jcss.2006.02.001.
(added following daniello's comment):
Odd cycle transversal has an $O(\sqrt{\log n})$ approximation algorithm, but (assuming the Unique Games Conjecture) no constant-factor approximation; see (references copied from "On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal" by Jansen and Kratsch):
Agarwal, Amit, Charikar, Moses, Makarychev, Konstantin, Makarychev, Yury, $O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems, STOC'05, pp. 573–581.
Khot, S., On the power of unique 2-prover 1-round games, STOC '02, pp. 767–775.
Wernicke, S., On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems. Master’s thesis, Wilhelm-Schickard-Institut für Informatik, U. Tübingen (2003)
answered Aug 28 '16 at 19:50
-
$\begingroup$ I seem to remember the problem is also unique games hard to approximate within any constant factor, but don't remember the reference $\endgroup$ – daniello Aug 29 '16 at 6:16
-
$\begingroup$ Thank you for this great answer. Do the hardness results there can be no poly time property testing algorithm even if we allow approximation and randomness? $\endgroup$ – Lembik Aug 29 '16 at 19:46
-
$\begingroup$ Does the largest eigenvalue of the Laplacian give some indication of bipartiteness? $\endgroup$ – Lembik Aug 31 '16 at 14:34
