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$
  • 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
15
$\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$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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