(i)
In Algorithm REF , we repeatedly picked a vertex \(c\)  with a large enough still-active neighborhood (i.e., \(N(c) \cap R\) )
to ensure that when \(N(c) \cap R\)  is added to the vertex cover, we continue to get a good approximation.
The cardinality of active neighborhoods is not useful in the weighted setting, but we can derive a corresponding
condition for picking \(c\)  as follows.
For any vertex \(c\) , let \(W(c)\)  denote \(\sum _{v\in N(c) \cap R} w(v)\) . Let \(w^*(c)\)  be the maximum weight of a vertex in
\(N(c) \cap R\) . Then, \(W(c)- w^*\)  is a lower bound on the weight of an optimal vertex cover
of \(G^2\)  restricted to \(N(c) \cap R\) , i.e., the clique in \(G^2\)  induced by \(N(c) \cap R\) .
Therefore, to be able to safely add \(N(c) \cap R\)  to the vertex cover the following condition needs to be satisfied:
\(W(c) \le (1+\varepsilon ) (W(c) - w^*(c))\) , or equivalently
\(w^*(c) \le W(c) \cdot \frac{\varepsilon }{(1+\varepsilon )}.\) 
(ii)
We apply the above condition, not to the entire active neighborhood of \(c\) , but to subsets with similar weights.
Let \(w_*(c)\)  denote the minimum weight of a vertex in \(N(c)\) .
We partition \(N(c)\)  into subsets \(N_i(c) := \lbrace v \in N(c) \mid w_*(c) \cdot 2^i \le w(v) < w_*(c) \cdot 2^{i+1}\rbrace \) 
for \(i = 0, 1, \ldots , I\) , where \(I = O(\log _2 n)\)  (since all vertex weights have \(O(\log n)\) -bit representations).
Instead of checking condition (REF ) for \(N(c) \cap R\) , we check it for
\(N_i(c) \cap R\) , for each \(i\) .
Let \(w^*_i(c)\)  denote the maximum weight of a vertex in \(N_i(c) \cap R\)  and similarly let
\(W_i(c)\)  denote \(\sum _{v\in N_i(c) \cap R} w(v)\) 
Specifically, we replace Line 4 in Algorithm REF  by
\(\textbf {while}\textit { there is a vertex \) 
C\( and \) i\( with } w^*_i(c) \le W_i(c) \cdot \frac{\varepsilon }{(1+\varepsilon )}\textbf { do}\)\(and perform the body of the loop with \) Ni(c)\( replacing \) N(c)\( in Lines 6 and 7.\)
To ensure efficiency of our algorithm, the key property we need is for \(|F|\)  to be small, so that a leader can gather all of \(F\) 
and the algorithm can proceed to Phase II.
In the analysis of Algorithm REF , this simply followeed from the fact that after Phase I, every vertex has at most \(1/\varepsilon \)  neighbors
in \(U\)  (the set of vertices not in the cover).
The following lemma proves a similar condition for the current algorithm.
Lemma 8 
\(|F| = O\left(n \cdot \frac{(1+\varepsilon )}{\varepsilon } \cdot \log _2 n\right)\) .

Suppose that for all \(c \in V\)  and \(i\) , we have \(w^*_i(c) > W_i(c) \cdot \varepsilon /(1+\varepsilon )\) .
This is guaranteed after Phase 1 of the algorithm.
Let \(s\)  denote the number of vertices in \(N_i(c) \cap R\) .
Since all vertices in \(N_i(c) \cap R\)  have weights in the range \([w_*(c) \cdot 2^i, w_*(c) \cdot 2^{i+1})\) , we see
that \(w_*(c) \cdot 2^{i+1} > w^*_i(c)\)  and \(W_i(c) \ge s \cdot w_*(c) \cdot 2^i\) .
This leads to the inequality
\(w_*(c) \cdot 2^{i+1} > s \cdot w_*(c) \cdot 2^i \cdot \frac{\varepsilon }{(1 + \varepsilon )},\) 
which in turn yields the upper bound
\(s < 2 \cdot \frac{1+\varepsilon }{\varepsilon }.\) 
Thus, each vertex \(c\)  has at most \(O((1+\varepsilon )/\varepsilon \log _2 n)\)  neighbors in \(U\)  after Phase I and the lemma follows
by accounting for all vertices.

The rest of the running time analysis simply follows as in the corresponding steps
for Algorithm REF  (see Lemmas , ).
Note that in the current algorithm, Phase I runs in \(O(n \log n)\)  rounds because we sequentially
consider every vertex \(c\)  and neighbor set \(N_i(c)\)  for \(O(\log _2 n)\)  possible values of \(i\) .
Phase II run in \(O(n \cdot \frac{(1+\varepsilon )}{\varepsilon } \cdot \log _2 n)\)  rounds because of the size
of \(|F|\) .
The correctness follows immediately, as in Lemma .
The approximation factor analysis depends on the fact that whenever we add \(N_i(c) \cap R\)  to the vertex cover,
the weight of the added vertices is within an \((1+\varepsilon )\)  factor of what the optimal solution pays
to cover the edges in the subgraph of \(G^2\)  induced by \(N_i(c) \cap R\) .
The calculations follow the steps in the proof of Lemma .
\(\mathsf {CONGESTED~CLIQUE}\) : \((1+\varepsilon )\) -Approximation for \(G^2\) -MVC
In the \(\mathsf {CONGESTED~CLIQUE}\)  we obtain faster deterministic and randomized algorithms for \((1+\varepsilon )\) -approximation of MVC on \(G^2\) .
As one component these algorithm use that learning the set \(F\)  is much faster as formalized in the next lemma.
Lemma 9 (Learning Remaining Graph in the \(\mathsf {CONGESTED~CLIQUE}\) ) 
The leader vertex \(\ell \)  can learn the set \(F\)  in \(O(1/\varepsilon )\)  rounds.

Just as in the proof of lem:learnRemainingGraph any node in \(v\in V\)  has at most \(1/\varepsilon \)  neighbors in \(U\)  as otherwise \(v\)  would be processed in the first phase and all of its neighbors would join \(S\) . We make \(v\)  responsible for sending its \(1/\varepsilon \)  incident edges of \(F\)  to the leader which can be done in parallel for all vertices in \(1/\varepsilon \)  rounds.

lem:learnRemainingGraphClique together with the analysis from sssec:UBunweightedVC immediately implies the following corollary.
Corollary 10 (\(\mathsf {CONGESTED~CLIQUE}\) , deterministic) 
For any (also non constant) \(\varepsilon >0\)  there is a deterministic distributed \(\mathsf {CONGESTED~CLIQUE}\)  algorithm that computes a \((1+\varepsilon )\) -approximation to the \(G^2\) -minimum vertex cover in \(O(\varepsilon \cdot n+1/\varepsilon )\)  rounds. By setting \(\varepsilon =1/\sqrt{n}\)  we can compute a \((1+1/\sqrt{n})\) -approximation in \(O(\sqrt{n})\)  rounds, deterministically.

Learning the set \(F\)  is sufficient to compute the graph \(H\)  and can be done in \(O(1/\varepsilon )\)  rounds by lem:learnRemainingGraphClique. Distributing the locally computed solution for the graph \(H\)  can be done in one round. Thus the runtime is dominated by the \(O(\varepsilon \cdot n)\)  rounds of the first phase.
We now show that we can also speed up the first phase of our our algorithm in Section REF , using randomization.
This follows a similar approach used in [1]} for approximating spanners and MDS, which in turn uses is a modification of the framework of Jia et al. [2]} for approximating minimum dominating sets. While this faster implementation itself works in the \(\mathsf {CONGEST}\)  model it still does not improve the overall running time in the \(\mathsf {CONGEST}\)  model. However, combined with lem:learnRemainingGraphClique it allows us to obtain a much faster algorithm for the \(\mathsf {CONGESTED~CLIQUE}\)  model, as given in the following theorem.
Theorem 11 
For any \(\varepsilon >0\) , there is a distributed \(\mathsf {CONGESTED~CLIQUE}\)  algorithm that computes a \((1+\varepsilon )\) -approximation for \(G^2\) -MVC in \(O(\log n+1/\varepsilon )\)  rounds.

We use the same notation of our algorithm in Section REF : The set \(S\)  contains vertices in the cover, the set \(R\)  denotes the remaining vertices, and \(C\)  is the set of candidates. Whenever the degree of a vertex \(c\in C\)  in \(R\)  drops below the threshold \(8/\varepsilon +2\)  it leaves \(C\) , that is, any vertex \(c \in C\)  for which \(|N(c)\cap R| \le 8/\varepsilon +2\)  is removed from \(C\) . For simplicity of notation, denote \(|N(c)\cap R|\)  by \(d_R(c)\) .
The algorithm consists of \(O(\log n)\)  phases and in each phase some vertices leave \(C\) , some vertices are added to \(S\)  and removed from \(R\) .
In each phase, each candidate, that is, each vertex in \(C\) , informs its neighbors that it is a candidate. Then, every vertex in \(R\)  votes for one of its candidate neighbors and informs all of them about its vote—we will soon explain the details of the voting scheme. Each candidate \(c\)  which gets at least \(d_R(c)/8\)  votes is successful, i.e., its neighbors are added into \(S\)  and are removed from \(R\) , and the candidate \(c\)  is removed from \(C\) . We repeat until there are no more candidates and then resort to having a leader learn the edges in \(F\)  as in our algorithm in Section REF .
We now describe the voting mechanism. Each candidate \(c\)  chooses a random number \(r_c \in [n^4]\)  and a voter votes for its candidate neighbor who has the highest random value. A candidate \(c\)  is successful if it gets at least \(d_R(c)/8\)  votes.
Correctness:
Lemma  holds here too, proving that we cover all edges of \(G^2\) .

Approximation Factor:
The approximation proved in Lemma  is maintained because we charge the votes that made the candidate successful only to a single candidate and a candidate is only successful if it got at least \(d_R(c)/8\ge (8/\varepsilon +2)/8>1/\varepsilon \)  votes.

Runtime:
We analyze progress using a potential function whose value at the beginning of iteration \(i\)  is \(\Phi _i = \sum _{c \in C}{d_R(c)}\) . We claim that \(\Phi \)  decreases by a constant factor in each iteration and hence we have a logarithmic number of iterations until the potential function is smaller than 1, i.e., the set of candidates \(C\)  is empty. For each vertex \(v \in R\)  we denote by \(s(v)\)  the number of neighbors it has in \(C\) . For each candidate \(c \in C\) , we sort its neighbors in \(R\)  according to their \(s\)  values, and split them into sets \(T(c)\)  and \(B(c)\)  where the \(\lceil d_R(c)/2 \rceil \)  top values go into \(T(c)\)  and the \(\lceil d_R(c)/2 \rceil \)  bottom values go into \(B(c)\)  (there may be an overlap of one vertex). For every \(v \in T(c)\) , we say that \((c,v)\)  is a top pair. We show that if a voter of a top pair votes for a candidate, then the candidate is successful with constant probability.
Claim 1 
If \((c,v)\)  is a top pair then \(Pr[c \text{ is successful} \mid v \text{ votes for } c]\ge 1/3\) .

We first claim that if \(v_1,v_2 \in N(c)\cap R\)  and \(s(v_1) \ge s(v_2)\)  then
\(Pr[v_2 \text{ votes for } c \mid v_1 \text{ votes for } c]\ge 1/2.\) 
Let \(N_1,N_2\)  and \(N_{1,2}\)  be the number of candidates that are neighbors of \(v_1\)  but not of \(v_2\) , the number of candidates that are neighbors of \(v_2\)  but not of \(v_1\) , and the number of candidates that are neighbors of both \(v_1\)  and \(v_2\) , respectively. Then,
\(Pr[v_2 \text{ votes for } c \mid v_1 \text{ votes for } c] & = \frac{Pr[v_1 \text{ and } v_2 \text{ vote for } c]}{Pr[v_1 \text{ votes for } c]} = \frac{1/(N_1+N_2+N_{1,2})}{1/(N_1+N_{1,2})} \\& = \frac{N_1+N_{1,2}}{N_1+N_2+N_{1,2}} \ge 1/2,\) 

where the last inequality is because \(N_1 \ge N_2\) , since \(s(v_1) \ge s(v_2)\) .
Now, let \((c,v)\)  be a top pair and suppose that \(v\)  votes for \(c\) . Then each \(u \in B(c)\)  votes for \(c\)  w.p. at least \(1/2\)  because \(s(v) \ge s(u)\)  for each such \(u\) . Let \(x\)  be the number of vertices in \(B(c)\)  that do not vote for \(c\) . We have that \(E[x] \le |B(c)|/2\) . By Markov's inequality, \(Pr[x > 3 \cdot B(c)|/4] \le 2/3\) . Thus, w.p. at least \(1/3\) , at least \(|B(c)|/4\)  vertices in \(B(c)\)  vote for \(c\) . This is at least \(d_R(c)/8\)  and hence \(c\)  is successful.
We can now show that in expectation, \(\Phi \)  decreases by a constant factor in each iteration. A Chernoff bound then implies that we need only \(O(\log n)\)  iterations w.h.p. We then need to learn the remaining graph after we are done, which, by lem:computeRemainingGraph and a proof along the same lines as the one for lem:learnRemainingGraphClique—note the slightly different threshold of \(8\varepsilon +1\)  for being a candidate— can be done in \(O(1/\varepsilon )\)  rounds.
This gives a total of \(O(\log n + 1/\varepsilon )\)  rounds in the \(\mathsf {CONGESTED~CLIQUE}\)  model.
Thus, it remains to show that the expected decrease in \(\Phi \)  is a constant fraction of it. Recall that we define \(\Phi _i = \sum _{c \in C}{d_R(c)}\) . If we count this according to the vertices in \(R\) , we get that this equals \(\sum _{v \in R}{s(v)}\) . If a vertex \(v\)  votes for a successful candidate \(c\) , then \(\Phi \)  decreases by at least \(s(v)\) . We can associate this decrease with the pair \((c,v)\)  because \(v\)  votes for a single candidate. We then have:
\(E[\Phi _{i-1} - \Phi _i] &\ge \sum _{(c,v)}{Pr[v \text{ votes for } c \text{ and } c \text{ is successful}]\cdot s(v)}\\&\ge \sum _{\text{top pairs } (c,v)}{Pr[v \text{ votes for } c]\cdot Pr[c \text{ is successful} \mid v \text{ votes for } c] \cdot s(v)}\\&\ge \sum _{\text{top pairs } (c,v)}{(1/s(v)) \cdot (1/3) \cdot s(v)} = 1/3 \cdot |\lbrace \text{top pairs } (c,v) \rbrace  |\\&\ge 1/6 \cdot \Phi _{i-1},\) 

where the last inequality follows since at least half of the pairs are top pairs.

Centralized \(G^2\) -Minimum Vertex Cover
In this section we present a polynomial time centralized algorithm that gives an \(\alpha \) -approximation to unweighted MVC, for a constant \(\alpha < 2\) .
In sec:centHardness we show that the problem of computing an exact \(G^2\) -MVC is NP-hard and that one cannot even get a FPTAS unless \(P=NP\) .
Here, we formally show the following theorem.
Theorem 12 
There is a centralized polynomial time algorithm that computes an \(\alpha \) -approximation to \(G^2\) -Minimum Vertex Cover, for a constant \(\alpha < 2\) .

High Level View on Algorithm:
The algorithm consists of three parts, in each of which we find an approximate solution to part of the remaining graph, until it is empty.
The high-level goal is to find a set of nodes \(U\)  for which the size of an optimal solution \(|OPT_U|\)  can be well approximated and is larger by some positive fraction compared to the size of the rest of the nodes \(U^{\prime }\) , which allows us to find only a sloppy approximation for the cover of \(U^{\prime }\) .
In the algorithm, we maintain that \(V^{\prime }\)  and \(E^{\prime }\)  are the remaining sets of vertices and edges, respectively. Initially, these are \(V\)  and \(E(G^2)\) . We denote by \(S\)  the cover that we obtain, initially empty. During the algorithm, whenever we say that we take a node into \(S\) , we also mean that it is removed from \(V^{\prime }\)  and all edges with at least one endpoint in \(S\)  are removed from \(E^{\prime }\) . Whenever there is a node with degree 0, it is removed from \(V^{\prime }\) .
In the first part, the algorithm loops until there are no more triangles in \(E^{\prime }\) : Sequentially, as long as there is a triangle in \(E^{\prime }\)  we add all of its three vertices to \(S\) , remove the vertices from \(V^{\prime }\)  and we remove all edges touching the triangle from \(E^{\prime }\) , i.e., we remove all edges with at least one endpoint being one of the triangle's vertices.
In the second part, that we detail on later, we remove further vertices from \(V^{\prime }\)  and edges from \(E^{\prime }\)  such that the remaining part has minimum degree 4. Then, in the third part of the algorithm we compute a 2-approximation on the remaining vertex cover instance (e.g. by computing a maximal matching and adding both endpoints of the matched edges to the cover).
For detailed pseudocode we refer to Algorithm .
0.5em
boxruled
 An \(\alpha \) -approximation for Minimum \(G^2\) -Vertex Cover 
