Falk Hüffner: Algorithm Engineering for Optimal Graph Bipartization

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(4k · kmn) time, where k is the number of vertices to delete. The basic idea is to construct size-k solutions from already known size-(k+1) solutions, the so-called iterative compression.

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(3k · 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.