KOPS - The Institutional Repository of the University of Konstanz
# W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension

Type of Publication: | Contribution to a conference collection |

Publication status: | Published |

Author: | Blum, Johannes |

Year of publication: | 2020 |

Conference: | Computing and Combinatorics : 26th International Conference, COCOON 2020, Aug 29, 2020 - Aug 31, 2020, Atlanta, GA, USA |

Published in: | Computing and Combinatorics : 26th International Conference, COCOON 2020 : Proceedings / Kim, Donghyun; Uma, R. N.; Cai, Zhipeng; Lee, Dong Hoon (ed.). - Cham : Springer, 2020. - (Lecture Notes in Computer Science ; 12273). - pp. 210-221. - ISSN 0302-9743. - eISSN 1611-3349. - ISBN 978-3-030-58149-7 |

DOI (citable link): | https://dx.doi.org/10.1007/978-3-030-58150-3_17 |

Summary: |
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.
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| ^{o(pw+κ+k+hd√)} for any computable function f. |

Subject (DDC): | 004 Computer Science |

Keywords: | k-Center, Skeleton dimension, Parameterized complexity |

Bibliography of Konstanz: | Yes |

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} }