\(V^{\prime } = V\) , \(E^{\prime } = E(G^2)\)  *current set of vertices and edges
\(S = \emptyset \)  *vertices in the cover
\(V_1 = \emptyset \) , \(V_2 = \emptyset \) , \(V_3 = \emptyset \)  *part-1, part-2, part-3 vertices in the cover
*part-1
there is a triangle in \((V^{\prime },E^{\prime })\)  
Take all three nodes of the triangle into \(S\)  and into \(V_1\) , delete them from \(V^{\prime }\)  and their incident edges from \(E^{\prime }\)

*part-2
there is a node \(x \in V^{\prime }\)  with \(\deg _{E^{\prime }}(x) \le 3\) 

If there is a node \(x\)  with \(\deg _{E^{\prime }}(x)=1\)  then its neighbor is taken into \(S\)  and into \(V_2\)
else If there is a node \(x\)  with \(\deg _{E^{\prime }}(x)=2\) , denote its neighbors by \(y_1,y_2\) . Since there is no node \(u\)  with \(\deg _{E^{\prime }}(u)=1\) , it holds that \(y_1\)  has a neighbor \(z\ne x\) . Take \(z,y_1,y_2\)  into \(S\)  and into \(V_2\)
else If there is a node \(x\)  with \(\deg _{E^{\prime }}(x)=3\) , denote its neighbors by \(y_1,y_2,y_3\) . Since there is no node \(u\)  with \(\deg _{E^{\prime }}(u)<3\) , there are two nodes \(z_1\ne z_2\)  such that \(z_1\)  is a neighbor of \(y_1\)  and \(z_2\)  is a neighbor of \(y_2\) , and \(z_1, z_2 \ne x,y_1,y_2,y_3\)  because there are no triangles. We take \(y_1,y_2,y_3,z_1,z_2\)  into \(S\)  and into \(V_2\)
In all three cases nodes added to \(S\)  are removed from \(V^{\prime }\)  and their incident edges are removed from \(E^{\prime }\) .

*part-3
Find a 2-approximation on \((V^{\prime },E^{\prime })\)  and take its nodes into \(S\)  and into \(V_3\) .
\(S\) 

0.5em
Let \(V_1\)  be the vertices added to \(S\)  in the first part, let \(V_2\)  be the set of vertices added to \(S\)  in the second part and let \(V_3\)  be the set of vertices added to \(S\)  in the third part. For, for \(i=1,2,3\)  let \(W_i\)  denote the set of vertices that leave \(V^{\prime }\)  in phase \(i\) . The set \(W_i\)  contains \(V_i\)  and it also contains all vertices that leave \(V^{\prime }\)  because their degree in the remaining graph reached 0.
Further, for \(i=1,2,3\)  we denote \(s_i=|V_i|\) .
We first show some crucial properties that hold after the first part. We call every edge in \(G\)  a red edge, and every edge in \(G^2-G\)  is called a blue edge. For a subset \(F\)  of edges of \(G^2\) , we denote by \(F^{\mathrm {red}}\)  and \(F^{\mathrm {blue}}\)  the red and blue edges in \(F\) , respectively. Let \(R=(V^{\prime },E^{\prime })=(V_R,E_R)\)  be the remaining graph after the first part.
Lemma 13 lemma]lemma:VC1
The following properties hold for \(R\) .
(1) There are no triangles in \(R\) .
(2) \(E^{\mathrm {red}}_R\)  forms a matching.
(3) \(s_1 \ge E^{\mathrm {blue}}_R\) .

As an edge of \(G^2\)  can only be removed from \(E^{\prime }\)  if at least one of its endpoints is added to \(S\)  we obtain that the remaining graph \(R\)  equals \(G^2[V_R]\) , that is, it contains all edges induced by vertices in \(V_R=V^{\prime }\) . We need this property to prove all three parts.

The graph \(R\)  clearly has no triangles, as otherwise the loop started in Line  is not finished.

The set \(E^{\mathrm {red}}_R\)  forms a matching, as otherwise it has two adjacent edges \(\lbrace x,y\rbrace , \lbrace y,z\rbrace \)  with \(x,y,z\in V_R\) , but since these are red edges this implies that the edge \(\lbrace x,z\rbrace \)  is in \(E_R=G^2[V_R]\)  and so the triangle \(\lbrace x,y\rbrace , \lbrace y,z\rbrace , \lbrace z,x\rbrace \)  is contained in \(R\) , which is a contradiction.

We claim that for every edge \(e=\lbrace x,y\rbrace  \in E^{\mathrm {blue}}_R\) , there is at least one vertex \(v \in V_1\)  that forms a triangle with \(e\) . This is because there must be such a vertex in \(V\) , and if it is not in \(V_1\)  it has to still be in \(V_R=V\setminus V_1\)  but this implies the triangle \(\lbrace x,y,z\rbrace \)  in \(R\) . Moreover, it holds that if \(v\)  forms a triangle with \(e=\lbrace x,y\rbrace  \in E^{\mathrm {blue}}_R\)  then it does not form a triangle with any other edge \(e^{\prime } \in E^{\mathrm {blue}}_R\) : Assume it did and denote one of the endpoints of \(e^{\prime }\)  that is different from \(x\)  and \(y\)  by \(x^{\prime }\) . Then \(x,y\)  and \(x^{\prime }\)  are neighbors of \(v\)  in \(G\)  and \(x,y,x^{\prime }\in V_R\)  from which we can deduce that the edges \(e\) , \(\lbrace x,x^{\prime }\rbrace \)  and \(\lbrace x^{\prime },y\rbrace \)  are all part of \(R\)  and form a triangle, a contradiction.
Therefore, we have that \(s_1 \ge E^{\mathrm {blue}}_R\) .

We also keep track of the approximation factor we have so far. Let \(OPT_1\)  be an optimal cover for the edges of \(G^2\)  induced by \(W_1\)  and let \(opt_1 = |OPT_1|\) .
The triangles taken into \(V_1\)  are vertex disjoint and \(OPT_1\)  must take at least two nodes of every triangle while we add all three vertices of the triangle. This implies \(opt_1 \ge (2/3) s_1\) .
Next, we show that the properties for \(R\)  also hold after part 2. Let \(R^{\prime }=(V^{\prime },E^{\prime })=(V_{R^{\prime }},E_{R^{\prime }})\)  be the remaining graph after Line .
Lemma 14 lemma]lemma:VC2
The following properties hold for \(R^{\prime }\) .
(1) There are no triangles in \(R^{\prime }\) .
(2) \(E^{\mathrm {red}}_{R^{\prime }}\)  forms a matching.
(3) \(s_1 \ge E^{\mathrm {blue}}_{R^{\prime }}\) .
(4) \(s_1 \ge (3/2)|V_{R^{\prime }}|\) .

First note that we again have that \(R^{\prime }\)  equals \(G^2[V_{R^{\prime }}]\)  as an edge of \(G^2\)  can only be removed from \(E^{\prime }\)  if at least one of its endpoints is added to \(S\) .
Since we only remove nodes and edges, the graph \(R^{\prime }\)  retains the three properties of \(R\)  from Lemma  because these are monotone properties. That is, \(R^{\prime }\)  has no triangles, \(E^{\mathrm {red}}_{R^{\prime }}\)  forms a matching, and \(s_1 \ge E^{\mathrm {blue}}_{R^{\prime }}\) , where \(E^{\mathrm {blue}}_{R^{\prime }}\)  is the set of blue edges in \(R^{\prime }\) .
The graph \(R^{\prime }\)  has the additional property that for every \(v \in R^{\prime }\)  it holds that \(\deg _{E_{R^{\prime }}}(v) \ge 4\) , and since \(E^{\mathrm {red}}_{R^{\prime }}\)  forms a matching, it holds that for every \(v \in R^{\prime }\)  we have \(\deg _{E^{\mathrm {blue}}_{R^{\prime }}}(v) \ge 3\) . This gives that \(s_1 \ge E^{\mathrm {blue}}_{R^{\prime }} \ge (1/2)\sum _{v\in R^{\prime }}{\deg _{E^{\mathrm {blue}}_{R^{\prime }}}(v)} \ge (1/2) \cdot 3|V_{R^{\prime }}| = (3/2)|V_{R^{\prime }}|\) .
We also keep track of the approximation factor we have so far. Let \(OPT_2\)  be an optimal cover for the edges of \(G^2\)  induced by \(W_2\)  and let \(opt_2 = |OPT_2|\) .
For a node \(x\)  with \(\deg _{E^{\prime }}(x)=1\)  there is a single vertex taken into \(V_2\)  and \(OPT_2\)  must also take a vertex to cover that edge. For a node \(x\)  with \(\deg _{E^{\prime }}(x)=2\)  there are 3 vertices taken into \(V_2\)  and \(OPT_2\)  must take at least 2 nodes to cover the vertex-disjoint edges \(\lbrace z,y_1\rbrace ,\lbrace x,y_2\rbrace \) . Finally, for a node \(x\)  with \(\deg _{E^{\prime }}(x)=3\)  there are 5 nodes taken to \(V_2\) , and \(OPT_2\)  must take 3 nodes to cover the vertex-disjoint edges \(\lbrace y_1,z_1\rbrace ,\lbrace y_2,z_2\rbrace ,\lbrace x,y_2\rbrace \) . The latter dominates the ratio, giving that \(opt_2 \ge (3/5) s_2\)
Let \(OPT_3\)  be an optimal cover for the edges of \(G^2\)  induced by \(W_3\)  (these are the edges \(E_{R^{\prime }}\) ) and let \(opt_3 = |OPT_3|\) . Let \(s_3 = |V_3|\) . Because \(V_3\)  is a 2-approximation for \(R^{\prime }\) , we immediately get that \(opt_3 \ge (1/2) s_3\) . These three inequalities are encapsulated in the following lemma.
Lemma 15 lemma]lemma:OPTs
It holds that \(opt_1 \ge (2/3) s_1\) , \(opt_2 \ge (3/5) s_2\) , and \(opt_3 \ge (1/2) s_3\) .

We next show that the computed set actually is a vertex cover.
Lemma 16 lemma]lem:SvertexCover
At the end of the algorithm the set \(S=V_1\cup V_2\cup V_3\)  is a vertex cover of \(G^2\) .

We only remove an edge from \(E^{\prime }\)  if at least one of its endpoints is added to \(S\) .
Thus any edge that is not covered by a vertex in \(V_1\)  or \(V_2\)  is still contained in \(E^{\prime }\)  after phase 2 and any such edge is then covered by \(V_3\) .
We are now ready to prove Theorem REF .
(Proof of Theorem REF )
lem:SvertexCover shows that the returned set \(S=V_1\cup V_2\cup V_3\)  is a vertex cover and the runtime of the algorithm is polynomial.
We now bound the approximation factor. Let \(OPT\)  be an optimal solution for \(G^{2}\) , and let \(opt = |OPT|\)  and let \(s = |S|\) . It holds that \(opt \ge opt_1 + opt_2 + opt_3\)  because these are optimal solutions for the vertex-disjoint sets of edges \(W_1\) , \(W_2\)  and \(W_3\) . Since \(s=s_1 + s_2 + s_3\) , the approximation factor is \(\alpha = s/opt \le (s_1 + s_2 + s_3)/(opt_1 + opt_2 + opt_3)\) . We bound the value of \(\alpha \)  as follows:
From Lemma , we know that \(s_1 \ge (3/2)|V_{R^{\prime }}| \ge (3/2)s_3\) . Denoting \(c = s_1/s_3\) , we have that \(c \ge 3/2\) . We now have \(s = s_1 + s_2 + s_3 = s_2 + (c+1)s_3\) . By Lemma  and using \(s_1=c\cdot s_3\) , we have
\(opt &\ge opt_1 + opt_2 + opt_3 \ge (2/3) s_1 + (3/5) s_2 + (1/2) s_3 \\&= (3/5) s_2 + ((2/3)\cdot c+(1/2))s_3 = (3/5)s_2 + ((4c+3)/6))s_3~.\) 
We claim that \((4c+3)/6 \ge (3/5)(c+1)\) , and thus \(opt\ge (3/5)s_2 + (3/5)(c+1)s_3 = (3/5) (s_2 + (c+1)s_3) = (3/5)s\) , which proves that \(\alpha \le 5/3\) .
For \((4c+3)/6 \ge (3/5)(c+1)\)  to hold, we need \(5(4c+3) \ge 6\cdot 3(c+1)\) , that is, we need \(20c +15 \ge 18c+18\) , which is equivalent to \(2c \ge 3\) . This holds since our bound for \(c\)  is exactly \(c \ge 3/2\) , by Lemma .
By plugging in the result of theorem:VCcent in the second phase of the algorithm of thm:G2VC or theorem:VC-CC we obtain the following corollary.
Corollary 17 There exists a deterministic
\(\mathsf {CONGEST}\)  algorithm in which nodes only use polynomial computations and that computes a \(5/3\) -approximation for \(G^2\) -MVC in \(O(n)\)  rounds.
There exists a randomized
\(\mathsf {CONGESTED~CLIQUE}\)  algorithm in which nodes only use polynomial computations and that computes a \(5/3\) -approximation for \(G^2\) -MVC in \(O(\log n)\)  rounds.

We run the first phase of the algorithm from thm:G2VC (\(\mathsf {CONGEST}\) ) or theorem:VC-CC (\(\mathsf {CONGESTED~CLIQUE}\) ) with \(\varepsilon =1/2\) . Then, in the second phase we learn the remaining graph at a leader vertex which locally uses theorem:VCcent to compute a \(5/3\) -approximation for the remaining graph. The approximation factor is the maximum of \(1+\varepsilon =3/2\)  and \(5/3\) .

Distributed \(G^2\) -Minimum Vertex Cover (Lower Bounds)
In subsec:aloceBob we present the Alice-Bob lower bound framework developed in [3]} that we use to obtain quadratic and near-quadratic lower bounds for \(G^2\) -MVC and \(G^2\) -MDS (Section ). Then, in Sections REF  and REF  we use the framework to prove near-quadratic lower bounds for \(G^2\) -MWVC and \(G^2\) -MVC. In sec:VC-apx-limitations we show limitations of the framework and in sec:VChardness we show our conditional lower bound for \(G^2\) -MVC.
Reduction from Communication Complexity: The Alice Bob Framework
To prove our lower bounds
we use the known framework of reductions from 2-party communication problems or reduce to lower bounds that have been proven with this framework. This framework was pioneered by Peleg and Rubinovich [3]}, and has been used extensively since then to obtain lower bounds for bandwidth restricted models (see, e.g., [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}).
The novelty in our proofs lies in the constructions of the graph families that give our reductions. We first recall the framework itself, as follows.
The 2-party communication setting consists of two players, Alice and Bob, who are given two input strings, \(x,y\in \left\lbrace 0,1\right\rbrace ^K\)  respectively,
and need to evaluate some given function \(f:\left\lbrace 0,1\right\rbrace ^K\times \left\lbrace 0,1\right\rbrace ^K\rightarrow \left\lbrace \mathrm {true},\mathrm {false}\right\rbrace \)  on their inputs.
The maximal number of bits, over all inputs, exchanged in a protocol \(\pi \)  that computes
\(f\)  is the communication complexity of \(\pi \) and is denoted \(CC(\pi )\) . The communication complexity of the function \(f\) is the minimum of \(CC(\pi )\)  over all deterministic protocols \(\pi \)  that compute \(f\)  and is denoted \(CC(f)\) . In a similar manner, for randomized protocols, the randomized communication complexity of \(f\)  is denoted \(CC^R(f)\) .
In the set disjointness problem, the problem is to compute a boolean function
\(DISJ_K\)  defined as \(DISJ_K(x, y) = \mathrm {false}\)  if and only if there is an index \(0\le i\le K-1\)  such that \(x_i=y_i=1\) . It is well known that that \(CC(DISJ_K), CC^R(DISJ_K)\)  are both \(\Theta (K)\)  (see, e.g., [13]}).
Definition 18 (Family of Lower Bound Graphs [14]})definition]def:family
Fix an integer \(K\) , a function \(f:\left\lbrace 0,1\right\rbrace ^K\times \left\lbrace 0,1\right\rbrace ^K\rightarrow \left\lbrace \mathrm {true},\mathrm {false}\right\rbrace \)  and a graph predicate \(P\) . A family of graphs
\( \left\lbrace G_{x,y}=(V,E_{x,y}) \mid x,y \in \left\lbrace 0,1\right\rbrace ^K\right\rbrace \) 
with a partition \(V=V_A\dot{\cup }V_B\)  is said to be a family of lower bound graphs for the \(\mathsf {CONGEST}\)  model w.r.t. \(f\)  and \(P\) if the following properties hold:


