Abstract
In (k,r)Center we are given a (possibly edgeweighted) 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 finegrained 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*((3r+1)^cw) time, where cw is the cliquewidth 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 ETHbased lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs.
 We show that the complexity of the problem parameterized by treedepth is 2^Theta(td^2) by showing an algorithm of this complexity and a tight ETHbased lower bound.
We complement these mostly negative results by providing FPT approximation schemes parameterized by cliquewidth 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*((tw/epsilon)^O(tw)), O*((cw/epsilon)^O(cw)) and return a (k,(1+epsilon)r)center, if a (k,r)center exists, thus circumventing the problem's Whardness.
BibTeX  Entry
@InProceedings{katsikarelis_et_al:LIPIcs:2017:8244,
author = {Ioannis Katsikarelis and Michael Lampis and Vangelis Th. Paschos},
title = {{Structural Parameters, Tight Bounds, and Approximation for (k,r)Center}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {50:150:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8244},
URN = {urn:nbn:de:0030drops82441},
doi = {10.4230/LIPIcs.ISAAC.2017.50},
annote = {Keywords: FPT algorithms, Approximation, Treewidth, Cliquewidth, Domination}
}
Keywords: 

FPT algorithms, Approximation, Treewidth, Cliquewidth, Domination 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017) 
Issue Date: 

2017 
Date of publication: 

04.12.2017 