Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82

Question

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?

Answer 1

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.