Only the existence or the weight of edges in \(V_A\times V_A\)  may depend on \(x\) ;


Only the existence or the weight of edges in \(V_B\times V_B\)  may depend on \(y\) ;

\(G_{x,y}\)  satisfies the predicate \(P\)  iff \(f(x,y)=\mathrm {true}\) .


Theorem 19 ([14]})theorem]thm: general lb framework
Fix a function \(f:\left\lbrace 0,1\right\rbrace ^K\times \left\lbrace 0,1\right\rbrace ^K\rightarrow \left\lbrace \mathrm {true},\mathrm {false}\right\rbrace \)  and a graph predicate \(P\) . If there is a family \(\lbrace G_{x,y}\rbrace \)  of lower bound graphs for the \(\mathsf {CONGEST}\)  model w.r.t. \(f\)  and \(P\)  with cut edge set \(C = E(V_A, V_B)\) , then any deterministic algorithm for deciding \(P\)  in the \(\mathsf {CONGEST}\)  model requires \(\Omega (CC(f)/|C|\log n)\)  rounds, and any randomized algorithm for deciding \(P\)  in the \(\mathsf {CONGEST}\)  model requires \(\Omega (CC^R(f)/|C|\log n)\)  rounds.


\(\mathsf {CONGEST}\) : Quadratic Lower Bound for Exact \(G^2\) -MWVC (Warmup)
We show an \(\Omega (n^2)\)  lower bound for exact computation of \(G^2\) -MWVC. We later make it apply also for \(G^2\) -MVC.
Theorem 20 theorem]thm:MWVC-lower-bound-main-theorem
Any distributed algorithm in the \(\mathsf {CONGEST}\)  model which given an input graph \(G\) , computes the minimum weighted vertex cover of \(G^{2}\)  requires \(\tilde{\Omega }(n^{2})\)  rounds.

To prove this lower bound, we use the framework of reductions from 2-party communication problems as stated in Theorem .
A naive attempt is to try and use the vertex cover lower bound graph \(G_{x,y}\)  from [14]} and replace each edge with a vertex of weight 0,
in order to get a new lower bound graph \(H_{x,y}\)  with the same size of solution for \(H^2\)  as in \(G\) .
The issue is that in the graph \(H_{x,y}\) , the number of vertices is \(O(m)\)  where \(m = O(n^{2})\)  is the number of edges in \(G_{x,y}\) . This is a major issue if we want super linear lower bounds as a quadratic lower bound in \(G_{x,y}\)  only gives a linear lower bound for \(H^{2}_{x,y}\) . So instead, we modify the lower bound graph construction of [14]} in a subtle manner to show an \(\Omega (n^2)\)  lower bound for computing exact MWVC in \(G^2\) .
The \(G\) -MVC lower bound graph family \(G_{x,y}\)  from [14]}:  See fig:censor-hillel-mvc-lb-graph for an illustration of \(G_{x,y}\) . At a high level, the lower bound graph of [14]} has four cliques \(A_1, A_2, B_1, B_2\)  of size \(k\)  which are called the row vertices and \(2 \log _2 k\)  4-cycles which are called bit-gadgets. There are \(\log _{2} k\)  4-cycles for the row vertices \(A_{1}, B_{1}\)  and the other \(\log _{2} k\)  4-cycles are for the row vertices \(A_{2}, B_{2}\) 
The \(i^{th}\)  bit gadget for \(A_{1}, B_{1}\)  is a 4-cycle with vertices \(t_{A_{1}}^{i}, f_{A_{1}}^{i}, t_{B_{1}}^{i}, f_{B_{1}}^{i}\) . The vertices in \(a_{1}^{i} \in A_{1}\)  are connected to the bit gadget vertices \(f_{A_{1}}^j, t_{A_{1}}^j\)  depending on the binary representation of \(i-1\) .
Specifically, \(a_1^i\)  is connected to \(t_{A_{1}}^{j}\)  if the \(j^{th}\)  bit of the binary representation of \(i-1\)  is 1 and it is connected to \(f_{A_{1}}^{j}\)  otherwise.
For example, the vertex \(a_{1}^{1}\)  is connected to all the \(f_{A_{1}}\)  vertices. The connections for other row vertices in \(A_{2}, B_{1}, B_{2}\)  to the corresponding bit gadget vertices are similar.
An edge between vertices \(a_{1}^{i} \in A_1\)  and \(a_{2}^{j} \in A_2\)  is added iff \(x_{ij} = 0\)  in the set disjointness input \(x \in {\lbrace 0,1\rbrace }^{k^{2}}\) . Similarly, an edge between vertices \(b_{1}^{i} \in B_1\)  and \(b_{2}^{j} \in B_2\)  is added iff \(y_{ij} = 0\)  in the set disjointness input \(y \in {\lbrace 0,1\rbrace }^{k^{2}}\) .
<FIGURE>\(G^{2}\) -MWVC lower bound graph family \(H_{x,y}\) :  In order to construct our lower bound graph \(H_{x,y}\) , we first start with \(G_{x,y}\) . We take the edges incident on the \(2 \log _2 k\)  bit-gadget vertices and replace each edge \(e\)  with a path gadget \(P_{e}\)  which is a single vertex \(p_{e}\)  having weight 0, which connected to both endpoints of \(e\) .
Note that up to this point, we have added \(O(k \log k)\)  vertices of weight 0, so we do not have too many vertices in \(H_{x,y}\) . But we cannot replace each edge between the cliques \(A_1, A_2\)  and cliques \(B_1, B_2\)  by path gadgets because doing so might introduce \(O(k^2)\)  vertices in the worst case.
To overcome this issue, we have the cliques share their path gadgets. In particular, we connect a new zero weight vertex \(p_{a}^{i}\)  to the vertex \(a_{1}^{i} \in A_1\)  for each \(1 \le i \le k\)  and for every edge between \(a_1^{i} \in A_1\)  and \(a_2^{j} \in A_2\)  in \(G_{x,y}\) , we add a corresponding edge between \(p_{a}^{i}\)  and \(a_{2}^{j}\) . We do the same for the row vertices \(B_{1}, B_{2}\)  by connecting a new zero weight vertex \(p_{b}^{i}\)  to the vertex \(b_{1}^{i} \in B_{1}\)  for each \(1 \le i \le k\) . Therefore, the number of vertices in \(H_{x,y}\)  is still \(O(k \log k)\) . See fig:MWVC-lower-bound-path-gadgets for an illustration. Note that all vertices in \(H_{x,y}\)  that come from \(G_{x,y}\)  have weight 1 and all the other vertices have weight 0.
<FIGURE>We formally state our reduction between the lower bound graphs in the following lemma.
Lemma 21 lemma]lemma:sizeMWVC
The graph \(H_{x,y}^2\)  has a vertex cover of weight \(W\)  if and only if the graph \(G_{x,y}\)  has a vertex cover of weight \(W\) .

For the forward direction, we can include all the zero weight vertices in any vertex cover of \(H_{x,y}^2\)  without affecting the weight. The edges that need to be covered are between pairs of vertices that are connected by some path gadget, plus the edges of the cliques \(A_{1}, A_{2}, B_{1}, B_{2}\) . These are exactly the edges in \(G_{x,y}\)  and therefore, the non-zero weight vertices in a vertex cover of \(H_{x,y}^2\)  form a valid vertex cover of \(G_{x,y}\) . For the reverse direction, notice that a vertex cover of \(G_{x,y}\)  along with all zero-weight vertices of \(H_{x,y}\)  covers all the edges in \(H_{x,y}^2\) .
[Proof of thm:MWVC-lower-bound-main-theorem]
Censor-Hillel et al. [14]} show that the MVC lower bound graph \(G_{x,y}\)  is a family of lower bound graphs for the \(\mathsf {CONGEST}\)  model wrt the set-disjointness function \(f=DISJ_{k^{2}}\)  and the predicate \(P_{G}\)  which asks whether the graph \(G\)  has a vertex cover of size \(W = 4(k - 1) + 4\log k\) . The vertices of \(G_{x,y}\)  are partitioned into \(V_{A} = A_{1} \cup A_{2} \cup \lbrace f_{S}^{i}, t_{S}^{i} \mid 1 \le i \le \log _{2} k, S \in \lbrace A_{1}, A_{2}\rbrace \rbrace \)  and \(V_{B} = V(G_{x,y}) \setminus V_{B}\) , with the cut size being \(|E(V_{A}, V_{B})| = O(\log k)\) .
By lemma:sizeMWVC, we know that \(G_{x,y}\)  satisfies the predicate \(P_{G}\)  iff the graph \(H_{x,y}\)  satisfies the predicate \(P_{H}\)  which asks whether the input graph has a weighted \(G^{2}\) -vertex cover of weight \(W\) . Recall that the number of vertices in \(H_{x,y}\)  is \(O(k \log k)\) .
Define \(V_{A}^{\prime } = V_{A} \cup \lbrace P_{e} | e = \lbrace u, v\rbrace  \text{ and } u, v \in V_{A}\rbrace \cup \lbrace p_{a}^{i} \mid 1 \le i \le k\rbrace \)  and \(V_{B}^{\prime } = V(H_{x,y}) \setminus V_{A}^{\prime }\) . With these definitions of \(V_{A}^{\prime }\)  and \(V_{B}^{\prime }\) , the size of the cut of \(H_{x,y}\)  is \(|E(V_{A}^{\prime }, V_{B}^{\prime })| = O(\log k)\) .
The graph \(H_{x,y}\)  with partition \(V_{A}^{\prime }, V_{B}^{\prime }\)  is a family of lower bound graphs wrt the set-disjointness function \(f=DISJ_{k^{2}}\)  and the predicate \(P_{H}\) . Therefore, thm: general lb framework gives an \(\tilde{\Omega }(k^2)\)  lower bound for the problem of deciding whether a graph with \(O(k \log k)\)  vertices has a vertex cover of weight \(W = 4(k - 1) + 4 \log _{2} k\)  as shown in [14]}. Therefore for a graph with \(n\) -vertices we get an \(\tilde{\Omega }(n^{2})\)  lower bound which completes the proof of thm:MWVC-lower-bound-main-theorem.

\(\mathsf {CONGEST}\) : Quadratic Lower Bound for Exact \(G^2\) -MVC
In this section we show a quadratic lower bound for exact minimum vertex cover with no weights.
Theorem 22 theorem]thm:MVC-lower-bound-main-theorem
Any distributed algorithm in the \(\mathsf {CONGEST}\)  model which given an input graph \(G\) , computes the minimum vertex cover of \(G^{2}\)  requires \(\tilde{\Omega }(n^{2})\)  rounds.

The Dangling Path Gadget:  The lower bound graph construction is inspired by the weighted construction, but here we need to define a new gadget in order to remove the vertex weights. For an edge \(e \in G_{x,y}\) , let \(DP_{e}\)  be a gadget having 3 vertices \(DP_{e}[1], DP_{e}[2], DP_{e}[3]\)  connected in a path. The vertex \(DP_{e}[1]\)  is connected to both the endpoints of \(e\) . We call \(DP_{e}\)  a dangling path gadget and the path \(DP_{e}[1], DP_{e}[2], DP_{e}[3]\)  is called a dangling path. We refer to \(DP_{e}[3]\)  as the leaf of the dangling path gadget \(DP_{e}\) . See fig:MVC-lower-bound-dangling-path-gadget (left) for an illustration.
\(G^{2}\) -MVC lower bound graph family \(H_{x,y}\) :  In order to construct our lower bound graph \(H_{x,y}\) , we first start with \(G_{x,y}\) . We take each edge \(e \in G_{x,y}\)  that is incident on the \(2 \log _2 k\)  bit-gadget vertices and replace each edge \(e\)  with a dangling path gadget \(DP_{e}\) . Note that there are \(O(k \log k)\)  edges incident on bit gadget vertices and therefore we have not introduced too many path gadget vertices.
The remaining edges are those between the row vertices \(A_{1}, B_{1}, A_{2}, B_{2}\) .
These can be \(O(k^2)\)  in number and so we cannot add a dangling path gadget for each edge.
For each row vertex \(a_{1}^{i} \in A_{1}\) , we add a shared path gadget \(A_{1}^{i}\) .
The gadget is similar to the dangling path gadget in that it has 3 vertices \(A_{1}^{i}[1], A_{1}^{i}[2], A_{1}^{i}[3]\)  connected to form a path.
The vertex \(A_{1}^{i}[1]\)  is connected to \(a_{1}^{i}\) . We add a similar shared path gadget \(B_{1}^{i}\)  for the \(i^{th}\)  row vertex \(b_{1}^{i} \in B_{1}\) .
For each edge between \(a_{1}^{i}\)  and \(a_{2}^{j}\)  in \(G_{x,y}\) , we add a corresponding edge
between \(A_{1}^{i}[1]\)  and \(a_{2}^{j}\)  in \(H_{x,y}\) . And similarly for each edge between \(b_{1}^{i}\)  and \(b_{2}^{j}\)  in \(G_{x,y}\) , we
add a corresponding edge between \(B_{1}^{i}[1]\)  and \(b_{2}^{j}\)  in \(H_{x,y}\) . See fig:MVC-lower-bound-dangling-path-gadget (right) for an illustration.
Note that adding shared path gadgets results in only \(O(k)\)  additional path gadget vertices.
<FIGURE>Lemma 23 lemma]lem:dangling-rearrangement
Any vertex cover of \(H_{x,y}^2\)  of size \(c\)  can be modified to a vertex cover of size at most \(c\)  that contains no vertex of index 3 in any dangling path gadget or shared path gadget. Equivalently, this modified vertex cover contains all vertices in every dangling path gadget except the leaf.

Fix a particular dangling path gadget or shared path gadget \(P\)  such that \(P[3]\)  is in the vertex cover. Note that \(P[3]\)  is only connected to vertices \(P[1]\)  and \(P[2]\)  since it is more than 2-hops apart from vertices not in \(P\) . Moreover, \(P[1], P[2], P[3]\)  form a triangle in \(H_{x,y}^2\) . Therefore, any vertex cover must have at least 2 vertices from this triangle. So if \(P[3]\)  is present in the vertex cover, we can remove it and add any other vertex in the triangle that was excluded (there can be at most one such vertex), and we still cover all the edges in \(H^{2}_{x,y}\) .
Since \(P[3]\)  is not in the vertex cover, \(P[1], P[2]\)  have to be in the vertex cover as these three vertices form a triangle. Doing this process for all dangling path gadgets and shared path gadgets gives us the lemma.
We now state the reduction from our lower bound graph \(H_{x,y}^2\)  to the lower bound graph \(G_{x,y}\)  of [14]} in the following lemma.
Lemma 24 
The graph \(H_{x,y}^2\)  has a minimum vertex cover of size \(W + 2(2k + 4k\log _2 k + 8\log _2 k)\)  if and only if the graph \(G_{x, y}\)  has a minimum vertex cover of size \(W\) .

