<p>It just so happened that we used a similar reduction as part of our proof for NP-hardness of regret-minimizing set, so I'm pretty familiar with this. We have the following claim:</p>
<blockquote>
<p>Let <span class="math-container">$V$</span> and <span class="math-container">$V'$</span> be the vertex sets of <span class="math-container">$G$</span> and <span class="math-container">$G'$</span>, then <span class="math-container">$G'$</span> has a vertex cover of size <span class="math-container">$k$</span> if and only if <span class="math-container">$G$</span> has a vertex cover of size <span class="math-container">$k-\frac{1}{2}(|V'|-|V|)$</span>.</p>
</blockquote>
<p>This is because:</p>
<ul>
<li>Given a vertex cover <span class="math-container">$C\subseteq V$</span> for <span class="math-container">$G$</span>, one can construct a vertex cover for <span class="math-container">$G'$</span> of size <span class="math-container">$|C|+\frac{1}{2}(|V'|-|V|)$</span>: On each edge in <span class="math-container">$G$</span>, starting from an endpoint in <span class="math-container">$C$</span>, alternately select the padding vertices.</li>
<li>Consider a vertex cover <span class="math-container">$C'\subseteq V'$</span> for <span class="math-container">$G'$</span>. On each edge <span class="math-container">$e=(u,v)$</span> in <span class="math-container">$G$</span>, assume there are <span class="math-container">$p_e$</span> (which is an even number) padding vertices in <span class="math-container">$G'$</span>. At least <span class="math-container">$\frac{1}{2}p_e$</span> of them have to be in <span class="math-container">$C'$</span>, and if <span class="math-container">$u\notin C'$</span> and <span class="math-container">$v\notin C'$</span> then at least <span class="math-container">$\frac{1}{2}p_e+1$</span> of them have to be in <span class="math-container">$C'$</span>. Therefore
<span class="math-container">$$|C'|\geq |V\cap C'|+\frac{1}{2}\sum p_e+\#\{e=(u,v)\mid u,v\notin C'\}.$$</span>
But you can take the set <span class="math-container">$V\cap C'$</span>, and for each edge <span class="math-container">$e=(u,v)$</span> in <span class="math-container">$G$</span> that <span class="math-container">$u,v\notin C'$</span>, just add <span class="math-container">$u$</span> to this set. Then it forms a vertex cover for <span class="math-container">$G$</span>, which has size at most <span class="math-container">$|C'|-\frac{1}{2}\sum p_e=|C'|-\frac{1}{2}(|V'|-|V|)$</span>.</li>
</ul>
<p>Combining this claim with your Claim 2 shows the NP-hardness of clustering, and I think hardness of approximation follows from the rest of the proof in that paper.</p>

CC BY-SA 4.0
2022-11-29T22:39:19.763Z
2022-11-30T08:21:01.933Z
2022-11-30T08:21:01.933Z
Wei Zhan
<p>I was reading the paper &quot;Optimal Algorithms for Approximate Clustering&quot;, Feder and Greene [1988] (<a href="https://dl.acm.org/doi/10.1145/62212.62255" rel="noreferrer">https://dl.acm.org/doi/10.1145/62212.62255</a>).</p>
<p>Specifically, I was trying to look at the <span class="math-container">$1.82$</span> approximation hardness proof for central L2 clustering (this is the standard k-center problem in Euclidean <span class="math-container">$\mathcal{R}^2$</span> space with the normal metric - we need to cluster a pointset into <span class="math-container">$k$</span> clusters such that the maximum distance from centroid of cluster to a point in the cluster is minimized). The proof is considerably shorter and simpler than Stuart Mentzer's construction independently showing the same result (<a href="https://www.academia.edu/23251714/Approximability_of_Metric_Clustering_Problems" rel="noreferrer">https://www.academia.edu/23251714/Approximability_of_Metric_Clustering_Problems</a>).</p>
<p>The relevant parts of the paper are Section 2, Theorem 2.1 and Figure 1.</p>
<p>At the start of Section 2, it is mentioned that</p>
<blockquote>
<p>An instance of vertex cover for planar graphs of degree at most <span class="math-container">$3$</span> can be embedded in the plane, by replacing all edges with odd length paths, so that edges become segments of length <span class="math-container">$1$</span> [see Fig. 1]. The midpoints of these edges then form an instance of central clustering which has a <span class="math-container">$k$</span>-clustering with cluster size <span class="math-container">$1$</span> if and only if the embedded graph has a vertex cover with <span class="math-container">$k$</span> nodes. We can use this construction to show that approximate clustering is NP-Complete.</p>
</blockquote>
<p>I don't quite understand why the stated claim in the given form is true. There are two graphs which we can discuss here.</p>
<p>First, is the planar graph with max vertex degree <span class="math-container">$ \leq 3$</span>, let's call this graph <span class="math-container">$G$</span> (this is an arbitrary instance of the vertex cover problem in planar graphs with max vertex degree <span class="math-container">$\leq 3$</span>, which has been shown to be NP-Complete by Gary and Johnson in 1977 as mentioned in references).</p>
<p>Second, we take the graph <span class="math-container">$G$</span>, obtain its planar embedding, and ensure that the edge length is odd (by stretching edges I presume). Then, we split up each edge into segments of length 1 and convert the edges into paths (by adding nodes at lengths of <span class="math-container">$1$</span>). Thus, we have transformed <span class="math-container">$G$</span> into a new graph <span class="math-container">$G^{'}$</span> (which also has a embedding on the plane).</p>
<p>Now, the claim in the paragraph can be interpreted in two ways:</p>
<p>Claim Interpretation 1: The midpoints of these edges then form an instance of central clustering which has a <span class="math-container">$k$</span>-clustering with cluster size <span class="math-container">$1$</span> if and only if <span class="math-container">$G$</span> has a vertex cover with <span class="math-container">$k$</span> nodes.</p>
<p>Claim Interpretation 2: The midpoints of these edges then form an instance of central clustering which has a <span class="math-container">$k$</span>-clustering with cluster size <span class="math-container">$1$</span> if and only if <span class="math-container">$G^{'}$</span> has a vertex cover with <span class="math-container">$k$</span> nodes.</p>
<p>As far as I understand, Claim 1 is incorrect while Claim 2 is correct.</p>
<p>However, I do not understand how just Claim 2 being correct is enough to show NP-Hardness of approximation. It seems to be that the paper assumes that Claim 1 is correct (in Theorem 2.1).</p>
<p>Can someone point out what I might be missing?</p>

<cc.complexity-theory><reductions><computational-geometry>
Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82
Agile_Eagle
# Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82

(Asked by: username_0 on 2022-09-25)

I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene [1988] (<https://dl.acm.org/doi/10.1145/62212.62255>).

Specifically, I was trying to look at the $1.82$ approximation hardness proof for central L2 clustering (this is the standard k-center problem in Euclidean $\mathcal{R}^2$ space with the normal metric - we need to cluster a pointset into $k$ clusters such that the maximum distance from centroid of cluster to a point in the cluster is minimized). The proof is considerably shorter and simpler than Stuart Mentzer's construction independently showing the same result (<https://www.academia.edu/23251714/Approximability_of_Metric_Clustering_Problems>).

The relevant parts of the paper are Section 2, Theorem 2.1 and Figure 1.

At the start of Section 2, it is mentioned that

> An instance of vertex cover for planar graphs of degree at most $3$ can be embedded in the plane, by replacing all edges with odd length paths, so that edges become segments of length $1$ [see Fig. 1]. The midpoints of these edges then form an instance of central clustering which has a $k$-clustering with cluster size $1$ if and only if the embedded graph has a vertex cover with $k$ nodes. We can use this construction to show that approximate clustering is NP-Complete.

I don't quite understand why the stated claim in the given form is true. There are two graphs which we can discuss here.

First, is the planar graph with max vertex degree $ \leq 3$, let's call this graph $G$ (this is an arbitrary instance of the vertex cover problem in planar graphs with max vertex degree $\leq 3$, which has been shown to be NP-Complete by Gary and Johnson in 1977 as mentioned in references).

Second, we take the graph $G$, obtain its planar embedding, and ensure that the edge length is odd (by stretching edges I presume). Then, we split up each edge into segments of length 1 and convert the edges into paths (by adding nodes at lengths of $1$). Thus, we have transformed $G$ into a new graph $G^{'}$ (which also has a embedding on the plane).

Now, the claim in the paragraph can be interpreted in two ways:

Claim Interpretation 1: The midpoints of these edges then form an instance of central clustering which has a $k$-clustering with cluster size $1$ if and only if $G$ has a vertex cover with $k$ nodes.

Claim Interpretation 2: The midpoints of these edges then form an instance of central clustering which has a $k$-clustering with cluster size $1$ if and only if $G^{'}$ has a vertex cover with $k$ nodes.

As far as I understand, Claim 1 is incorrect while Claim 2 is correct.

However, I do not understand how just Claim 2 being correct is enough to show NP-Hardness of approximation. It seems to be that the paper assumes that Claim 1 is correct (in Theorem 2.1).

Can someone point out what I might be missing?

**Tags:** cc.complexity-theory, reductions, computational-geometry

---

## 1 answers

### Answer by username_1 on 2022-11-29. Score: 3 | Accepted answer

It just so happened that we used a similar reduction as part of our proof for NP-hardness of regret-minimizing set, so I'm pretty familiar with this. We have the following claim:

> Let $V$ and $V'$ be the vertex sets of $G$ and $G'$, then $G'$ has a vertex cover of size $k$ if and only if $G$ has a vertex cover of size $k-\frac{1}{2}(|V'|-|V|)$.

This is because:

* Given a vertex cover $C\subseteq V$ for $G$, one can construct a vertex cover for $G'$ of size $|C|+\frac{1}{2}(|V'|-|V|)$: On each edge in $G$, starting from an endpoint in $C$, alternately select the padding vertices.
* Consider a vertex cover $C'\subseteq V'$ for $G'$. On each edge $e=(u,v)$ in $G$, assume there are $p\_e$ (which is an even number) padding vertices in $G'$. At least $\frac{1}{2}p\_e$ of them have to be in $C'$, and if $u\notin C'$ and $v\notin C'$ then at least $\frac{1}{2}p\_e+1$ of them have to be in $C'$. Therefore
  $$|C'|\geq |V\cap C'|+\frac{1}{2}\sum p\_e+\#\{e=(u,v)\mid u,v\notin C'\}.$$
  But you can take the set $V\cap C'$, and for each edge $e=(u,v)$ in $G$ that $u,v\notin C'$, just add $u$ to this set. Then it forms a vertex cover for $G$, which has size at most $|C'|-\frac{1}{2}\sum p\_e=|C'|-\frac{1}{2}(|V'|-|V|)$.

Combining this claim with your Claim 2 shows the NP-hardness of clustering, and I think hardness of approximation follows from the rest of the proof in that paper.


---

