License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.50
URN: urn:nbn:de:0030-drops-82441
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8244/
Katsikarelis, Ioannis ;
Lampis, Michael ;
Paschos, Vangelis Th.
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>=1, we show an algorithm that solves the problem in O*((3r+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^Theta(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*((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 W-hardness.
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:1--50:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-054-5},
ISSN = {1868-8969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8244},
URN = {urn:nbn:de:0030-drops-82441},
doi = {10.4230/LIPIcs.ISAAC.2017.50},
annote = {Keywords: FPT algorithms, Approximation, Treewidth, Clique-width, Domination}
}
|
Keywords: |
|
FPT algorithms, Approximation, Treewidth, Clique-width, Domination |
|
Collection: |
|
28th International Symposium on Algorithms and Computation (ISAAC 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.12.2017 |