For the forward direction, consider the vertices from the dangling path gadgets in a minimum vertex cover \(C_H\)  of \(H_{x,y}^2\) . By lem:dangling-rearrangement, we can assume that for each dangling path gadget and shared path gadget \(P\) , the vertices \(P[1],P[2]\)  belong to \(C_H\)  and the vertex \(P[3]\)  does not belong to \(C_{H}\) . There are \(2k + 4k\log _2 k + 8\log _2 k\)  such gadgets in \(H_{x, y}\) . Therefore, \(C_{H}\)  contains \(2(2k + 4k\log _2 k + 8\log _2 k)\)  vertices which cover all the edges that have a dangling (or shared) path gadget vertex as an endpoint.
The rest of the vertices in \(C_H\)  have to cover all the edges formed by pairs of non-gadget vertices that have a dangling (or shared) path gadget connecting them. These are exactly the edges in \(G_{x,y}\)  and therefore, the non-gadget vertices in \(C_H\)  must form a minimum vertex cover of \(G_{x,y}\) , since otherwise we can create a smaller cover of \(H_{x,y}^2\)  than \(C_H\)  by taking the vertices corresponding to the MVC of \(G_{x,y}\)  instead.
For the reverse direction, consider the MVC \(C_G\)  of \(G_{x,y}\)  having size \(W\) . We can take all the \(2(2k + 4k\log _2 k + 8\log _2 k)\)  vertices indexed \(1, 2\)  from all the dangling path gadgets and shared path gadgets, plus the corresponding \(W\)  vertices in \(C_G\)  to form a vertex cover of \(H_{x,y}^2\) . We cannot form a smaller vertex cover in \(H_{x, y}^2\) , because otherwise we could extract a vertex cover of \(G_{x, y}\)  that is smaller than \(C_G\)  using lem:dangling-rearrangement, which would contradict the optimality of \(C_G\) .
[Proof of thm:MVC-lower-bound-main-theorem]
Censor-Hillel et al. [14]} show that the MVC lower bound graph \(G_{x,y}\)  is a family of lower bound graphs for the \(\mathsf {CONGEST}\)  model wrt the set-disjointness function \(f=DISJ_{k^{2}}\)  and the predicate \(P_{G}\)  which asks whether the graph \(G\)  has a vertex cover of size \(W = 4(k - 1) + 4\log k\) . The vertices of \(G_{x,y}\)  are partitioned into \(V_{A} = A_{1} \cup A_{2} \cup \lbrace f_{S}^{i}, t_{S}^{i} \mid 1 \le i \le \log _{2} k, S \in \lbrace A_{1}, A_{2}\rbrace \rbrace \)  and \(V_{B} = V(G_{x,y}) \setminus V_{B}\) , with the cut size being \(|E(V_{A}, V_{B})| = O(\log k)\) .
By lemma:sizeMVC, we know that \(G_{x,y}\)  satisfies the predicate \(P_{G}\)  iff the graph \(H_{x,y}\)  satisfies the predicate \(P_{H}\)  which asks whether the input graph has a \(G^{2}\) -vertex cover of size \(W + 2(2k + 4k\log _2 k + 8\log _2 k)\) . Recall that the number of vertices in \(H_{x,y}\)  is \(O(k \log k)\) .
Define \(V_{A}^{\prime } = V_{A} \cup \lbrace DP_{e} | e = \lbrace u, v\rbrace  \text{ and } u, v \in V_{A}\rbrace \cup \lbrace A_{1}^{i} \mid 1 \le i \le k\rbrace \)  and \(V_{B}^{\prime } = V(H_{x,y}) \setminus V_{A}^{\prime }\) . With these definitions of \(V_{A}^{\prime }\)  and \(V_{B}^{\prime }\) , the size of the cut of \(H_{x,y}\)  is \(|E(V_{A}^{\prime }, V_{B}^{\prime })| = O(\log k)\) .
The graph \(H_{x,y}\)  with partition \(V_{A}^{\prime }, V_{B}^{\prime }\)  is a family of lower bound graphs wrt the set-disjointness function \(f=DISJ_{k^{2}}\)  and the predicate \(P_{H}\) . Therefore, thm: general lb framework gives an \(\tilde{\Omega }(k^2)\)  lower bound for the problem of deciding whether a graph with \(O(k \log k)\)  vertices has a vertex cover of size \(W + 2(2k + 4k\log _2 k + 8\log _2 k)\)  where \(W = 4(k - 1) + 4 \log _{2} k\) . Therefore for a graph with \(n\) -vertices we get an \(\tilde{\Omega }(n^{2})\)  lower bound which completes the proof of thm:MVC-lower-bound-main-theorem.

Limitations of thm: general lb framework:
With the goal of finding how good is the complexity we obtain for a \((1+\varepsilon )\) -approximation of MVC in sssec:UBunweightedVC, we tried to prove a lower bound for it, with respect to \(n\)  (We mention that the \(1/\varepsilon \)  term in the complexity is unavoidable, due to a straightforward adaptation of the lower bound given in [24]}. The quadratic lower bounds in this paper, as well as in previous papers [14]}, [26]}, are all obtained by lower bound graphs of small cuts (logarithmic size). We show that any construction which has a cut of size \(o(n)\)  cannot give any super-constant lower bound for a \((1+\varepsilon )\) -approximation of MVC, for any \(\varepsilon = O(1)\) .
Lemma 25 lemma]lemma:limitationVC
Let \(P\)  be a predicate that implies a \((1+\varepsilon )\) -approximation for \(G^{2}\) -MVC. If \(\lbrace G_{x,y}\rbrace \)  is a family of lower bound graphs with respect to a function \(f\)  and the predicate \(P\) , which has a cut \(C\)  of size \(o(n)\) , then thm: general lb framework cannot give a super-constant lower bound for a distributed algorithm for deciding \(P\) .

The two players construct a graph from the family according to their inputs \(x\)  and \(y\) . Each player takes into the cut all of its cut vertices, denoted \(C_A\)  and \(C_B\) , respectively, and whatever other vertices from \(V_A \setminus C_A\)  (respectively, \(V_B\setminus C_A\) ) that form an optimal cover of the edges of \(G^2_{x,y}\)  that remain after taking the cut vertices \(C_A \cup C_B\) . The players inform each other about the number of vertices each one took into the cover and conclude the size of the computed cover. This requires exchanging \(O(\log {n})\)  bits, thus \(CC(f) \le O(\log {n})\) .
Our first claim is that the set of selected vertices is indeed a cover. This is because taking all of the cut vertices \(C_A \cup C_B\)  into the cover promises that any yet uncovered edge of \(G^2_{x,y}\)  has both endpoints in \(V_A \setminus C_A\)  or both in \(V_B \setminus C_B\) , and thus adding any cover on each side gives a cover for \(G^2_{x,y}\) .
Second, we claim that the computed cover is a \((1+\varepsilon )\) -approximation of an optimal solution. The reason is that the computed cover takes an optimal cover of the edges of \(G^2_{x,y}\)  that have both endpoints in \(V_A \setminus C_A\)  or both in \(V_B \setminus C_B\) , and since these are disjoint sets then an optimal solution must take at least this number of vertices. The computed solution then has to account also for the cut vertices \(C_A \cup C_B\) . However, these are only \(o(n)\) , while we know from lem:structAllNodesVC that the size of an optimal solution is at least \(n/2\) , which gives an approximation factor of \(1+o(1)\) .
We are now ready to complete the proof. Suppose that \(G_{x,y}\)  is used with some function \(f\)  to show a lower bound for a \((1+\varepsilon )\) -approximation for \(G^{2}\) -MVC using thm: general lb framework. Then this lower bound is \(\Omega (CC(f)/|C|\log n)\) . But \(CC(f) \le O(\log {n})\)  and so no super-constant lower bound can be derived with this approach using small cuts.

Conditional Hardness for \((1+\epsilon )\) -Approximation
Theorem 26 
Let \(\delta , \alpha \)  be constants in \((0,1)\) . If for every \(\varepsilon \in (0,1)\)  there is a \((1+\varepsilon )\) -approximation algorithm for MVC of \(G^2\)  that completes in \(O(n^\alpha /\varepsilon )\)  rounds, then there is a \((1+\delta )\) -approximation algorithm for MVC of \(G\)  that completes in \(\tilde{O}(D + n^{(4(1+\alpha )+2\rho )/3})\)  rounds, where \(\rho =\log (1/\delta )/\log {n}\) .

Let \(ALG\)  be a \((1+\varepsilon )\) -approximation algorithm for MVC on \(G^2\)  that completes in \(O(n^\alpha /\varepsilon )\)  rounds. The high-level goal is to deduce an approximate solution for MVC of \(G\)  given the approximate solution for MVC of \(H^2\) , for a related graph \(H\) . An obstacle in doing so is that we will need to run \(ALG\)  with a value of \(\varepsilon \)  that depends on the size of the optimal vertex cover of \(G\) , which we denote by \(OPT\) , and for this we need \(OPT\)  to be sufficiently large. To this end, we will first find a very rough approximation for \(OPT\) , and if it is not sufficiently large then we resort computing a \((1+\delta )\) -approximation for it using the parametrized approach of [24]}.
Formally, we define \(\beta =(2(1+\alpha )+\rho )/3\) . We run the 2-approximation algorithm for MVC on \(G\)  given by [28]}, which takes \(O(\log n\log \Delta /\log ^2\log \Delta )\)  rounds to complete.This is the state-of-the-art for a 2-approximation. We note that we could use here any constant approximation algorithm but we omit \(\operatorname{\text{{\rm poly}}}\log n\)  factors anyhow. Within another \(O(D)\)  rounds the nodes learn the size of the given solution, denoted by \(SOL\) . Let \(\gamma = \log {(SOL/2)}/\log n\) , implying that \(n^{\gamma } = SOL/2\) .
We now consider two cases, depending on whether \(\gamma \)  is smaller than \(\beta \)  or is at least \(\beta \) . If \(\gamma <\beta \)  then we run the \((1+\delta )\) -approximation algorithm for MVC of \(G\)  given by [24]}, which takes \(O(n^{2\gamma })\)  rounds. Because \(\gamma <\beta \) , we have that in this case our algorithm completes within \(O(\operatorname{\text{{\rm poly}}}\log (n) + D + n^{2\gamma }) = \tilde{O}(D+ n^{2\beta })\)  rounds.
Otherwise, \(\gamma \)  is at least \(\beta \) . In this case we define a graph \(H\)  that is obtained from the graph \(G\)  by replacing each edge \(e =\lbrace w,u\rbrace  \)  in \(G\)  with dangling path gadget \(DP_e\) , as described in Section REF . Recall that \(DP_e\)  is a path on three vertices \(p_{e}^{1}, p_{e}^{2}, p_{e}^{3}\)  which is connected by \(p_e^1\)  to both \(u\)  and \(w\) . We simulate an execution of \(ALG\)  for MVC of \(H^2\)  with \(\varepsilon =\delta n^{\beta }/3m = n^{\beta -\rho }/3m\) . By our assumption, executing \(ALG\)  on \(H\)  completes in \(O(n_H^\alpha /\varepsilon )\)  rounds, where \(n_H = O(m)\)  is the number of nodes in \(H\)  (here \(m\)  is the number of edges in \(G\) ). For the simulation of \(ALG\)  on \(H\) , the nodes of \(G\)  simply assign each edge to one arbitrary endpoint (say, the one with the smaller identifier) and each node in \(G\)  simulates itself and the nodes of the gadgets that correspond to the edges that are assigned to it. Since the simulated nodes of each gadget are only connected with a single edge to the other endpoint of the original edge, this simulation incurs no overhead, thus completes in \(O(m^\alpha /\varepsilon )\)  rounds.
Let \(C\)  be the set of the original nodes of \(G\)  (the non-gadget nodes) that \(ALG\)  takes into the cover \(C_H\)  of \(H^2\)  that it produces. Our first claim is that \(C\)  is a cover of \(G\) . This follows since for every edge \(e=\lbrace u,w\rbrace \)  in \(G\) , it holds that \(\lbrace u,w\rbrace \)  is in \(H^2\) , and thus at least one of its endpoints has to be in \(C_H\) . Further, we claim that \(C\)  cannot be too large compared with \(OPT\) . To see this, note that any cover of \(H^2\)  must take at least 2 nodes of every gadget, and hence \(C \le C_H - 2m\) . Moreover, the size of any optimal solution \(OPT_H\)  for \(H^2\)  is exactly \(OPT_H = OPT + 2m\) , because any smaller solution either does not take 2 nodes of every gadget or induces a cover for \(G\)  that is smaller than \(OPT\) , either of which is impossible.
Hence, we have
\(C \le C_H - 2m \le (1+\varepsilon )OPT_H -2m = (1+\varepsilon )(OPT+2m)-2m = OPT(1+\varepsilon (1+2m/OPT)).\) 
This means that the approximation factor we get is
\(1+ \varepsilon (1+2m/OPT)=1 +(\delta n^{\beta }/3m)(1+2m/n^{\gamma }) \le 1+(\delta n^{\beta }/m)(m/n^\gamma ) = 1+\delta (n^{\beta -\gamma }) \le 1+\delta .\) 
The time the simulation takes is \(O(m^\alpha /\varepsilon )= O(m^\alpha \cdot m/(\delta n^\beta ) ) = O( n^{2+2\alpha -\beta +\rho })\) .
Thus, the total number of rounds for the algorithm is \(\tilde{O}(D+n^{2\beta } + n^{2+2\alpha -\beta +\rho })\) . Since \(\beta =(2(1+\alpha )+\rho )/3\) , we get a number of rounds which is \(\tilde{O}(D+n^{(4(1+\alpha )+2\rho )/3})\) .
In particular, Theorem REF  tells us that going below \(\alpha =1/2\)  for small values of \(\varepsilon \)  would yield a sub-quadratic algorithm for any constant approximation \((1+\delta )\)  for \(G\) , which would answer a major open question in distributed MVC approximation.
Corollary 27 
Let \(\delta \)  be a constant in \((0,1)\) . If for every \(\varepsilon \in (0,1)\)  there is a \((1+\varepsilon )\) -approximation algorithm for MVC of \(G^2\)  that completes in \(o(n^{1/2}/\varepsilon )\)  rounds, then there is a \((1+\delta )\) -approximation algorithm for MVC of \(G\)  that completes in \(o(n^2)\)  rounds.

Corollary REF  says that there is still a gap between our \(O(n/\varepsilon )\) -round algorithm of Section REF  and an algorithm that would imply a non-trivial runtime for \(G\) . We mention again that the \(1/\varepsilon \)  term in the complexity is unavoidable, due to a straightforward adaptation of the lower bound given in [24]}.

Distributed \(G^2\) -Minimum Dominating Set
An \(O(\log n)\) -Approximation for \(G^2\) -MDS (Randomized)
Theorem 28 
There is a randomized distributed \(\mathsf {CONGEST}\)  model algorithm, which given an input graph \(G\)  computes an \(O(\log \Delta )\) -approximate solution to the MDS problem on \(G^{2}\)  in \(\text{poly}\log n\)  rounds.

We simulate the algorithm proposed in [1]} for approximating MDS in \(G\) . The algorithm guarantees an \(O(\log \Delta )\)  approximation in \(O(\log n \log \Delta )\)  roundsIf one is careful with constants in the analysis of [1]}, the approximation factor can be shown to be \(8 H_{k}\)  where \(H_{k}\)  is the \(k^{th}\)  harmonic number and \(k \le \Delta ^{2}\)  is the maximum number of vertices that can be dominated by a single vertex.. Their algorithm for \(G\)  has the following steps in each round:

Each vertex \(v\)  computes its rounded density \(\rho _v\) , where \(\rho _{v}\)  is the number of uncovered vertices that \(v\)  covers rounded up to the closest power of 2. Vertex \(v\)  sends this value to its 2-hop neighbors in \(G\) . Here \(C_{v}\)  is the number of uncovered vertices that \(v\)  covers.

Each vertex \(v\)  such that \(\rho _v \ge \rho _u\)  for each \(u\)  in its 2-neighborhood is a candidate. Vertex \(v\)  informs its neighbors that it is a candidate.

Each candidate \(v\)  chooses a random number \(r_v \in \lbrace 1, \dots , n^4\rbrace \)  and sends it to its neighbors.

Each uncovered vertex that is covered by at least one of the candidates, votes for the first candidate that covers it according to the order of the values \(r_v\) . If there is more than one candidate with the same minimum value, it votes for the one with the minimum ID.

If \(v\)  receives at least \(|C_v|/8\)  votes from vertices it covers then it is added to the dominating set.

All vertices that are covered output 0, and \(v\)  outputs 1 if and only if it was added to the dominating set in the previous step.

We wish to simulate this algorithm on the graph \(G^{2}\)  while the network is still \(G\) . This poses some interesting congestion problems when \(v\)  tries to estimate the number of uncovered 2-hop neighbors of each vertex in \(G\)  and the number of votes that it receives from its 2-hop neighbors. The following lemma allows us to get this estimate quickly in a randomized manner.
Lemma 29 lemma]lem:sampling-estimation
Let \(U \subseteq V\)  be an arbitrary set of vertices. If each vertex knows whether or not it belongs to \(U\) , it is possible to get an estimate \(\tilde{d_{v}}\)  of the quantity \(d_{v} = |N_{2}(v) \cap U|\)  for all vertices \(v\)  such that with high probabilty
\(d_{v}(1-\varepsilon ) \le \tilde{d_{v}} \le (1+\varepsilon )d_{v}\) 
for a constant \(\varepsilon \in (1,1/4)\) , in \(O(\log n)\)  rounds in the \(\mathsf {CONGEST}\)  model.

