TY - CHAP

T1 - Fixed-parameter algorithms for the (k, r)-center in planar graphs and map graphs

AU - Demaine, Erik D.

AU - Fomin, Fedor V.

AU - Hajiaghayi, Mohammad Taghi

AU - Thilikos, Dimitrios M.

PY - 2003

Y1 - 2003

N2 - 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)n O(1) where the function f is independent of n. In particular, we show that f (k,r) = 2O(rlogr)√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 branch-width 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 branch-width 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.

AB - 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)n O(1) where the function f is independent of n. In particular, we show that f (k,r) = 2O(rlogr)√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 branch-width 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 branch-width 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.

UR - http://www.scopus.com/inward/record.url?scp=35248842524&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248842524&partnerID=8YFLogxK

U2 - 10.1007/3-540-45061-0_65

DO - 10.1007/3-540-45061-0_65

M3 - Chapter

AN - SCOPUS:35248842524

SN - 3540404937

SN - 9783540404934

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 829

EP - 844

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Baeten, Jos C. M.

A2 - Lenstra, Jan Karel

A2 - Parrow, Joachim

A2 - Woeginger, Gerhard J.

PB - Springer Verlag

ER -