8
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ What do you mean by "approximately almost bipartite"? ​ ​ $\endgroup$
    – user6973
    Commented Aug 28, 2016 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$ Commented Aug 28, 2016 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$
    – Simd
    Commented Aug 28, 2016 at 19:18

1 Answer 1

16
$\begingroup$

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)

$\endgroup$
5
  • $\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
    Commented Aug 29, 2016 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$
    – Simd
    Commented Aug 29, 2016 at 19:46
  • $\begingroup$ Does the largest eigenvalue of the Laplacian give some indication of bipartiteness? $\endgroup$
    – Simd
    Commented Aug 31, 2016 at 14:34
  • $\begingroup$ A similar, although much simpler (it is polynomial), question is raised here: math.stackexchange.com/questions/3927366/… -- any idea? $\endgroup$ Commented Jan 11, 2021 at 19:35
  • $\begingroup$ 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? $\endgroup$
    – Hao S
    Commented Apr 1, 2021 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.