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 [1]}, 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 [1]} does not show
any lower bounds for approximating MDS on \(G\) .
However, [1]} 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 [1]}: Our bounds are indeed quadratic lower bounds for approximation of \(G^2\) -MDS, and our results remove the necessity of weights.