We use a simplified version of the estimation algorithm provided in [33]}. In order to estimate \(\sum _{i=1}^{k}{y_{i}}\) , the algorithm generates \(r\)  independent random \(W_{1}^{i}, \dots , W_{r}^{i}\)  such that each \(W_{j}^{i}\)  is distributed according to the exponential distribution with mean \(1/y_{i}\)  for each \(1 \le i \le k\) .
The algorithm exploits the following property of exponential random variables: for each \(1 \le j \le r\)  the random variable \(\tilde{W_{j}} = \min _{1 \le i \le k}{W_{j}^{i}}\)  is distributed exponentially with mean \(1/\tilde{y}\)  where \(\tilde{y} = \sum _{i=1}^{k}{y_{i}}\) . Therefore, the quantity we want to estimate is the reciprocal of the expectation of \(\tilde{W_{j}}\) . And the \(r\)  independent samples give us concentration around this expectation as shown in the following lemma which is a consequence of Cramér's Theorem ([34]}, pp. 30, 35).
Lemma 30 
Let \(\tilde{W_{1}}, \tilde{W_{2}}, \dots , \tilde{W_{r}}\)  be iid exponential random variables with mean \(\lambda \) . Let \(\tilde{W} = \frac{1}{r}\sum _{j=1}^{r}{\tilde{W_{j}}}\) . Then for any \(\varepsilon \in (0, 1/2)\) :
\(Pr\left( \left| \tilde{W} - \lambda \right| \ge \varepsilon \lambda \right) \le exp(-\varepsilon ^{2}r/3)\)

Therefore, if we use \(r = \log n\) , then we get that with high probability, \((1-\varepsilon ) 1/\tilde{y} \le \tilde{W} \le (1+\varepsilon )1/\tilde{y}\)  which also implies \((1-\varepsilon ) \tilde{y} \le 1/\tilde{W} \le (1+2\varepsilon )\tilde{y}\)  for \(\varepsilon \in (0,1/2)\) .
Now we have every vertex in \(v \in U\)  hold \(y_{v} = 1\) . Every vertex \(v \in U\)  generates \(r = O(\log n)\)  iid exponential random variables \(W_{1}^{v}, \dots , W_{r}^{v}\)  with mean 1, and broadcasts each random variable to its neighbors in \(r\)  rounds of \(\mathsf {CONGEST}\) . Once a vertex \(v \in V\)  receives \(W_{j}^{u}\)  for all neighbors \(u \in N_{1}(v)\) , it sends \(\overline{W}_{j}^{v}\min _{u \in N_{1}(v)}{W_{j}^{u}}\)  to all its neighbors. Now once a vertex \(v \in V\) , receives \(\overline{W}_{j}^{u}\)  for all neighbors \(u \in N_{1}(v)\) , it calculates \(\tilde{W_{j}} = \min _{u \in N_{1}(v)}{\overline{W}_{j}^{u}} = \min _{u \in N_{2}(v)}{W_{j}^{u}}\) . The estimate that each \(v \in V\)  outputs is \(\tilde{d_{v}} = \frac{r}{\sum _{j=1}^{r}{\tilde{W_{j}}}}\)  where \(1/\tilde{d_{v}}\)  is distributed exponentially with mean \(\lambda = 1/d_{v}\) . Therefore, the statement of the lemma follows from lem:Mosk-Aoyama-Shah-Estimation.
For each vertex \(v \in V\)  that computes some estimate \(\tilde{d_{v}}\) , the value \(d_{v}\)  that \(v\)  is estimating lies in the set \(\lbrace 1, \dots , \Delta ^{2}\rbrace \) . We can assume that \(d_{v} \ge c \log n\)  for any arbitrarily large constant \(c\) , by having vertices with degree \(< c \log n\)  broadcast all their edges in \(O(\log n)\)  rounds. Therefore, \(O(\log n)\)  bits of precision suffice to get the correct estimate with high probability since rounding will only affect the final estimate by an additive \(r = \log n\)  factor.
Using lem:sampling-estimation with \(U\)  being the set of uncovered vertices, each vertex \(v\)  can calculate its rounded density \(\tilde{\rho _{v}}\)  of step 1 in \(O(\log n)\)  rounds. In step 2, each vertex just needs the maximum rounded density in its 4-hop neighborhood in \(G\)  in order to mark itself as a candidate. For steps 3 and 4, it suffices that each uncovered vertex \(u\)  know the ID of the vertex having minimum rank in their 2-hop neighborhood (where rank ties are broken by smallest ID) in order to know which candidate \(u\)  is voting for. For step 5, we wish to estimate the number of votes and \(|C_{v}|\)The algorithm in [1]} uses the exact value of \(|C_{v}|\) . But it suffices to use a good estimate, since it doesn't affect the approximation factor and only changes the running time by a constant. for each candidate \(v\) . Estimating \(|C_v|\)  can be done using lem:sampling-estimation the same way we estimated \(\rho _{v}\) . Estimating the number of votes is a bit different. Note that the candidates form a partition of the uncovered vertices, therefore we can apply lem:sampling-estimation for each candidate in parallel which allows the candidates to estimate the number of votes that they have received. Note that when performing this estimation, a vertex might receive vote estimates for many different candidates that it needs to forward and it will send the estimate only to the candidate it corresponds to instead of broadcasting it like in the proof of lem:sampling-estimation. This allows us to simulate step 5 in \(O(\log n)\)  rounds. For step 6, it suffices that each uncovered node \(u\)  know the smallest ID vertex in its 2-hop neighborhood that joins the dominating set.

Distributed \(G^2\) -Minimum Dominating Set (Lower Bounds)
In this section we show \(\tilde{\Omega }(n^2)\)  lower bounds in the \(\mathsf {CONGEST}\)   model for solving the (unweighted) \(G^2\) -MDS problem. In app:ExactMDSLB we show a lower bound for solving the problem exactly and in app:ApproximateMDSLB and app:ApproximateMDSLB-unweighted we show lower bounds for computing constant approximations.
Quadratic Lower bound for Exact \(G^2\) -MDS
In this section we will show an \(\tilde{\Omega }(n^2)\)  lower bound for solving the (unweighted) \(G^2\) -MDS problem exactly in \(\mathsf {CONGEST}\) , that is, we formally prove the following theorem.
Theorem 31 theorem]thm:exact-mds-lower-bound-main-theorem
Any \(\mathsf {CONGEST}\)  algorithm requires \(\tilde{\Omega }(n^{2})\)  rounds for solving (unweighted) \(G^2\) -MDS exactly.

We now give an outline for the proof of thm:exact-mds-lower-bound-main-theorem. The formal proof follows at the end of the section.
Proof Outline of thm:exact-mds-lower-bound-main-theorem: 
Bachrach et al. [26]} provided a family of lower bound graphs \(G_{x,y}\)  that shows that solving exact \(G\) -MDS needs near quadratic time in the \(\mathsf {CONGEST}\)  model. To prove thm:exact-mds-lower-bound-main-theorem we construct a graph family \(H_{x,y}\)  such that the size of the MDS in \(G_{x,y}\)  is closely related to the size of an exact MDS in \(H^2_{x,y}\)  (cf. lem:MDSsizesRelate). Then, one can solve \(G\) -MDS on \(G_{x,y}\)  via creating the graph \(H_{x,y}\)  and then solving MDS on \(H^2_{x,y}\) . Thus a lower bound for \(G\) -MDS translates into a lower bound for the \(G^2\) -MDS problem. The main difficulty is in having asymptotically the same number of vertices in \(H\)  graphs while keeping the graph \(H\)  simulatable in the communication network \(G\) . If \(H\)  has drastically more vertices that \(G\)  the lower bounds results for \(G^2\) -MDS would be very far from being quadratic.
We start with the lower bound graph family used by [26]} to show that
\(G\) -MDS requires \(\tilde{\Omega }(n^2)\)  rounds to be solved exactly.
<FIGURE>\(G\) -MDS lower bound graph family \(G_{x,y}\)  from [26]}: 
For any \(k\)  that is a power of 2 and for each pair of bit vectors \(x, y \in \lbrace 0, 1\rbrace ^{k^2}\) , there is a graph, denoted \(G_{x, y}\) , in this family.
See fig:Bachrach-MDS-lb-graph for an illustration of \(G_{x,y}\) .
This lower bound graph has four sets of row vertices \(A_{1}, B_{1}, A_{2}, B_{2}\)  each of which contain \(k\)  vertices.
Moreover there are two sets of bit gadgets, each set containing \(\log _{2} k\)  bit gadgets, one set for \(A_{1}, B_{1}\)  and the other set for \(A_{2}, B_{2}\) .
The \(i^{th}\)  bit gadget for \(A_{1}, B_{1}\)  is a 6-cycle with vertices \(f_{A_{1}}^{i}, t_{A_{1}}^{i}, u_{A_{1}}^{i}, f_{B_{1}}^{i}, t_{B_{1}}^{i}, u_{B_{1}}^{i}\) .
The vertices in \(a_{1}^{i} \in A_{1}\)  are connected to the bit gadget vertices \(f_{A_{1}}^j, t_{A_{1}}^j\)  depending on the binary representation of \(i-1\) .
Specifically, \(a_1^i\)  is connected to the complement of the binary representation of \(i-1\) .
For example, the vertex \(a_{1}^{1}\)  is connected to all the \(t_{A_{1}}\)  vertices. The connections for other row vertices are similar.
All of these edges are fixed, i.e., independent of \(x\)  and \(y\) . Additionally, \(x\)  determines edges between \(A_1\)  and \(A_2\) , whereas \(y\)  determines edges between
\(B_1\)  and \(B_2\) . Specifically, index the \(k^2\)  bits in \(x\)  as \(x_{i, j}\) , \(1 \le i, j \le k\) . Connect vertex \(i \in A_1\)  and vertex \(j \in A_2\)  iff \(x_{i,j} = 1\) .
The edges between \(B_1\)  and \(B_2\)  are similarly determined by the bit vector \(y\) .
One can check that \(G_{x, y}\)  has \(4k + 12\log _2 k\)  vertices, \(4k\cdot \log _2 k\)  fixed edges, and \(O(k^2)\)  variable edges (i.e., edges determined
by \(x\)  and \(y\) ).
[26]} now defines a vertex partition \((V_A, V_B)\)  of \(G_{x, y}\) , where \(V_A = A_1 \cup A_2 \cup \lbrace t_{A_1}^i, f_{A_1}^i, u_{A_1}^i \mid 1 \le i \le \log _2 k\rbrace  \cup \lbrace t_{A_2}^i, f_{A_2}^i, u_{A_2}^i \mid 1 \le i \le \log _2 k\rbrace \)  and \(V_B\)  is the set of remaining vertices.
Basically, the vertices in left half of fig:Bachrach-MDS-lb-graph are assigned to \(V_A\)  and those in the right half are assigned to \(V_B\) .
Now consider two players Alice and Bob and suppose \(V_A\)  (and incident edges) are provided to Alice and \(V_B\)  and incident edges are provided
to Bob. Bachrach et al. [26]} show that the construction of \(G_{x, y}\)  is such that \(G_{x, y}\)  has a dominating set of size at most \(4\log _2 k + 2\)  iff
\(DISJ_{k^{2}}(x,y) = \mathrm {false}\)  for the bit vectors \(x\)  and \(y\) . Since the two-party communication complexity of set disjointness for bit vectors of size \(k^2\)  is
\(\Omega (k^2)\) , Alice and Bob need to communicate \(\Omega (k^2)\)  bits to determine if \(G_{x, y}\)  has a dominating set of size at most \(4\log _2 k + 2\) .
The number of edges in the cut between Alice and Bob is \(O(\log k)\) , implying that if our goal was to determine if \(G_{x, y}\)  has a
dominating set of size at most \(4\log _2 k + 2\)  in the \(\mathsf {CONGEST}\)  model, then \(\Omega (k^2)\)  bits would have to flow over \(O(\log k)\)  edges,
leading to a \(\tilde{\Omega }(k^2)\)  lower bound on the number of rounds.
We introduce a dangling path gadget which we insert into edges in the graph \(G_{x,y}\)  to obtain a
graph \(H_{x,y}\) . The goal is to show that one can solve MDS on \(G_{x,y}\)  by solving \(G^2\) -MDS on \(H_{x,y}\) .
Note that the motivation for introducing a dangling path gadget into edge \(e\)  of \(G_{x, y}\)  is to ensure that
\(H^2_{x, y}\)  has all the edges of \(G_{x, y}\)  and we can compute a minimum dominating set of \(G_{x, y}\)  by computing
a minimum dominating set of \(H^{2}_{x, y}\)  and exchanging/removing vertices that
cover the gadgets.
Here is a more precise description of the dangling path gadget.
The dangling path gadget \(DP_{e}\) : We propose adding the following dangling path gadget \(DP_{e}\)  replacing each edge \(e = (u, v)\)  in \(G_{x,y}\) .
The gadget has 5 vertices which we denote by \(DP_e[1]\) , \(DP_e[2]\) , \(DP_e[3]\) , \(DP_e[4]\) , \(DP_e[5]\) .
Then edge \(e\)  is deleted, the vertex \(DP_e[1]\)  is connected to \(u\)  and \(v\) , and
there is a path connecting \(DP_e[1], DP_e[2], DP_e[3], DP_e[4], DP_e[5]\) .
See Figure  (left) for an illustration.
<FIGURE>There is one main challenge posed by this approach, which we now describe along with a description of how we get around it.
Challenge 1:
Introducing a dangling path gadget into each edge of the graph increases the number of vertices of the graph quite significantly.
If \(G_{x, y}\)  is a graph with \(n\)  vertices and \(m\)  edges, then \(H_{x, y}\)  has \(\Omega (m)\)  vertices which could be \(\Omega (n^2)\)  vertices in the worst case.
This “blow up” in the number of vertices means
the \(\tilde{\Omega }(n^2)\)  lower bound for \(G\) -MDS would only translate into a \(\tilde{\Omega }(n)\)  lower bound for \(G^2\) -MDS.
To deal with this challenge, we introduce the idea of sharing dangling path gadgets. Informally speaking, this simply means that instead of each edge having a separate dangling path gadget, a lot of the edges in \(G_{x, y}\)  will share dangling path gadgets. A precise version of the construction of a lower bound graph family, that uses this idea, is described below.
\(G^{2}\) -MDS lower bound graph family \(H_{x,y}\) : We first replace each edge having at least one bit gadget vertex as
an end point, by a 5-vertex dangling path gadget.
Note that there are \(O(k \log k)\)  edges incident on bit gadget vertices and therefore we have not introduced too many path gadget vertices.
The remaining edges are those between the row vertices \(A_{1}, B_{1}, A_{2}, B_{2}\) .
These can be \(O(k^2)\)  in number and so we have to be careful in introducing path gadget vertices.
For each row vertex \(a_{1}^{i} \in A_{1}\) , we add a shared path gadget \(A_{1}^{i}\) .
The gadget is similar to the dangling path gadget in that it has 5 vertices
\(A_{1}^{i}[1], A_{1}^{i}[2], A_{1}^{i}[3], A_{1}^{i}[4], A_{1}^{i}[5]\)  connected to form a path.
The vertex \(A_{1}^{i}[1]\)  is connected to \(a_{1}^{i}\) . We add similar shared path gadgets
\(A_{2}^{i}, B_{1}^{i}, B_{2}^{i}\)  for the \(i^{th}\)  row vertex in \(A_{2}, B_{1}\) , and \(B_{2}\)  respectively.
For each edge between \(a_{1}^{i}\)  and \(a_{2}^{j}\)  in \(G_{x,y}\) , we add a corresponding edge
between \(A_{1}^{i}[1]\)  and \(A_{2}^{j}[1]\)  in \(H_{x,y}\) . Similarly for each edge between \(b_{1}^{i}\)  and \(b_{2}^{j}\)  in \(G_{x,y}\) , we
add a corresponding edge between \(B_{1}^{i}[1]\)  and \(B_{2}^{j}[1]\)  in \(H_{x,y}\) . See fig:Exact-MDS-dangling-path-gadgets for an illustration.
Note that this sharing of path gadgets results in only \(O(k)\)  additional path gadget vertices.
We now show, in a sequence of three lemmas that any MDS on \(H^2_{x,y}\)  can be put into a normal form (Lemmas  and ). Afterwards we use this normal form to show how the size of an MDS of \(G_{x,y}\)  is related to the size of an MDS on \(H^2_{x,y}\)  (lem:MDSsizesRelate).
Lemma 32 lemma]lem:middle-dangling-gadget-in-mds
Any MDS of \(H^2_{x,y}\)  can be transformed into an equal size MDS such that

the vertex \(DP_{e}[3]\)  of each dangling path gadget \(DP_{e}\)  is in the MDS of \(H^2_{x,y}\) ,

\(S[3]\)  of the shared path gadgets \(S \in \lbrace A_{1}^{i}, A_{2}^{i}, B_{1}^{i}, B_{2}^{i}\rbrace _{i=1}^{k}\)  belongs to the MDS of \(H^{2}_{x,y}\) .


