Inapproximability of the $k$-center problem


The $ k$ -center problem:

Given:

  1. Undirected, complete graph $ G=(V,E)$ ,
  2. a distance function $ d:E\rightarrow\mathbb{R}$ such that $ d_{ii}=0, d_{ij}=d_{ji}$ for each pair for vertices $ i,j\in V$ , and that the distances obey triangle inequality,
  3. A positive integer $ k$ .

Find a set $ S\subseteq V, |S|=k$ of $ k$ cluster centers with the objective to minimize the maximum distance of a vertex to its cluster center.

We know that the problem is NP-hard and a simple greedy algorithm gives 2-approximation. I was going through a proof from the book "The Design of Approximation Algorithms" for a theorem that states that an approximation algorithm with factor less than 2 would imply P=NP. This is done using a reduction from the dominating set problem.

Theorem: There is no $ \alpha$ -approximation algorithm for the $ k$ -center problem with $ \alpha<2$ unless P=NP.

Proof: Given an instance of the dominating set problem, we can define an instance of the $ k$ -center problem by setting the distance between adjacent vertices to 1 and non-adjacent vertices to 2. Then there is a dominating set of size $ k$ if and only if the optimal radius for this $ k$ -center instance is 1. Furthermore, any $ \alpha$ -approximation with $ \alpha<2$ must always produce a solution of radius 1 if such a solution exists.

Question: I think I understand the proof. However, I am confused with the setting of distance between non-adjacent vertices to 2. What if we set it to 3 instead of 2? Would that mean the $ \alpha<3$ is not possible unless P=NP? This is not true as we have a 2-approximation algorithm. The proof should not work for values greater than 2. However, I am not able to figure out which step of the proof breaks when we set distance between non-adjacent vertices to 3.

Dominating Set Problem: Given an undirected graph $ G=(V,E)$ and an integer $ k$ , we must decide if there exists a set $ S\subseteq V$ of size $ k$ such that each vertex is either in $ S$ or adjacent to a vertex in $ S$ .