Parameterized Algorithms for Computing r-Scattered Sets and r-Dominating Sets on Unit Disk Graphs

Abstract

We study the r-scattered set problem and the r-dominating set problem defined on the unit disk graph on the 2-dimensional Euclidean plane. They are the generalized version of the independent set problem and the dominating set problem, respectively. Our main result is that the r-scattered set problem on the unit disk graph can be solved in n^O(k) time. Also, we show that the r-dominating set problem on the unit disk graph can be solved in n^O(k) time if the input graph has a unique-neighbored r-dominating set of size k. The algorithm is based on the concept of partitioning the plane with a hypothetical solution of k vertices. It is known that there exists a closed curve separating the solution vertices in a balanced manner if the degree of every vertex in the partition is three. Then it is possible to guess the correct solution by listing the balanced separators of the partition to obtain subproblems of balanced size.