Polynomial Kernels for Hard Problems on Disk Graphs

摘要

Kernelization is a powerful tool to obtain fixed-parameter tractable algorithms. Recent breakthroughs show that many graph problems admit small polynomial kernels when restricted to sparse graph classes such as planar graphs, bounded-genus graphs or H-minor-free graphs. We consider the intersection graphs of (unit) disks in the plane, which can be arbitrarily dense but do exhibit some geometric structure. We give the first kernelization results on these dense graph classes. CON-NECTED VERTEX COVER has a kernel with 12k vertices on unit-disk graphs and with 3k~2 + 7k vertices on disk graphs with arbitrary radii. RED-BLUE DOMINATING SET parameterized by the size of the smallest color class has a linear-vertex kernel on planar graphs, a quadratic-vertex kernel on unit-disk graphs and a quartic-vertex kernel on disk graphs. Finally we prove that H-MATCHING on unit-disk graphs has a linear-vertex kernel for every fixed graph H.