Finding small balanced separators

Let G be an n-vertex graph that has a vertex separator of size k that partitions the graph into connected components of size smaller than α n, for some fixed 2/3 ≤ α < 1. Such a separator is called an α-separator. Finding an α-separator of size at most k is NP-hard. Moreover, under reasonable complexity theoretic assumptions, it is shown that this problem is not polynomially solvable even when k=O(log n). In this paper, we give a randomized algorithm that finds an α-separator of size k in the given graph, unless the graph contains an (α+ε)-separator of size strictly less than k, in which case our algorithm finds one such separator. For fixed ε, the running time of our algorithm is n O(1) 2 O(k) , which is polynomial for k = O(log n). For bounded degree graphs (as well as for the case of finding balanced edge separators), we present a deterministic algorithm with similar running time.Our algorithm involves (among other things) a new concept that we call (ε,k)-samples. This is related to the notion of detection sets for network failures, introduced by Kleinberg [FOCS 2000]. Our proofs adapt and simplify techniques that were introduced by Kleinberg. As a by-product, our proof improves the known bounds on the size of detection sets. We also show applications of (ε,k)-samples to problems in approximation algorithms and rigorous analysis of heuristics.

Authors

• Uriel Feige
• Mohammad Mahdian

Keywords

• VC dimension
• fixed parameter tractability