Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote · 2008
We study the parameterized complexity of the k-center problem on an given n-point set P in Rd, with the dimension d as the parameter. We show that the rectilinear 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in O(n log n) time for any fixed dimension d. On the other hand, we show that this is unlikely to be the case with both the Euclidean and rectilinear k-center problems for any k ≥ 2 and k ≥ 4 respectively. In particular, we prove that deciding whether P can be covered by the union of 2 balls of given radius or by the union of 4 cubes of given side length is W[1]-hard with respect to d, and thus not fixed-parameter tractable unless FPT=W[1]. For the Euclidean case we also show that even an no(d)-time algorithm does not exist, unless there is a 2o(n)-time algorithm for n-variable 3SAT, i.e., the Exponential Time Hypothesis fails.