Consider a dangling path gedget or a shared path gadget \(P\)  in \(H^{2}_{x,y}\) . In order to cover \(P[5]\) , at least one of \(P[3], P[4], P[5]\)  has to be in the dominating set \(S_{H}\)  of \(H^{2}_{x,y}\) . If either of \(P[4]\)  or \(P[5]\)  (or both) is in the dominating set \(S_{H}\) , we can create a new dominating set \(S^{\prime }_{H}\)  by removing them and adding \(P[3]\)  (if it is not already present). The dominating set \(S^{\prime }_{H}\)  still covers all the vertices in \(H^2_{x,y}\)  and has size at most the size of \(S_{H}\) . Doing this exercise for all dangling path gadgets and shared path gadgets gives us the lemma.
Lemma 33 lemma]lem:no-other-dangling-gadget-in-mds
Any MDS of \(H^2_{x,y}\)  can be transformed into an equal size MDS such that

for any dangling path gadget \(DP_{e}\)  such that \(e\)  is incident on a bit gadget vertex in \(G_{x,y}\)  no gadget vertices other than \(DP_{e}[3]\)  belongs to the MDS

the vertices \(S[2], S[4], S[5]\)  of a shared path gadget \(S\)  do not belong to the MDS of \(H^{2}_{x,y}\)  for all \(S \in \lbrace A_{1}^{i}, A_{2}^{i}, B_{1}^{i}, B_{2}^{i}\rbrace _{i=1}^{k}\) .



Consider a dangling path gadget \(DP_{e}\)  for the edge \(e = \lbrace u, v\rbrace \)  in \(G_{x,y}\) .
For ease of exposition, we rename the vertices of \(DP_{e}\)  to be \(p, q, r, s, t\) , with \(p\)  connected to \(u\)  and \(v\)  in \(H_{x, y}\) .
By lem:middle-dangling-gadget-in-mds, \(r\)  belongs to the MDS and covers all vertices \(p, q, r, s, t\)  in the gadget.
Note that if \(s\)  and \(t\)  are in the MDS, they can just be removed, because they do not cover any more vertices than \(r\)  in \(H^2_{x,y}\) .
The vertex \(q\)  covers just the vertices \(u, v, p, q, r, s\)  in \(H^2_{x,y}\)  and thus the only vertices \(q\)  covers other than \(r\)  are \(u\)  and \(v\) .
Therefore, if \(q\)  is in a minimum dominating set \(S\) , we can exchange it for either \(u\)  or \(v\)  and we still have a dominating set of size at most \(|S|\) .
Similarly, the additional vertices that \(p\)  covers over \(r\) , are \(u, v\) , and all the \(P[1]\)  vertices of each dangling path gadget and shared path gadget \(P\) 
incident on \(u\) , and \(v\) . The all these vertices are covered due to lem:middle-dangling-gadget-in-mds. Therefore, if \(p\)  is in the minimum dominating set \(S\) , we can exchange it for either \(u\)  or \(v\)  and we still have a dominating set of size at most \(|S|\) .
Hence, we can assume no vertex in \(DP_{e}\)  other than \(r\)  belongs to the MDS. Repeating this argument for all dangling path vertices gives us the lemma.

Note that the last part of the above proof does not apply to the shared path gadgets, though the rest does.
For example, the \(A_{1}^{i}[1]\)  vertex might cover the vertex \(a_{2}^{j}\)  if \(\lbrace A_{1}^i[1], A_{2}^{j}[1]\rbrace \)  is an edge in \(H_{x, y}\) .
Therefore we get the following, slightly weaker, lemma for shared path gadgets.

We are now ready to prove the lemma that will allow us to show our lower bound.
Lemma 34 
The graph \(H_{x,y}^2\)  has a minimum dominating set of size \(W + 2k + 4k\log _2 k + 12\log _2 k\)  if and only if, the graph \(G_{x, y}\)  has a minimum dominating set of size \(W\) .

For the forward direction, let \(S_H\)  denote a minimum dominating set of \(H_{x, y}^2\) .
By lem:middle-dangling-gadget-in-mds, we
can assume that the vertex with index 3 from each dangling path gadget and each shared path gadget belongs to \(S_H\) .
There are \(2k + 4k\log _2 k + 12\log _2 k\)  such vertices in \(H_{x, y}\)  and they only cover the dangling path gadget and
shared path gadget vertices.
Let \(S_H^{\prime }\)  denote the remaining vertices of \(S_{H}\) , i.e., those that remain in \(S_H\)  after vertices with index 3 from
dangling path and shared path gadgets are removed.
Let \(W\)  denote the size of \(S_H^{\prime }\) .
We show that \(S_H^{\prime }\)  can be transformed into a minimum dominating set of \(G_{x,y}\)  of size \(W\) .
By lem:no-other-dangling-gadget-in-mds, we know that \(S_{H}\)  does not contain any dangling path gadget vertex
besides those with index 3. Therefore \(S_H^{\prime }\)  contains no dangling path vertex.
By lem:no-other-dangling-gadget-in-mds, (2), we know that \(S_{H}\)  does not contain the \(S[2], S[4], S[5]\)  vertices of any shared path gadget \(S\) .
Therefore, for any shared path gadget \(S\) , the only vertices from \(S\)  that \(S_H^{\prime }\)  may contain is \(S[1]\) .
Now these vertices in \(S_H^{\prime }\)  have to cover all the vertices in \(H^2_{x,y}\)  that are not dangling and shared path vertices;
these are exactly the vertices of \(G_{x,y}\) .
We now show that \(S_H\)  does not contain both \(a_1^i\)  and \(A_1^i[1]\)  for any \(i\) , \(1 \le i \le k\) .
The same argument can be applied to other sets of row vertices \(A_2\) , \(B_1\) , and \(B_2\) .
The vertex \(a_{1}^{i}\)  in \(H^{2}_{x,y}\)  covers some bit gadget vertices and the vertex \(A_{1}^{i}[1]\)  covers the
same row vertices in \(A_{2}\)  as the vertex \(a_{1}^{i}\)  does in \(G_{x,y}\) . Note that \(a_{1}^{i}\)  does not cover any row vertex in \(H^{2}_{x,y}\) .
We know from [26]} that the MDS of \(G_{x,y}\)  has the property that the bit gadget vertices provide
coverage for all bit gadget vertices. This is a local argument and it also holds for the MDS of \(H^{2}_{x,y}\) 
since the subgraph induced by the bit gadget vertices in \(H^{2}_{x,y}\)  is the same as the subgraph induced in \(G_{x,y}\) .
Therefore, \(a_{1}^{i}\)  and \(A_1^i[1]\)  cannot belong to \(S_{H}\)  because if they do, we can remove
\(a_1^i\)  and still have a dominating set of \(H_{x, y}\) , contradicting the fact that \(S_H\)  is a minimum dominating set of \(H^2_{x, y}\) .
Knowing that \(S_H^{\prime }\)  does not contain both \(a_1^i\)  and \(A_1^i[1]\)  (and similarly for vertices from other rows), we can
transform \(S_{H}^{\prime }\)  to the set \(S_{G}\)  by replacing any shared path vertex by the corresponding row vertex.
This gives a dominating set of \(G_{x, y}\)  of size \(|S_H^{\prime }|\) .
Note that \(S_G\)  must form a minimum dominating set of \(G_{x,y}\) .
Otherwise we can create a smaller dominating set of \(H_{x,y}^2\)  than \(S_H\) , by taking the vertices corresponding to the
MDS of \(G_{x,y}\)  and applying the reverse transformation that replaces all the row vertices by their corresponding shared path gadget vertex.
For the reverse direction, consider an MDS \(S_G\)  of \(G_{x,y}\)  of size \(W\) .
Let \(S_H\)  contain the \(P[3]\)  vertices from all the \(2k + 4k\log _2 k + 12\log _2 k\)  dangling path and shared path gadgets \(P\) .
We now add to \(S_{H}\) , the \(W\)  vertices in \(S_G\) , while replacing each the row vertex by its neighboring shared path gadget vertex.
It is easy to see that \(S_{H}\)  has size \(W + 2k + 4k\log _2 k + 12\log _2 k\)  and is
a dominating set of \(H_{x,y}^2\) . There cannot be a smaller dominating set of \(H_{x, y}^2\) , because otherwise we could extract
a dominating set of \(G_{x,y}\)  that is smaller than \(S_G\)  using the procedure described while proving the forward direction, contradicting the optimality of \(S_G\) .

Using that the size of a \(G^{2}\) -MDS of \(H_{x,y}\)  relates the size of an MDS of \(G_{x,y}\)  we can prove thm:exact-mds-lower-bound-main-theorem as follows.
[Proof of thm:exact-mds-lower-bound-main-theorem]
Bachrach et al. [26]} show that the MDS lower bound graph \(G_{x,y}\)  is a family of lower bound graphs for the \(\mathsf {CONGEST}\)  model wrt the set-disjointness function \(f=DISJ_{k^{2}}\)  and the predicate \(P_{G}\)  which asks whether the graph \(G\)  has a dominating set of size \(W = 4\log k + 2\) . The vertices of \(G_{x,y}\)  are partitioned into \(V_{A} = A_{1} \cup A_{2} \cup \lbrace f_{S}^{i}, t_{S}^{i}, u_{S}^{i} \mid 1 \le i \le \log _{2} k, S \in \lbrace A_{1}, A_{2}\rbrace \rbrace \)  and \(V_{B} = V(G_{x,y}) \setminus V_{A}\)  with cut size being \(|E(V_{A}, V_{B})| = O(\log k)\) .
By lem:MDSsizesRelate, we know that \(G_{x,y}\)  satisfies the predicate \(P_{G}\)  iff the graph \(H_{x,y}\)  satisfies the predicate \(P_{H}\)  which asks whether the input graph has a \(G^{2}\) -dominating set of size \(W + 2k + 4k\log _2 k + 12\log _2 k\)  where \(W = 4\log k + 2\) . Recall that the number of vertices in \(H_{x,y}\)  is \(O(k \log k)\) .
Define \(V_{A}^{\prime } = V_{A} \cup \lbrace DP_{e} \mid e = \lbrace u, v\rbrace  \text{ and } u, v \in V_{A}\rbrace  \cup \lbrace A_{1}^{i}, A_{2}^{i} \mid 1 \le i \le k\rbrace \)  and \(V_{B}^{\prime } = V(H_{x,y}) \setminus V_{A}^{\prime }\) . With these definitions of \(V_{A}^{\prime }\)  and \(V_{B}^{\prime }\) , the cut \(E(V_{A}^{\prime }, V_{B}^{\prime })\)  of \(H_{x,y}\)  has size at most \(O(\log k)\) .
The graph \(H_{x,y}\)  with partition \(V_{A}^{\prime }, V_{B}^{\prime }\)  is a family of lower bound graphs wrt the set-disjointness function \(f=DISJ_{k^{2}}\)  and the predicate \(P_{H}\) . Therefore, thm: general lb framework gives an \(\tilde{\Omega }(k^2)\)  lower bound for the exact unweighted \(G^{2}\) -MDS problem in the \(\mathsf {CONGEST}\)  model on a graph with \(O(k \log k)\)  vertices. Therefore for a graph with \(n\) -vertices we get an \(\tilde{\Omega }(n^{2})\)  lower bound which completes the proof of thm:exact-mds-lower-bound-main-theorem.

Quadratic Lower bound for \(O(1)\) -approximate \(G^2\) -WMDS
In this section, we will prove the following theorem.
Theorem 35 theorem]thm:approx-MWDS-lower-bound-main-theorem
Any distributed algorithm in the \(\mathsf {CONGEST}\)  model which, given an input graph \(G\) , produces a \(c\) -approximate solution to the minimum weighted dominating set problem on \(G^{2}\)  for \(c < 7/6\)  requires \(\tilde{\Omega }(n^{2})\)  rounds.

Obtaining quadratic lower bounds for approximation algorithms seems much more challenging than obtaining quadratic lower
bounds for algorithms that solve problems exactly.
This is illustrated in [26]}, which contains quadratic lower bounds for exact versions of a number
of problems (e.g., MDS, Hamiltonian path, Steiner tree, and max-cut) and a quadratic lower bound for a \(O(1)\) -approximation algorithm for just
one problem: maximum independent set (MaxIS).
The authors use an interesting gadget, called a code gadget, that helps in creating the “gap” needed
for the MaxIS problem.
But, the success of this gadget seems to depend a lot on the structure of the MaxIS problem.
In particular, this gadget does not seem to work for MDS and [26]} does not show
any lower bounds for approximating MDS on \(G\) .
However, [26]} does show weaker lower bounds (i.e., linear or worse)
for \(G^2\) -MWDS, though for larger approximation factors.
Specifically, they show two results for \(G^2\) -MWDS in \(\mathsf {CONGEST}\) : (i) an \(\Omega (n^{1-\varepsilon }/\log n)\) -round lower bound for \(O(\varepsilon \log n)\) -approximation and (ii) an \(\tilde{\Omega }(n)\) -round lower bound for \(O(\log \log n)\) -approximation.
Our results overcome the weaknesses of the results of [26]}: Our bounds are indeed quadratic lower bounds for approximation of \(G^2\) -MDS, and our results remove the necessity of weights.
We now provide a proof of Theorem , while
providing intuition for the main challenges our proof overcomes in addition to the challenge addressed in app:ExactMDSLB.
Challenge 2:
The size of the MDS in \(H^2_{x,y}\)  is too large for any small-cut bit gadget to yield a constant fraction gap.
At this stage, there are still \(\Omega (k \log k)\)  distinct dangling and shared path gadgets and this leads to
a minimum dominating set of size \(\Omega (k \log k)\)  because every path gadget needs at least 1 distinct vertex
in the dominating set.
To get a lower bound for \(O(1)\) -approximation, one would need to create a “gap” of size \(\Omega (k \log k)\) 
and this is not possible, given the \(O(\log k)\)  size of the cut.
To overcome this challenge, we propose an “extreme” version of sharing path gadgets, which we now describe.
To overcome this challenge, we need to reduce the size of the MDS significantly.
For this purpose, we propose a merged version of the dangling and shared path gadgets which will
use fewer vertices to cover all the gadget vertices. Let \(C\)  be an arbitrary set of dangling and shared path
gadgets \(P_{e}\)  that were added during the construction of \(H_{x, y}\) . In order to merge these gadgets, we remove all the
\(P_{e}[3], P_{e}[4], P_{e}[5]\)  vertices and connect all the \(P_{e}[2]\)  vertices to a common 3
vertex path \(P_{C}[3], P_{C}[4], P_{C}[5]\) . These three common vertices play the same role as the
original \(P_{e}[3], P_{e}[4], P_{e}[5]\)  vertices for each of the constituent gadgets we merged.
We denote this merged path gadget as \(P_{C}\) . Therefore we get the following lemma.
The proof is similar to those of lem:middle-dangling-gadget-in-mds so we skip it.
Lemma 36 lemma]lem:merged-gadget-vertex-in-mds
Let \(\mathcal {C}\)  be an arbitrary partition of the dangling and shared path gadgets in \(H_{x, y}\) . We modify \(H_{x, y}\)  by merging the dangling and shared path gadgets for each \(C \in \mathcal {C}\) . Any MDS of \(H^2_{x,y}\)  can be transformed into an equal size MDS of \(H^2_{x,y}\)  which contains the \(P_{C}[3]\)  vertex of each merged path gadget \(P_{C}\) .

