Proof Outline of thm:exact-mds-lower-bound-main-theorem: 
Bachrach et al. [1]} 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.
