There is a vast body of research on approximating MVC and MDS in the sequential
setting; we refer to the references in [1]}, [2]}
as an introduction to this literature.
Since there has been no progress on approximating MVC with an
approximation factor that is smaller than 2, researchers have studied the problem of approximating
MVC on restricted graph classes, such as planar graphs [3]},
bounded-degree graphs [4]}, and
graphs with perfect matchings [5]}.
More recently, research in distributed approximation algorithms for
MVC and MDS received a lot of attention.
Bar-Yehuda et al. [6]} present a deterministic
\((2+\varepsilon )\) -approximation algorithm for MWVC in \(O(\log \Delta /\varepsilon \log \log \Delta )\)  rounds, where
the \(\Delta \) -dependency is optimal due to the lower bound of Kuhn et al. [7]}.
Ben-Basat et al. [8]} shave off the \(\varepsilon \)  term in the approximation factor
and present a deterministic 2-approximation algorithm for the MWVC problem in the \(\mathsf {CONGEST}\)  model at the cost of an increased runtime of \(O(\log n\log \Delta /\log ^2\log \Delta )\)  rounds.
For MDS, Censor-Hillel and Dory [9]} obtain an \(O(\log \Delta )\) -approximation
in \(O(\log n\log \Delta )\)  rounds, improving on the result by Jia et al. [10]} that achieves
this approximation in expectation.
Both of these algorithms are randomized, whereas Ghaffari et al. [11]} and Deurer et al. [12]}
present deterministic algorithms for MDS with approximation factors \(O(\log \Delta ^2)\)  and \((1+\varepsilon )(1+\ln (\Delta +1))\) , respectively. Both algorithms rely on a network decomposition of \(G^2\)  and [11]} provided a \(2^{O(\sqrt{\log n\log \log n})}\)  round CONGEST algorithm to compute such a decomposition; due to the faster decomposition algorithm from [14]} (that also works for \(G^2\)  and in the CONGEST model) both algorithms now run in \(\operatorname{\operatorname{\text{{\rm poly}}}\log }n\)  rounds.