This “extreme” merging of path gadgets allows us to reduce the size of a MDS substantiallyWe note that this “extreme” merging fails for \(G^{2}\) -MVC; these different path gadgets,
even after being merged, require a large vertex cover. This may indicate why we do not have
an \(\tilde{\Omega }(n^2)\)  lower bound for approximating \(G^{2}\) -MVC and also indicates something fundamentally different about
the two problems., to \(O(\log k)\) 
But, it is still not clear how to create a large enough “gap” i.e., how to ensure that the
size of MDS changes by \(\Theta (\log k)\)  as a result of small changes in the edges of
\(H_{x, y}\)  caused by changes to the bit vectors \(x\) , \(y\) .
Our goal now is to modify the construction of the lower bound graph so as to
reduce the size of the MDS even further. But, for that we have the overcome the following challenge.
Challenge 3:
The bit gadgets themselves contribute \(\Omega (\log k)\)  vertices to any minimum dominating set.
In order to address this challenge, we replace the bit gadgets from the exact MDS construction with a set gadget \(G_{MDS}\)  inspired by the lower bound graph for 2-MDS from [26]}. See fig:MDS-weighted-bit-gadget for an illustration.
Set Gadgets:
Consider a set system in a universe \(\mathcal {U} = \lbrace 1, 2, \dots , \ell \rbrace \)  of \(\ell \)  elements. In \(G_{MDS}\)  there are \(T\)  vertices corresponding to sets \(S_{1}, S_{2}, \dots , S_{T} \subset \mathcal {U}\)  and another \(T\)  vertices corresponding to their complements \(\overline{S_{1}}, \overline{S_{2}}, \dots , \overline{S_{T}}\) . A vertex has the same name as the set it represents. There are \(2\ell \)  vertices \(\lbrace \alpha _{i}, \beta _{i}\rbrace _{i=1}^{\ell }\)  where each \(\alpha _{i}, \beta _{i}\)  corresponds to the element \(i\)  in the universe \(\mathcal {U}\) . There are edges between \(\alpha _{i}\)  and \(\beta _{i}\)  for each \(i \in \mathcal {U}\) . And there are membership edges between \(S_{j}\)  and \(\alpha _{i}\)  if \(i \in S_{j}\)  and between \(\overline{S_{j}}\)  and \(\beta _{i}\)  if \(i \notin S_{j}\) . We require a collection of sets \(S_{1}, \dots , S_{T}\)  that satisfy the following property which is used to prove hardness of approximation for set cover in different models [48]}, [49]}.
Definition 37 (\(r\) -covering property)  Consider a collection of \(r\)  sets \(\mathcal {R}\)  from \(\lbrace S_{i}, \overline{S_{i}}\rbrace _{i=1}^{T}\) , such that for each index \(i\)  the set \(S_{i}\)  and its complement \(\overline{S_{i}}\)  are not both included together in \(\mathcal {R}\) . The sets \(S_{1}, \dots , S_{T}\)  are said to satisfy the \(r\) -covering property if for any such \(\mathcal {R}\) , there is at least one element in the universe \(\mathcal {U}\)  that is not covered by \(\mathcal {R}\)  (i.e. the element does not belong to any set in \(\mathcal {R}\) ).

Lemma 38 ([49]}) 
For any \(r \le \log \ell - O(\log \log \ell )\)  there exists sets \(S_{1}, \dots , S_{T}\)  satisfying the \(r\) -covering property with \(T = e^{\ell /r 2^{r}}\) .

Therefore, if we consider \(r\)  to be some large constant, we have \(\ell = O(\log T)\) . We set the weight of all the \(\alpha _{i}\) 's and \(\beta _{i}\) 's in \(G_{MDS}\)  to be \(r\) , and all other vertices have weight 1. Finally we add two vertices \(\alpha \)  and \(\beta \)  both having weight \(r\) . The vertex \(\alpha \)  is connected to all \(S_{i}\) 's and \(\beta \)  to all \(\overline{S_{i}}\) 's. This also means that all the \(S_{i}\) 's are two hops away from each other and all the \(\overline{S_{i}}\) 's are two hops away from each other.
<FIGURE>We get the following separation property.
Lemma 39 lemma]lem:bit-gadget-domination-gap
The graph \(G^2_{MDS}\)  has an MDS of weight 2. Moreover, any dominating set of \(G_{MDS}\)  that does not pick both \(S_{j}, \overline{S_{j}}\)  for some \(j \in \lbrace 1, \dots , T\rbrace \)  will have size at least \(r\) .

For any index \(i \in \lbrace 1, \dots , T\rbrace \) , the vertices \(S_{i}\)  and \(\overline{S_{i}}\)  form a dominating set of weight 2. Note that all the \(\alpha _{i}\) 's and \(\beta _{i}\) 's are covered because either \(S_{i}\)  or \(\overline{S_{i}}\)  is at most two hops away from them due to the set membership edges.
We can assume that vertices having weight \(r\)  cannot be included in the dominating because otherwise the lemma is vacuously true. Therefore, our only option is to include the \(S_{i}\) 's, and the \(\overline{S_{i}}\) 's in the dominating set.
The \(r\) -covering property ensures that if we do not pick both \(S_{j}, \overline{S_{j}}\)  for some \(j \in \lbrace 1, \dots , T\rbrace \) , then we will have to pick at least \(r\)  set vertices to cover all the \(\alpha _{i}\) 's and the \(\beta _{i}\) 's. The lemma follows.
We are now ready to describe our lower bound graph construction in detail.
We show how to replace bit gadgets in the construction of \(H_{x, y}\)  described earlier by
set gadgets \(G_{MDS}\) .
This modification leads to an MDS of constant weight in \(H^2_{x, y}\)  and more importantly
an MDS of weight 6 if \(x\)  and \(y\)  are not disjoint and a weight of 7 otherwise.
<FIGURE>Fixed Graph Construction: Our lower bound graph \(H_{x,y}\)  consists of four sets of row vertices \(A, A^{\prime }, B, B^{\prime }\)  each of which has \(T\)  vertices. There are two copies of the set gadget described above: one connected to \(A, B\) , denoted by \(G_{MDS}\) , and the other connected to \(A^{\prime }, B^{\prime }\) , denoted by \(G^{\prime }_{MDS}\) . For each vertex \(v \in G_{MDS}\) , the corresponding vertex in \(G^{\prime }_{MDS}\)  is named \(v^{\prime }\) .
Each vertex \(a_{i} \in A\) , has two shared path gadgets \(A^{a}_{i}\)  and \(A^{S}_{i}\) , both of which are connected to \(a_{i}\) . And similarly, each vertex \(a^{\prime }_{i} \in A^{\prime }\)  has two shared path gadgets \(A^{a^{\prime }}_{i}\)  and \(A^{S^{\prime }}_{i}\)  which are connected to \(a^{\prime }_{i}\) .
We merge the shared path gadgets \(A^{S}_{i}\) , \(A^{a}_{i}\) , \(A^{S^{\prime }}_{i}\) , and \(A^{a^{\prime }}_{i}\)  for all \(1 \le i \le T\)  to form the merged path gadget \(A_{*}\)  having common vertices \(A_{*}[3], A_{*}[4], A_{*}[5]\) . The vertex \(A_{*}[3]\)  has weight 0. The sharing reduces the total number of vertices in the graph, and the merging reduces the weight of the minimum dominating set. Note that \(H_{x,y}\)  does not have any dangling path gadgets.
Each \(a^{S}_{i}\)  is connected to \(S_{j} \in G_{MDS}\)  if \(i \ne j\) , and similarly each \(a^{S^{\prime }}_{i}\)  is connected to \(S^{\prime }_{j} \in G^{\prime }_{MDS}\)  if \(i \ne j\) . All vertices on Alice's side except \(\lbrace \alpha _{i}, \alpha ^{\prime }_{i}\rbrace _{i=1}^{\ell }\) , \(\alpha \) , \(\alpha ^{\prime }\) , and \(A_{*}[3]\)  have weight 1.
The construction of Bob's side is symmetric, so we do not describe it in this proof.
Alice hosts the vertices in \(A, A^{\prime }\) , the vertices in the merged gadget \(A_{*}\) , and the “left side” of the set gadgets \(G_{MDS}\)  and \(G^{\prime }_{MDS}\) . More formally, the set gadget vertices Alice hosts are \(\alpha \) , \(\alpha ^{\prime }\) , \(\lbrace S_{i}, S^{\prime }_{i}\rbrace _{i=1}^{T}\) , and \(\lbrace \alpha _{i}, \alpha ^{\prime }_{i}\rbrace _{i=1}^{\ell }\) . Bob hosts the rest of the vertices.
Constructing \(H_{x,y}\)  given inputs \(x, y \in \lbrace 0, 1\rbrace ^{T^{2}}\) : We index the strings \(x, y\)  by \((i, j) \in T \times T\) . We add an edge between \(A^{a}_{i}[1]\)  and \(A^{a^{\prime }}_{j}[1]\)  iff \(x_{ij} = 1\)  and similarly we add an edge between \(B^{b}_{i}[1]\)  and \(B^{b^{\prime }}_{j}[1]\)  iff \(y_{ij} = 1\) .
If \(x_{ij} = 1\)  then the vertices \(A^{a^{\prime }}_{j}[1], A^{a}_{i}[1]\)  have edges to \(a_{i}\)  and \(a^{\prime }_{j}\)  in \(H^{2}_{x,y}\)  and if \(x_{ij} = 0\)  then no vertex in \(H^{2}_{x,y}\)  has an edge to both \(a_{i}\)  and \(a^{\prime }_{j}\) . Similarly, if \(y_{ij} = 1\)  then the vertices \(B^{b^{\prime }}_{j}[1], B^{b}_{i}[1]\)  have edges to \(b_{i}\)  and \(b^{\prime }_{j}\)  in \(H^{2}_{x,y}\)  and if \(y_{ij} = 0\)  then no vertex in \(H^{2}_{x,y}\)  has an edge to both \(b_{i}\)  and \(b^{\prime }_{j}\)
Lemma 40 lemma]lem:weighted-mds-disjointness-reduction
If \(DISJ_{T^{2}}(x,y) = \mathrm {false}\)  then \(H^{2}_{x,y}\)  has an MDS of weight 6, otherwise any dominating set of \(H^{2}_{x,y}\)  has weight at least 7.

Note that we can assume that \(A_{*}[3]\)  and \(B_{*}[3]\)  are in the dominating set because their weight is zero (and also due to lem:merged-gadget-vertex-in-mds). The vertex \(A_{*}[3]\)  covers all the vertices \(\lbrace A_{*}[4]\) , \(A_{*}[5]\) , \(A^{a}_{i}[1,2]\) , \(A^{S}_{i}[1,2]\) , \(A^{S^{\prime }}_{i}[1,2]\) , \(A^{a^{\prime }}_{i}[1,2]\rbrace _{i=1}^{T}\)  and the vertex \(B_{*}[3]\)  covers all the vertices \(\lbrace B_{*}[4]\) , \(B_{*}[5]\) , \(B^{b}_{i}[1,2]\) , \(B^{\overline{S}}_{i}[1,2]\) , \(B^{\overline{S^{\prime }}}_{i}[1,2]\) , \(B^{b^{\prime }}_{i}[1,2]\rbrace _{i=1}^{T}\)  without increasing the weight of the dominating set.
If \(DISJ_{T^{2}}(x,y) = \mathrm {false}\)  then there is an index \((i,j)\)  such that \(x_{ij} = y_{ij} = 1\) . Therefore, we add \(A^{a}_{i}[1], S_{i}, B^{b}_{i}[1], \overline{S_{i}}, S^{\prime }_{j}, \overline{S^{\prime }_{j}}\)  to the MDS incurring a total cost of 6. The vertices \(S_{i}\)  and \(\overline{S_{i}}\)  together cover all the vertices in the set gadget \(G_{MDS}\)  along with all row vertices in \(A,B\)  except \(a_{i}\)  and \(b_{i}\) , whereas the vertices \(S^{\prime }_{j}\)  and \(\overline{S^{\prime }_{j}}\)  cover all vertices in the set gadget \(G^{\prime }_{MDS}\) , along with all row vertices in \(A^{\prime },B^{\prime }\)  except \(a^{\prime }_{j}\)  and \(b^{\prime }_{j}\) . Since \(x_{ij} = y_{ij} = 1\) , the vertex \(A^{a}_{i}[1]\)  covers both \(a_{i}\)  and \(a^{\prime }_{j}\) , and the vertex \(B^{b}_{i}[1]\)  covers both \(b_{i}\)  and \(b^{\prime }_{j}\) . This means all the vertices in \(H^{2}_{x,y}\)  are dominated by a set of weight 6 and hence the MDS of \(H^{2}_{x,y}\)  has weight at most 6 when \(DISJ_{T^{2}}(x,y) = \mathrm {false}\) .
Now we look at the case when \(DISJ_{T^{2}}(x,y) = \mathrm {true}\) . In this case, we assume we cannot pick vertex of weight \(r\)  in the dominating set because if we do, we immediately get a dominating set of weight at least \(r\) . And then the lemma follows because \(r\)  was set to some arbitrarily large constant.
In order to cover all the set gadget vertices in \(G_{MDS}\)  and \(G^{\prime }_{MDS}\) , we need to pick \(S_{i}, \overline{S_{i}}, S^{\prime }_{j}, \overline{S^{\prime }_{j}}\)  for some \(i, j \in \lbrace 1, \dots , T\rbrace \) . Otherwise we incur a cost of at least \(r\)  by lem:bit-gadget-domination-gap for covering vertices in the two set gadgets.
Now, the only vertices that are left uncovered are \(a_{i}, a^{\prime }_{j}, b_{i}\) , and \(b^{\prime }_{j}\) . Note that since \(DISJ_{T^{2}}(x,y) = \mathrm {true}\) , there is no \((i,j)\)  such that both \(x_{ij}\)  and \(y_{ij}\)  are 1. Without loss of generality assume \(x_{ij}=0\) , therefore there is no vertex in \(H^{2}_{x,y}\)  that has an edge to both \(a_{i}\)  and \(a^{\prime }_{j}\) . Therefore, we need to pick at least 2 vertices in \(H^{2}_{x,y}\)  to cover \(a_{i}\)  and \(a^{\prime }_{j}\) . And neither of these two vertices will have an edge to \(b_{i}\)  and \(b^{\prime }_{j}\)  so we need to pick at least 3 vertices to cover all the four vertices. The only vertices with weight less than 1 are \(A_{*}[3]\)  and \(B_{*}[3]\)  which don't cover any of these four vertices. Therefore, every dominating set has to have weight at least 7.
[Proof of thm:approx-MWDS-lower-bound-main-theorem]
Let \(V_{A} = A \cup A^{\prime } \cup S \cup S^{\prime } \cup \lbrace \alpha _{i} \mid 1 \le i \le \ell \rbrace  \cup A_{*}\)  and \(V_{B} = V \setminus V_{A}\) . With these definitions of \(V_{A}\)  and \(V_{B}\) , the size of the cut \((V_{A},V_{B})\)  is at most \(O(\ell ) = O(\log T)\) . Let \(P\)  be the predicate that a graph has a minimum dominating set of weight at least 7. lem:weighted-mds-disjointness-reduction implies that \(H^{2}_{x,y}\)  is a family of lower bound graphs with respect to the function \(DISJ\)  and the predicate \(P\) .
Therefore, thm: general lb framework gives an \(\tilde{\Omega }(T^2)\)  lower bound for the problem of distinguishing between the case when a graph with \(O(T)\)  vertices has a dominating set of weight at least 7 and the case when it has a dominating set of weight at most 6. This gives a lower bound for approximation factor \(c < 7/6\)  which completes the proof of thm:approx-MWDS-lower-bound-main-theorem.

Quadratic Lower bound for \(O(1)\) -approximate \(G^2\) -MDS
The previous lower bound used weights in order to simplify the construction and proofs. In this section, we provide some modifications to get the same lower bound for unweighted MDS. In particular, we will prove the following theorem.
Theorem 41 theorem]thm:approx-MDS-lower-bound-main-theorem
Any distributed algorithm in the \(\mathsf {CONGEST}\)  model which, given an input graph \(G\) , produces a \(c\) -approximate solution to the minimum unweighted dominating set problem on \(G^{2}\)  for \(c < 9/8\)  requires \(\tilde{\Omega }(n^{2})\)  rounds.

The only modification we need is to the set gadgets \(G_{MDS}\)  and \(G^{\prime }_{MDS}\) . In order to do this, we remove the vertices \(\alpha , \beta , \alpha ^{\prime }, \beta ^{\prime }\) . We connect each \(S_{i}\)  to a new vertex \(q_{i}\) , each \(S^{\prime }_{i}\)  to a new vertex \(q^{\prime }_{i}\) , each \(\overline{S_{i}}\)  to a new vertex \(\overline{q_{i}}\) , and each \(\overline{S^{\prime }_{i}}\)  to a new vertex \(\overline{q^{\prime }_{i}}\) . The vertices \(q_{i}, q^{\prime }_{i}\)  are connected to \(A_{*}[3]\) , and the vertices \(\overline{q_{i}}, \overline{q^{\prime }_{i}}\)  are connected to \(B_{*}[3]\)  for each \(1 \le i \le T\) . Since the merged path gadgets in \(H^{2}_{x,y}\)  come from only shared path gadgets, we can show the following variant of lem:no-other-dangling-gadget-in-mds. Since the proof is similar, we skip it.
Lemma 42 lemma]lem:no-other-merged-shared-gadget-in-mds
We can assume w.l.o.g. that the vertices \(A_{*}[4], A_{*}[5]\)  of the merged path gadget \(A_{*}\) , and the vertices \(S[2]\)  where \(S \in \lbrace A^{S}_{i}, A^{a}_{i}, A^{S^{\prime }}_{i}, A^{a^{\prime }}_{i}\rbrace _{i=1}^{T}\)  do not belong to the MDS of \(H^{2}_{x,y}\) . A similar statement holds for the merged path gadget \(B_{*}\)

