Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set D of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time n(O(rootk)) that is-to our knowledge-the first algorithm with running time bounded by an exponential with a sublinear exponent. For lambda-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time 2(O(rootk)) + n(O(1)). The results are based on problem kernelization and a new "geometric (root(.)-separator) theorem" which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a "geometric problem kernelization" and, in a second step, uses divide-and-conquer based on our new "geometric separator theorem." (C) 2003 Elsevier Inc. All rights reserved.