2026-08-10T20:24:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8244 2024-03-06T10:41:52Z ddc:004 open_access

Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center Katsikarelis, Ioannis Lampis, Michael Paschos, Vangelis Th. FPT algorithms Approximation Treewidth Clique-width Domination 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ioannis Katsikarelis and Michael Lampis and Vangelis Th. Paschos 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.50 urn:nbn:de:0030-drops-82441 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.50 eng https://creativecommons.org/licenses/by/3.0/legalcode