(i)
The benefit of the structure of \(G^2\)  is that it contains many cliques, e.g., each neighborhood in \(G\)  induces a clique in \(G^2\) .
One approach to getting a good approximation to MVC is to repeatedly add disjoint cliques to the vertex cover.
Adding a clique of size \(s\)  costs our algorithm \(s\) , but OPT needs to pay \(s-1\) . However, large cliques
could also be exclusively induced by edges in \(G^2 - G\)  and these are not easy to find. Our algorithm relies on
a structural property we show: we only need to find cliques induced by neighborhoods in \(G\) . We show that once such cliques
are found and removed, then the remaining graph becomes sparse enough for fast processing.
(ii)
For obtaining our centralized \(5/3\) -approximation for MVC on \(G^2\) , we also rely on the structure of \(G^2\) . We use the local ratio approach [1]} to take care of small vertex-disjoint parts of the graph, for which an optimal solution has to pay not much less than our cost. An example is taking triangles, for which an optimal solution needs to pay 2 while we pay 3. We also use techniques of finding local maximal matchings, as first done by Gavril as explained in [2]}.
Many local-ratio algorithms then take the worst approximation factor among all these parts and that is the approximation factor of the entire solution. However, in our algorithm, after handling some parts of the graph we still remain with a part for which we find a 2-approximation. Still, we avoid paying this in the final approximation factor, by constructing a useful partition, in which the size of one part is bounded by a constant fraction of the optimal solution for another part. This allows us to take a sloppy approximation for the former, and rely on the latter in order to argue that this still gives a good total approximation factor, rather than taking the worst factor among the parts.
(iii)
For the lower bound constructions in this paper, we use the Alice-Bob lower bound framework developed in [3]}
for obtaining quadratic and near-quadratic lower bounds for graph problems.
To leverage the current lower bound construction for \(G\)  and use it for \(G^2\) , we replace each edge \(\lbrace u, v\rbrace \) 
by a path gadget that creates a 2-path between \(u\)  and \(v\)  and possibly adds an additional \(O(1)\)  vertices
Note that this provides the edge \(\lbrace u, v\rbrace \)  in the square of this graph.
Doing this suffices for the centralized setting, but in the distributed setting it introduces a factor-\(n\)  blowup
in the number of vertices, and no longer provides a lower bound that is quadratic in the number of vertices.
An even bigger challenge is the need to create a constant-factor gap in the output of the lower bound reduction, which necessitates many new techniques in our construction.

