<p>Here's the same proof in other words. The idea is that if we had a $(2-\epsilon)$-approximation algorithm with $\epsilon &gt; 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 &gt; 0$ for $k$-center unless $\mathsf{P} = \mathsf{NP}$. Recall that the dominating set problem is indeed $\mathsf{NP}$-complete.</p>

<p>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.</p>

<p>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 $&lt; 2$. If there is no such dominating set in $G$, every $k$-center has cost $\geq 2 &gt; 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$.</p>

CC BY-SA 3.0
2012-06-21T12:43:43.220Z
There is a policy on this site of not answering non-research-level questions, there has been many discussion on meta about this. It is better to flag this question and wait until a moderator moves it to cs.SE before answering it.
Gopi
CC BY-SA 3.0
2012-06-21T21:58:14.173Z
@Gopi Sorry, I was unaware of this. I'll be more careful in the future. Thanks for the info!
Juho
CC BY-SA 3.0
2012-06-21T08:46:56.047Z
2012-06-21T12:33:25.393Z
2012-06-21T12:33:25.393Z
Juho
<p>For example, for the $k$-center problem we want to prove that a 2-approximation algorithm is optimal.</p>

<p>A proof is presented on page 39 (Theorem 2.4) in <a href="http://www.designofapproxalgs.com/book.pdf" rel="nofollow">Williamson and Shmoys, The Design of Approximation Algorithms</a>. In the proof, by taking dominating set problem we get a special case of $k$-center problem.</p>

<p>I don't get the part from here.</p>

CC BY-SA 3.0
2012-06-21T08:06:36.970Z
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](http://cs.stackexchange.com/) after some editing.
Juho
CC BY-SA 3.0
2012-06-21T12:47:42.293Z
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 [CS.SE].
Gopi
<cc.complexity-theory><np-hardness><approximation-algorithms><approximation-hardness>
What is meant by "if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP"?
epsilon8
# What is meant by "if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP"?

(Asked by: username_0 on 2012-06-21)

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](http://www.designofapproxalgs.com/book.pdf). 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.

**Tags:** cc.complexity-theory, np-hardness, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: 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](http://cs.stackexchange.com/) after some editing.  
> **username_2**: 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 [CS.SE].  

---

## 1 answers

### Answer by username_1 on 2012-06-21. Score: 1 | Accepted answer

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

> **Comments:**
> **username_2**: There is a policy on this site of not answering non-research-level questions, there has been many discussion on meta about this. It is better to flag this question and wait until a moderator moves it to cs.SE before answering it.  
> **username_1**: @Gopi Sorry, I was unaware of this. I'll be more careful in the future. Thanks for the info!  

---

