# Are there poly time algorithms to determine if a graph is almost bipartite?

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?

• What do you mean by "approximately almost bipartite"? ​ ​ – user6973 Aug 28 '16 at 17:01
• It's np-hard for general $k$ because it's basically the max cut problem. I don't think this is research-level – Sasho Nikolov Aug 28 '16 at 18:26
• @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. – Lembik Aug 28 '16 at 19:18

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.

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)

• I seem to remember the problem is also unique games hard to approximate within any constant factor, but don't remember the reference – daniello Aug 29 '16 at 6:16
• 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? – Lembik Aug 29 '16 at 19:46
• Does the largest eigenvalue of the Laplacian give some indication of bipartiteness? – Lembik Aug 31 '16 at 14:34
• A similar, although much simpler (it is polynomial), question is raised here: math.stackexchange.com/questions/3927366/… -- any idea? – Matthieu Latapy Jan 11 at 19:35
• I see Agarwal, Amit, Charikar, Moses, Makarychev, Konstantin, Makarychev, Yury, O(logn−−−−√) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems, STOC'05, pp. 573–581. is doing graph bipartization (edge version) from min uncut does the vertex version also follow? – Hao S Apr 1 at 1:00