We examine exact algorithms for the NP-complete Graph Bipartization problem, also known as Maximum Bipartite Subgraph or Odd Cycle Transversal.

Graph Bipartization

**Input:** An undirected graph *G = (V, E)* and a nonnegative integer *k*.

**Task:** Find a subset *C ⊆V* of vertices with *|C| ≤ k* such that each odd
cycle in G contains at least one vertex from *C*, that is, the removal
of all vertices in *C* from *G* results in a bipartite graph.

This problem is NP-complete and MaxSNP-hard; the best known
approximation is by a factor of *log |V|*. It has numerous
applications, for example in VLSI design, computational biology, and
register allo-cation.

In a recent breakthrough paper, Reed, Smith, and Vetta proved that the
Graph Bipartization
problem on a graph with *n* vertices and *m* edges is solvable in *O(4 ^{k} ·
kmn)* time, where

In this work we present new algorithms based on iterative compression
and demonstrate that they are a worthwhile alternative for solving
Graph Bipartization in
practice. The worst-case time complexity is improved to *O(3 ^{k} ·
mn)*. We present experimental results with real-world data, synthetic
application data, and random graphs. The implementation can solve all
problems from a testbed from computational biology within minutes,
whereas established methods based on Integer Linear Programming are
only able to solve about half of the problems within reasonable
time. A heuristic yielding optimal solutions performs very well on
dense graphs. These results makes the practical evaluation of
iterative compression for other applications appealing.