Parameterized Tractability and Kernelization of Problems on Unit Disk Graphs

Unit disk graphs are used extensively in the field of networks in order to model the infrastructure of ad hoc wireless communication networks. Development of efficient algorithms for problems on unit disk graphs has therefore been a hot topic largely driven by the practical applications. This is while there are no general frameworks known in the literature for obtaining parameterized algorithms or kernelization results on UDGs. Clique Partition is one of the Richard Karp's original 21 NP-hard problems and is proved to be an extremely useful tool for obtaining solutions for other fundamental combinatorial problems such as Dominating Set, UDG Realization and Facility Location. We make the following contributions in this thesis: (1) We develop a novel framework for obtaining parameterized and FPT algorithms for Clique Partition and related problems on UDGs. (2) We bridge the complexity gap between the UDG and precision UDG classes through introducing a new useful subclass, namely quasi-precision UDGs, with interesting properties. We further describe (relaxed)-quasi-precision UDGs by proving structural properties for the subclass and classify the cases when the problems do not admit FPT algorithms under our framework. (3) We propose a new approach for constructing polynomial approximation schemes (PTAS) for Minimum Clique Partition on UDGs which results in significant computational speed-up comparing to the best previously known PTAS for the problem. (4) We introduce first-time data reduction rules for the problems of Clique Partition and Weighted Clique Partition and enhanced data reduction rules for Clique Cover on UDGs. (5) We develop a framework for obtaining linear-size kernels on quasi-precision UDGs and provide the sufficient criteria for the problems under which the framework applies.