On the Parameterized Complexity of Approximating Dominating Set

Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

We study the parameterized complexity of approximating the $k$-Dominating Set (DomSet) problem where an integer $k$ and a graph $G$ on $n$ vertices are given as input, and the goal…