

A deterministic \((1+\varepsilon )\) -approximation algorithm for \(G^2\) -MVC in the \(\mathsf {CONGEST}\)  modelIn the \(\mathsf {CONGEST}\)  model ([1]}) a communication network is abstracted as an \(n\) -node graph. In synchronous rounds each node can send a \(O(\log n)\)  bit message to each of its neighbors. The complexity is the number of rounds until each node has computed its output, e.g., whether it belongs to a VC or not.
which completes in \(O(n/\varepsilon )\)  rounds, for any \(\varepsilon > 0\) . We also provide an algorithm with these guarantees for weighted \(G^2\) -MVC (denoted by \(G^2\) -MWVC).
In comparison, for MVC on \(G\)  in the \(\mathsf {CONGEST}\)  model,
the fastest algorithm for any better-than-2 approximation factor is the naive \(O(n^2)\) -round algorithm.


A deterministic polynomial time centralized algorithm that gives a \(5/3\) -approximation for \(G^2\) -MVC while we also show that MVC remains hard on \(G^2\) , i.e., it does not admit a FPTAS unless \(P = NP\) .
Our algorithm should be contrasted with the celebrated
UGC hardness of a polynomial time algorithm for any better-than-2 approximation [2]}.
Given the hardness of finding a better-than-2-approximation algorithm for MVC, there is a long line of research on the approximability of MVC on
specific graph classes [3]}, [4]}, [5]}.
Our result contributes to this line of research.


A lower bound of \(\tilde{\Omega }(n^2)\)  rounds for any \(c\) -approximation algorithm with \(c<7/6\)  for weighted \(G^2\) -MDS (denoted \(G^2\) -MWDS) in the \(\mathsf {CONGEST}\)  model. We also provide such a quadratic lower bound when \(c<9/8\)  for the unweighted case.
In comparison, for MDS on \(G\)  in the \(\mathsf {CONGEST}\)  model, no super-polylogarithmic lower bound is known for any approximation factor that is smaller than \(\ln \Delta \) , where \(\Delta \)  is the maximum degree in \(G\) , and the best algorithm for any better-than-\(O(\log \Delta )\)  approximation factor is the naive \(O(n^2)\) -round algorithm. The best known lower bounds are a \(\tilde{\Omega }(n^2)\)  lower bound for exact MDS, and a \(\tilde{\Omega }(n)\)  lower bound for a \(O(1)\) -approximation [6]}.
We also point out that Bachrach et al. [6]} do consider the \(G^2\) -MWDS problem and provide lower bounds, e.g., a linear lower bound of \(O(\log n)\) -approximation.

