Tractability and Intractability of Problems on Unit Disk Graphs Parameterized by Domain Area
Hiro Ito, Masakazu Kadoshita · 2010
Abstract This paper treats unit disk graphs whose vertices are located in a square-shaped region with fixed area α, and considers parametrized problems on this model. It shows that “fixed area" is not a trivial restriction by proving that the maximum independent set problem and the minimum dominating set problem are both W[1]-complete for unit disk graphs parameterized by area. On the other hand, it shows an algorithm that solves the Hamiltonian circuit problem in O(m+ p2cp) time, where m is the number of edges, p = 2α + o(α), and c is a constant number, i.e., this problem is FPT for the parameter α. It also shows an algorithm that solves the k-coloring problem in O(kkp) time, i.e., this problem is also FPT for the pair of parameters k and α.