<p>The vertex version is called "odd cycle transversal"; it's NP-complete but fixed-parameter tractable. See:</p>

<p>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, <a href="http://doi.org/10.1145/800133.804355">doi:10.1145/800133.804355</a>.</p>

<p>Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals", Operations Research Letters, 32 (4): 299–301, doi:<a href="http://doi.org/10.1016/j.orl.2003.10.009">10.1016/j.orl.2003.10.009</a>.</p>

<p>Hüffner, Falk (2005), "Algorithm engineering for optimal graph bipartization", Experimental and Efficient Algorithms: 240–252, <a href="http://doi.org/10.1007/11427186_22">doi:10.1007/11427186_22</a>.</p>

<p>The edge version has been called "edge bipartization"; it's also NP-complete but fixed-parameter tractable. See:</p>

<p>Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization", <em>JCSS</em> 72 (8): 1386–1396, <a href="http://doi.org/10.1016/j.jcss.2006.02.001">doi:10.1016/j.jcss.2006.02.001</a>.</p>

<p>(added following daniello's comment):</p>

<p>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):</p>

<p>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.</p>

<p>Khot, S., On the power of unique 2-prover 1-round games, STOC '02, pp. 767–775.</p>

<p>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)</p>

CC BY-SA 3.0
2016-08-29T06:16:04.743Z
I seem to remember the problem is also unique games hard to approximate within any constant factor, but don't remember the reference
daniello
CC BY-SA 3.0
2016-08-29T19:46:32.527Z
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?
Simd
CC BY-SA 3.0
2016-08-31T14:34:52.713Z
Does the largest eigenvalue of the Laplacian give some indication of bipartiteness?
Simd
CC BY-SA 4.0
2021-01-11T19:35:32.173Z
A similar, although much simpler (it is polynomial), question is raised here: https://math.stackexchange.com/questions/3927366/check-whether-a-given-graph-is-bipartite-except-for-one-edge/ -- any idea?
Matthieu Latapy
CC BY-SA 4.0
2021-04-01T01:00:40.297Z
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
CC BY-SA 3.0
2016-08-28T19:50:44.660Z
2016-08-29T19:22:51.417Z
2016-08-29T19:22:51.417Z
David Eppstein
<p>Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite.  </p>

<p>Are there poly time algorithms to determine if a graph is exactly or approximately almost bipartite?</p>

CC BY-SA 3.0
2016-08-28T18:26:40.643Z
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
CC BY-SA 3.0
2016-08-28T19:18:49.410Z
@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.
Simd
<ds.algorithms><graph-theory>
Are there poly time algorithms to determine if a graph is almost bipartite?
Simd
# Are there poly time algorithms to determine if a graph is almost bipartite?

(Asked by: username_0 on 2016-08-28)

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?

**Tags:** ds.algorithms, graph-theory
> **Comments:**
> **username_1**: It's np-hard for general $k$ because it's basically the max cut problem. I don't think this is research-level  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2016-08-28. Score: 16 | Accepted answer

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](http://doi.org/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](http://doi.org/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](http://doi.org/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](http://doi.org/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)

> **Comments:**
> **username_3**: I seem to remember the problem is also unique games hard to approximate within any constant factor, but don't remember the reference  
> **username_0**: 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?  
> **username_0**: Does the largest eigenvalue of the Laplacian give some indication of bipartiteness?  
> **username_4**: A similar, although much simpler (it is polynomial), question is raised here: https://math.stackexchange.com/questions/3927366/check-whether-a-given-graph-is-bipartite-except-for-one-edge/ -- any idea?  
> **username_5**: 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?  

---