Therefore, we can show the following lemma which implies thm:approx-MDS-lower-bound-main-theorem.
Lemma 43 lemma]lem:mds-disjointness-reduction
If \(DISJ_{T^{2}}(x,y) = \mathrm {false}\)  then \(H^{2}_{x,y}\)  has an MDS of weight at most 8 and otherwise any dominating set of \(H^{2}_{x,y}\)  has weight at least 9.

Note that we can assume that \(A_{*}[3]\)  and \(B_{*}[3]\)  are in the dominating set due to lem:merged-gadget-vertex-in-mds. The vertex \(A_{*}[3]\)  covers all the vertices \(\lbrace A_{*}[4]\) , \(A_{*}[5]\) , \(A^{a}_{i}[1,2]\) , \(A^{S}_{i}[1,2]\) , \(A^{S^{\prime }}_{i}[1,2]\) , \(A^{a^{\prime }}_{i}[1,2]\) , \(S_{i}\) , \(S^{\prime }_{i}\) , \(q_{i}\) , \(q^{\prime }_{i}\rbrace _{i=1}^{T}\)  and the vertex \(B_{*}[3]\)  covers all the vertices \(\lbrace B_{*}[4]\) , \(B_{*}[5]\) , \(B^{b}_{i}[1,2]\) , \(B^{\overline{S}}_{i}[1,2]\) , \(B^{\overline{S^{\prime }}}_{i}[1,2]\) , \(B^{b^{\prime }}_{i}[1,2]\) , \(\overline{S_{i}}\) , \(\overline{S^{\prime }_{i}}\) , \(\overline{q_{i}}\) , \(\overline{q^{\prime }_{i}}\rbrace _{i=1}^{T}\) .
If \(DISJ_{T^{2}}(x,y) = \mathrm {false}\)  then there is an index \((i,j)\)  such that \(x_{ij} = y_{ij} = 1\) . Therefore, we add \(A^{a}_{i}[1], S_{i}, B^{b}_{i}[1], \overline{S_{i}}, S^{\prime }_{j}, \overline{S^{\prime }_{j}}\)  to the MDS incurring a total cost of 8. The vertices \(S_{i}\)  and \(\overline{S_{i}}\)  together cover all the uncovered vertices in the set gadget \(G_{MDS}\)  along with all row vertices in \(A,B\)  except \(a_{i}\)  and \(b_{i}\) , whereas the vertices \(S^{\prime }_{j}\)  and \(\overline{S^{\prime }_{j}}\)  cover all the uncovered vertices in the set gadget \(G^{\prime }_{MDS}\) , along with all row vertices in \(A^{\prime },B^{\prime }\)  except \(a^{\prime }_{j}\)  and \(b^{\prime }_{j}\) . Since \(x_{ij} = y_{ij} = 1\) , the vertex \(A^{a}_{i}[1]\)  covers both \(a_{i}\)  and \(a^{\prime }_{j}\) , and the vertex \(B^{b}_{i}[1]\)  covers both \(b_{i}\)  and \(b^{\prime }_{j}\) . This means all the vertices in \(H^{2}_{x,y}\)  are dominated by a set of weight 6 and hence the MDS of \(H^{2}_{x,y}\)  has weight at most 8 when \(DISJ_{T^{2}}(x,y) = \mathrm {false}\) .
Now we look at the case when \(DISJ_{T^{2}}(x,y) = \mathrm {true}\) . Consider the uncovered set gadget vertices in \(G_{MDS}\)  which are \(U = {\lbrace \alpha _{i}, \beta _{i}\rbrace }_{i=1}^{\ell }\)  and \(G^{\prime }_{MDS}\)  which are \(U^{\prime } = {\lbrace \alpha ^{\prime }_{i}, \beta ^{\prime }_{i}\rbrace }_{i=1}^{\ell }\) . Notice that by lem:no-other-merged-shared-gadget-in-mds, we can assume that \(U\)  can only be covered by vertices in \(G_{MDS}\) , and \(U^{\prime }\)  can only be covered by vertices in \(G^{\prime }_{MDS}\) .
The sets \(U, U^{\prime }\)  can be covered using 4 vertices: \(S_{i}, \overline{S_{i}}, S^{\prime }_{j}, \overline{S^{\prime }_{j}}\)  for some \(i, j \in \lbrace 1, \dots , T\rbrace \) . We cannot cover all the vertices of \(G_{MDS}\)  and \(G^{\prime }_{MDS}\)  using fewer than 4 vertices, as it would require using at most one vertex to cover all vertices in either \(G_{MDS}\)  or \(G^{\prime }_{MDS}\) . This is not possible since no single vertex covers all vertices \({\lbrace \alpha _{i}, \beta _{i}\rbrace }_{i=1}^{\ell }\)  in \(G_{MDS}\) , and \({\lbrace \alpha ^{\prime }_{i}, \beta ^{\prime }_{i}\rbrace }_{i=1}^{\ell }\)  in \(G^{\prime }_{MDS}\)  by the construction and the \(r\) -covering property.
Note that there are other ways of covering \(G_{MDS}\) , and \(G^{\prime }_{MDS}\)  using exactly 2 vertices each. If we pick \(q_{i}\)  (or \(\overline{q_{i}}\) ), it is better to pick \(S_{i}\)  (or \(\overline{S_{i}}\) ) since it covers more vertices of \(U\) . The \(r\) -covering property guarantees that no single set covers all the \(\ell \)  elements. But we can also cover \(U\)  by picking a vertex \(S \in \lbrace S_{i}, \overline{S_{i}}_{i=1}^{T}\rbrace \)  which covers all but one element \(j \in \lbrace 1, \dots , \ell \rbrace \)  along with either \(\alpha _{j}\)  or \(\beta _{j}\) . But this is equivalent to picking \(S\)  and \(\overline{S}\)  because \(\overline{S}\)  will cover both \(\alpha _{j}\)  and \(\beta _{j}\) , along with many other row vertices.
Therefore, we can assume w.l.o.g. that the 4 vertices used to cover the set gadgets are \(S_{i}, \overline{S_{i}}, S^{\prime }_{j}, \overline{S^{\prime }_{j}}\)  for some \(i, j \in \lbrace 1, \dots , T\rbrace \) .
Now, the only vertices that are left uncovered are \(a_{i}, a^{\prime }_{j}, b_{i}\) , and \(b^{\prime }_{j}\) . Note that since \(DISJ_{T^{2}}(x,y) = \mathrm {true}\) , there is no \((i,j)\)  such that both \(x_{ij}\)  and \(y_{ij}\)  are 1. Without loss of generality, assume \(x_{ij}=0\) , therefore there is no vertex in \(H^{2}_{x,y}\)  that has an edge to both \(a_{i}\)  and \(a^{\prime }_{j}\) . Therefore, we need to pick at least 2 vertices in \(H^{2}_{x,y}\)  to cover \(a_{i}\)  and \(a^{\prime }_{j}\) . Neither of these two vertices will have an edge to \(b_{i}\)  and \(b^{\prime }_{j}\)  so we need to pick at least 3 vertices to cover all the four vertices. Therefore, every dominating set has to have size at least 9.
[Proof of thm:approx-MDS-lower-bound-main-theorem]
Let \(V_{A} = A \cup A^{\prime } \cup S \cup S^{\prime } \cup \lbrace \alpha _{i} \mid 1 \le i \le \ell \rbrace  \cup A_{*}\)  and \(V_{B} = V \setminus V_{A}\) . With these definitions of \(V_{A}\)  and \(V_{B}\) , the size of the cut \(E(V_{A},V_{B})\)  is at most \(O(\ell ) = O(\log T)\) . Let \(P\)  be the predicate that a graph has a minimum dominating set of size at least 9. lem:mds-disjointness-reduction implies that \(H^{2}_{x,y}\)  is a family of lower bound graphs with respect to the function \(DISJ\)  and the predicate \(P\) .
Therefore, thm: general lb framework gives an \(\tilde{\Omega }(T^2)\)  lower bound for the problem of distinguishing between the case when a graph with \(O(T)\)  vertices has a dominating set of size at least 9 and the case when it has a dominating set of size at most 8. This gives a lower bound for approximation factor \(c < 9/8\)  which completes the proof of thm:approx-MDS-lower-bound-main-theorem.

Centralized Hardness Results for \(G^2\) -MVC and \(G^2\) -MDS
In the following theorem we show that using a dangling-path gadget as in Theorem  gives that MVC is NP-complete on \(G^2\) , and a simplified version of the proof of Theorem REF  gives that there is no FPTAS for MVC on \(G^2\)  unless \(P=NP\) .
Theorem 44 [No FPTAS for \(G^2\) -MVC]
Given input graph \(G\) , solving \(G^2\) -MVC exactly is NP-complete.
Moreover, there is no FPTAS for \(G^2\) -MVC unless \(P = NP\) , i.e., there is no family of algorithms \(\lbrace A_\varepsilon \mid \varepsilon >0\rbrace \)  such that algorithm \(A_\varepsilon \)  runs in time \(\operatorname{\text{{\rm poly}}}(n, \frac{1}{\varepsilon })\)  and yields a \((1 + \varepsilon )\) -approximation for MVC on \(G^2\) , unless \(P = NP\) .

For the first part of the theorem, we use a reduction from MVC on \(G\) . Given a graph \(G=(V_G,E_G)\) , we construct a graph \(H=(V_H,E_H)\)  by replacing each edge \(e \in E_G\)  with a dangling path gadget \(DP_e\)  which is a path on three vertices \(p_{e}^{1}, p_{e}^{2}, p_{e}^{3}\)  where \(p_{e}^{1}\)  is connected to both the end points of \(e\)  (as is defined in the proof of theorem:HtoG). Note that \(V_{H}\)  contains the vertices in \(V_{G}\)  plus the vertices in the dangling path gadget \(DP_{e}\)  for each \(e \in E_{G}\) . Therefore, the size of \(H\)  is polynomial in the size of \(G\) . Now we show that \(G\)  has a vertex cover of size \(c\)  iff \(H^{2}\)  has a vertex cover of size \(c + 2|E_{G}|\) .
For the forward direction, consider a vertex cover \(S_{G}\)  of \(G\)  having size \(c\) . We construct a vertex cover \(S_{H}\)  of \(H^{2}\)  by taking all the vertices in \(S_{G}\)  and adding the two vertices \(p_{e}^{1}, p_{e}^{2}\)  in the dangling path gadget \(DP_{e}\)  for all \(e \in E_{G}\) . The two vertices \(p_{e}^{1}, p_{e}^{2}\)  cover all the edges in \(H^{2}\)  incident on \(DP_{e}\) , and \(S_{G}\)  covers all the \(H^{2}\)  edges that are incident between two vertices in \(V_{G}\) . Therefore, \(S_{H}\)  is a valid vertex cover of \(H^{2}\)  with \(c+2|E_{G}|\)  vertices.
For the reverse direction, consider a vertex cover \(S_{H}\)  of \(H^{2}\)  having size \(c^{\prime }\) . lem:dangling-rearrangement implies that an exact MVC \(S_H\)  for \(H^2\)  takes all vertices of \(DP_e\)  except \(p_{e}^{3}\)  for every dangling path gadget \(DP_{e}\)  and that the set of nodes in \(S_H \cap V_{G}\)  is a vertex cover for \(G\) . This in particular implies \(c^{\prime } \ge 2|E_{G}|\) . Let \(c\)  be the number of vertices in \(S_{H} \cap V_{G}\) . These vertices have to form a valid vertex cover of \(G\)  because the subgraph of \(H^{2}\)  induced by \(V_{G}\)  is exactly \(G\) .
For the second part of the theorem, we follow a line similar to that of Theorem REF , as follows. Let \(ALG\)  be a \((1+\varepsilon )\) -approximation scheme for MVC on \(G^2\)  that completes in \(\operatorname{\text{{\rm poly}}}(n, \frac{1}{\varepsilon })\)  time. We construct the same graph \(H\)  from \(G\)  as before by adding a dangling path gadget \(DP_{e}\)  for each edge \(e \in E_{G}\) . We run \(ALG\)  on \(H^{2}\)  with \(\varepsilon = 1/(3|E_{G}|)\) . Note that by the previous argument the size of the minimum vertex cover of \(H^{2}\)  is \(c + 2|E_{G}|\)  where \(c\)  is the size of the minimum vertex cover in \(G\) . Therefore, \(ALG\)  will find a vertex cover of size at most \((1+\varepsilon )(c + 2|E_{G}|) = c + 2|E_{G}| + (c + 2|E_{G}|)/(3|E_{G}|) = c + 2|E_{G}| + \alpha \)  where \(\alpha < 1\) . Therefore, \(ALG\)  runs in polynomial time and we can find the MVC of \(G\)  by taking the solution returned by \(ALG\)  and taking all the corresponding \(V_{G}\)  vertices in the cover. This contradicts the \(NP\) -hardness of vertex cover in \(G\)  (assuming \(P \ne NP\) ).
We also show that one cannot efficiently compute good approximations of \(G^2\) -MDS unless one obtains a major breakthrough result.
Theorem 45 (No better-than-\(\ln n\) -approximation for MDS on \(G^2\) ) 

Given input graph \(G\) , solving MDS exactly on \(G^2\)  is NP-complete.
Moreover, if there is some \(\varepsilon > 0\)  such that a polynomial-time algorithm can solve MDS on \(G^2\)  to within an approximation factor of \((1 - \varepsilon ) \ln n\) , then \(NP \subseteq DTIME\left(n^{O(\log \log n)}\right)\) .

We prove this by showing a polynomial time reduction from MDS in \(G\)  to MDS in \(G^{2}\) . The theorem follows by the hardness of approximation result for \(G\)  [51]}. The reduction is that for each edge \(e\)  in \(G=(V_G,E_G)\) , we add a dangling path gadget \(DP_{e}\)  and merge all the dangling path gadgets in \(G\)  to form the merged path gadget \(DP_{E}\) . We call this new graph \(H=(V_H,E_H)\) . Note that \(H\)  has \(O(m)\)  vertices where \(m = |E_{G}|\)  which is polynomial in the size of \(G\) . The vertices in \(V_{H}\)  can be partitioned into two sets, namely the vertices in \(DP_{E}\)  and the vertices corresponding to \(V_{G}\) , which we call the \(G\) -vertices. Now we show that the size of the MDS in \(H^{2}\)  is \(W + 1\) , iff the size of the MDS in \(G\)  is \(W\) .
We start with the forward direction, let \(S_{H}\)  be an MDS of \(H^{2}\)  having size \(W+1\) . By lem:merged-gadget-vertex-in-mds we know that \(DP_{E}[3]\)  has to belong to \(S_{H}\)  (and therefore \(W \ge 0\) ) and it covers all the vertices in the merged path gadget \(DP_{E}\) . Note that given \(DP_{E}[3]\)  is in \(S_{H}\) , we can assume that no other vertex of \(DP_{E}\)  can belong to \(S_{H}\)  by arguing along similar lines as the proof of lem:no-other-dangling-gadget-in-mds. Now \(S_{H}\)  needs to cover the \(G\) -vertices in \(H\) , without using any vertices in \(DP_{E}\) . The subgraph of \(H^{2}\)  induced by the \(G\) -vertices is exactly the graph \(G\) . So \(S_{H} \setminus \lbrace DP_{E}[3]\rbrace \)  must form an MDS of \(G\)  because if \(G\)  has a dominating set \(S\)  of size \(< W\) , then it contradicts the optimality of \(S_{H}\)  because \(S \cup \lbrace DP_{E}[3]\rbrace \)  is a valid dominating set of \(H^{2}\)  having size \(< W + 1\) .
To prove the reverse direction, let \(S_{G}\)  be an MDS of \(G\)  of size \(W\) . We construct \(S_{H}\)  by taking the \(G\) -vertices in \(H^{2}\)  corresponding to \(S_{G}\)  along with the vertex \(DP_{E}[3]\) . The set \(S_{H}\)  has size \(W+1\)  and it covers all the vertices in \(H^{2}\)  because the vertices corresponding to \(S_{G}\)  dominate all the \(G\) -vertices in \(H^{2}\) , and \(DP_{E}[3]\)  dominates all the vertices in \(DP_{E}\) . Therefore, \(S_{H}\)  is a dominating set of \(H^{2}\)  of size \(W+1\) . Note that \(H^{2}\)  cannot have a smaller dominating set because then we can use the argument for the forward direction to extract a dominating set of \(G\)  of size \(< W\) , which contradicts the assumption that \(S_{G}\)  is an MDS of \(G\) .

Acknowledgement
This project was partially supported by the European Union's Horizon 2020 Research and Innovation Programme under grant agreement no. 755839 (Keren Censor-Hillel, Yannic Maus).
