On the Fine-Grained Complexity of Approximating k -Center in Sparse Graphs
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi · Society for Industrial and Applied Mathematics eBooks · 2023
We study the fine-grained complexity of the famous k-center problem in the metric induced by a graph with n vertices and m edges. The problem is NP-hard to approximate within a factor strictly better than 2, and several 2-approximation algorithms are known. Two of the most well-known approaches for the 2-approximation are (1) finding a maximal distance-r independent set (where the minimum pairwise distance is greater than r) and (2) Gonzalez's algorithm that iteratively adds the center farthest from the currently chosen centers. For the approach based on distance-r independent sets, Thorup [SIAM J. Comput. '05] already gave a nearly linear time algorithm. While Thorup's algorithm is not complicated, it still requires tools such as an approximate oracle for neighborhood size by Cohen [J. Comput. Syst. Sci. '97]. Our main result is a nearly straightforward algorithm that improves the running time by an O (log n) factor. It results in a (2 + ε)-approximation for k-center in O((m + n log n) log n log(n/ε)) time. For Gonzalez's algorithm [Theor. Comput. Sci. 85], we show that the simple Õ(mk)-time implementation is nearly optimal if we insist on an exact implementation. On the other hand, we show that a (1 + ε)-approximate version of the algorithm is efficiently implementable, leading to a (2 + ε)-approximation algorithm running in time O((m + n log n) log2(n)/ε). We also show that, unlike in the algorithm based on distance-r independent sets, the dependency on 1/ε in the running time is essentially optimal for (1 + ε)-approximate Gonzalez's.