# 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$$.