Combinatorial approximation algorithms for the maximum directed cut problem
Eran Halperin, Uri Zwick · 2001
We describe several combinatorial algorithms for the maximum directed cut problem. Among our results is a simple linear time 9/20-approximation algorithm for the problem, and a somewhat slower 1/2-approximation algorithm that uses a bipartite matching routine. No better combinatorial approximation algorithms are known even for the easier maximum cut problem for undirected graphs. Our algorithms do not use linear programming, nor semidefinite programming. They are based on the observation that the maximum directed cut problem is equivalent to the problem of finding a maximum independent set in the line graph of the input graph, and that the linear programming relaxation of the problem is equivalent to the problem of finding a maximum fractional independent set of that line graph. The maximum fractional independent set problem can be easily reduced to a bipartite matching problem. As a consequence of this relation, we also get that the maximum directed cut problem for bipartite digraphs can be solved in polynomial time.