On the complexity of finding balanced oneway cuts

✍ Scribed by Uriel Feige; Orly Yahalom

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 88 KB
• Volume: 87
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(03)00251-5

✦ Synopsis

A bisection of an n-vertex graph is a partition of its vertices into two sets S and T , each of size n/2. The bisection cost is the number of edges connecting the two sets. In directed graphs, the cost is the number of arcs going from S to T . Finding a minimum cost bisection is NP-hard for both undirected and directed graphs. For the undirected case, an approximation of ratio O(log 2 n) is known. We show that directed minimum bisection is not approximable at all. More specifically, we show that it is NP-hard to tell whether there exists a directed bisection of cost 0, which we call oneway bisection. In addition, we study the complexity of the problem when some slackness in the size of S is allowed, namely, (1/2ε)n |S| (1/2 + ε)n. We show that the problem is solvable in polynomial time when ε = (1/ log n), and provide evidence that the problem is not solvable in polynomial time when ε = o(1/(log n) 4 ).