# Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs

arXiv: https://arxiv.org/abs/1605.02530 · HTML: https://mlsanity.com/paper/1605.02530/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2016.

## Built on by (most cited first, 2 of 2)

- [Tight FPT Approximation for Constrained k-Center and k-Supplier](https://mlsanity.com/paper/2110.14242/) (2021)
- [Dynamic algorithms for k-center on graphs](https://mlsanity.com/paper/2307.15557/) (2023)

## Abstract (arXiv)

We consider the k-Center problem and some generalizations. For k-Center a set of k center vertices needs to be found in a graph G with edge lengths, such that the distance from any vertex of G to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by Abraham et al. [SODA 2010]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations, where the two paradigms are combined. In particular, we prove that for any varepsilon>0 computing a (2-varepsilon)-approximation is W[2]-hard for parameter k and NP-hard for graphs with highway dimension O(log2 n). The latter does not rule out fixed-parameter (2-varepsilon)-approximations for the highway dimension parameter h, but implies that such an algorithm must have at least doubly exponential running time in h if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor of 2 by combining the parameters k and h: we develop a fixed-parameter 3/2-approximation with running time 2O(khlog h)· nO(1). Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter (2-varepsilon)-approximations for only the parameter h. We also provide similar fixed-parameter approximations for the weighted k-Center and (k,F)-Partition problems, which generalize k-Center.