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. [1]} 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)\) .
