Structural parameters, tight bounds, and approximation for [formula omitted]-center.

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 ≥ 1 , we show an algorithm that solves the problem in O ∗ ( (3 r + 1) cw) time, where 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 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 Θ (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 ϵ > 0 , run in time O ∗ ( (tw ∕ ϵ) O (tw) ) , O ∗ ( (cw ∕ ϵ) O (cw) ) and return a (k , (1 + ϵ) r) -center if a (k , r) -center exists, thus circumventing the problem's W-hardness. [ABSTRACT FROM AUTHOR]