KOPS - The Institutional Repository of the University of Konstanz

W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension

W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BLUM, Johannes, 2020. W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension. Computing and Combinatorics : 26th International Conference, COCOON 2020. Atlanta, GA, USA, Aug 29, 2020 - Aug 31, 2020. In: KIM, Donghyun, ed., R. N. UMA, ed., Zhipeng CAI, ed., Dong Hoon LEE, ed.. Computing and Combinatorics : 26th International Conference, COCOON 2020 : Proceedings. Cham:Springer, pp. 210-221. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-58149-7. Available under: doi: 10.1007/978-3-030-58150-3_17

@inproceedings{Blum2020W1Har-50800, title={W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension}, year={2020}, doi={10.1007/978-3-030-58150-3_17}, number={12273}, isbn={978-3-030-58149-7}, issn={0302-9743}, address={Cham}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Computing and Combinatorics : 26th International Conference, COCOON 2020 : Proceedings}, pages={210--221}, editor={Kim, Donghyun and Uma, R. N. and Cai, Zhipeng and Lee, Dong Hoon}, author={Blum, Johannes} }

terms-of-use In the k-Center problem, we are given a graph G=(V,E) with positive edge weights and an integer k and the goal is to select k center vertices C⊆V such that the maximum distance from any vertex to the closest center vertex is minimized. On general graphs, the problem is NP-hard and cannot be approximated within a factor less than 2.<br /><br />Typical applications of the k-Center problem can be found in logistics or urban planning and hence, it is natural to study the problem on transportation networks. Such networks are often characterized as graphs that are (almost) planar or have low doubling dimension, highway dimension or skeleton dimension. It was shown by Feldmann and Marx that k-Center is W[1]-hard on planar graphs of constant doubling dimension when parameterized by the number of centers k, the highway dimension hd and the pathwidth pw [11]. We extend their result and show that even if we additionally parameterize by the skeleton dimension κ , the k-Center problem remains W[1]-hard. Moreover, we prove that under the Exponential Time Hypothesis there is no exact algorithm for k-Center that has runtime f(k,hd,pw,κ)⋅|V|<sup>o(pw+κ+k+hd√)</sup> for any computable function f. Blum, Johannes Blum, Johannes W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension eng 2020-09-11T11:33:00Z 2020 2020-09-11T11:33:00Z

This item appears in the following Collection(s)

Search KOPS


Browse

My Account