Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs
Jochen Alber, Jiřı́ Fiala · 2002
We consider the parameterized problem, whether a given set of n disks (of bounded radius) in the Euclidean plane contains k non-intersecting disks. We expose an algorithm running in time % MathType!MTEF!2!1!+- % feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBamaaCa % aaleqabaGaam4taiaacIcadaGcaaqaaiaadUgaaWqabaWccaGGPaaa % aOGaaiilaaaa!3B12! $${n^{O(\sqrt k )}}, $$ that is—to our knowledge—the first algorithm for this problem with running time bounded by an exponential with a sublinear exponent. The results are based on a new “geometric √∙-separator theorem” which holds for all disk graphs of bounded radius. 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 geometric separator theorem.