Revisiting a Successful Reduction Rule for Dominating Set

Lukas Geis, Alexander Leonhardt, Johannes Meintrup +3

Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, the DominatingSet problem asks for a set $D\subseteq V$ of minimal cardinality such that every vertex either is in $D$…