Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center

Abstract

In $(k,r)$-Center we are given a (possibly edge-weighted) graph and are asked to select at most $k$ vertices (centers), so that all other vertices are at distance at most $r$ from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically: - For any $r\ge 1$, we show an algorithm that solves the problem in $O^{\ast }((3r+1{)}^{\text{cw}})$ time, where $\text{cw}$ is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithm's performance. As a corollary, for $r=1$, this closes the gap that previously existed on the complexity of Dominating Set parameterized by $\text{cw}$. - We strengthen previously known FPT lower bounds, by showing that $(k,r)$-Center is W[1]-hard parameterized by the input graph's vertex cover (if edge weights are allowed), or feedback vertex set, even if $k$ is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs. - We show that the complexity of the problem parameterized by tree-depth is $2^{\Theta ({\text{td}}^2)}$ by showing an algorithm of this complexity and a tight ETH-based lower bound. We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth which work efficiently independently of the values of $k,r$. In particular, we give algorithms which, for any $\epsilon >0$, run in time $O^{\ast }((\text{tw}/\epsilon {)}^{O(\text{tw})})$, $O^{\ast }((\text{cw}/\epsilon {)}^{O(\text{cw})})$ and return a $(k,(1+\epsilon )r)$-center, if a $(k,r)$-center exists, thus circumventing the problem's W-hardness.

References in corpus (1)

• Parameterized Approximation Schemes using Graph Widths

Cited by in corpus (2)

• New Algorithms for Mixed Dominating Set
• New Results on Directed Edge Dominating Set