# What is meant by “if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP”?

For example, for the $k$-center problem we want to prove that a 2-approximation algorithm is optimal.

A proof is presented on page 39 (Theorem 2.4) in Williamson and Shmoys, The Design of Approximation Algorithms. In the proof, by taking dominating set problem we get a special case of $k$-center problem.

I don't get the part from here.

• Can you be more specific: what exactly don't you understand? Other than that, I think this would be a good question for CS.SE after some editing. – Juho Jun 21 '12 at 8:06
• Welcome to CSTheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. As stated by @mrm, you should try posting it on Computer Science. – Gopi Jun 21 '12 at 12:47

Here's the same proof in other words. The idea is that if we had a $(2-\epsilon)$-approximation algorithm with $\epsilon > 0$, we could decide whether or not there is a dominating set of size $k$. In other words, we want to show that there is no $(2-\epsilon)$-approximation algorithm with $\epsilon > 0$ for $k$-center unless $\mathsf{P} = \mathsf{NP}$. Recall that the dominating set problem is indeed $\mathsf{NP}$-complete.
Let $G = (V,E)$ with integer $k$ be an instance of the dominating set problem. Let us then define a complete graph $G'$ such that the distance between adjacent vertices is 1 while nonadjacent vertices have a distance of 2. $G'$ satisfies the triangle inequality as well.
Suppose $G$ has a dominating set of size at most $k$. Then, $G'$ has a $k$-center cost of 1. Now, a $(2-\epsilon)$-approximation algorithm gives us a solution with cost $< 2$. If there is no such dominating set in $G$, every $k$-center has cost $\geq 2 > 2-\epsilon$. Thus, a $(2-\epsilon)$-approximation algorithm for the $k$-center problem can decide whether or not there is a dominating set of size $k$.