The (k, r)-center problem asks whether an input graph
G has ≤ k vertices (called centers) such
that every vertex of G is within distance ≤ r from some
center. In this paper we prove that the (k, r)-center
problem,
parameterized by k and r, is fixed-parameter tractable (FPT)
on planar graphs,
i.e., it admits an algorithm of complexity f(k, r) nO(1) where the function
f is independent of n. In particular, we show that
f(k, r) = 2O(r log r) √k, where the exponent
of the exponential term grows sublinearly in the number of centers.
Moreover, we prove that the same type of FPT
algorithms can be designed for the more general class of
map graphs introduced by Chen, Grigni, and Papadimitriou.
Our results combine dynamic-programming algorithms for
graphs of small branchwidth and a graph-theoretic result bounding
this parameter in terms of k and r. Finally, a byproduct of
our algorithm is the existence of a PTAS for the r-domination
problem in both planar graphs and map graphs.
Our approach builds on the seminal results of Robertson and
Seymour on Graph Minors, and as a result is much more powerful
than the previous machinery of Alber et al. for exponential
speedup on planar graphs. To demonstrate the versatility of our
results, we show how our algorithms can be extended to general
parameters that are “large” on grids. In addition, our use of
branchwidth instead of the usual treewidth allows us to obtain
much faster algorithms, and requires more complicated dynamic
programming than the standard leaf/introduce/forget/join structure
of nice tree decompositions. Our results are also unique in that
they apply to classes of graphs that are not minor-closed, namely,
constant powers of planar graphs and map graphs.