Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial

Adir Morgan, Shay Solomon, Nicole Wein

We revisit the minimum dominating set problem on graphs with arboricity bounded by $\alpha$. Bansal and Umboh [BU17] gave an $O(\alpha )$-approximation LP rounding algorithm, which also trans…