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.
vc dimension fixed parameter tractability