Approximating the minimum bisection size (extended abstract)
Uriel Feige, Robert Krauthgamer, Kobbi Nissim · 2000
) Uriel Feige Robert Krauthgamer Kobbi Nissim Deptartment of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot 76100, Israel ffeige,robi,[email protected] February 22, 2000 Abstract A bisection of a graph with n vertices is a partition of its vertices into two sets, each of size n=2. The bisection size is the number of edges connecting the two sets. Finding the bisection of minimum size is NP-hard. We present an algorithm that finds a bisection that is within O( p n log n) of optimal. No sublinear approximation ratio for bisection was previously known. 1 Introduction Let G(V; E) be a graph with n vertices and m edges, where n is even. A bisection of G is a set of vertices S ae V with cardinality jSj = n=2. The size of the bisection S is the number of edges connecting S to its complement V nS. The minimum size of the bisection of a graph is denoted by b. Computing b is NP-hard, cf. [8, 6]. We address the problem of approximating b....