Revisiting a Successful Reduction Rule for Dominating Set
Abstract
Given a graph \(G = (V,\!E)\) with \(n\) vertices and \(m\) edges, the Dominating Set problem asks for a set \(\mathcal{D} \subseteq V\) of minimal cardinality such that every vertex either is in \(D\) or adjacent to a member of \(D\). Although there is little hope for a kernelization algorithm on general graphs due to the W[2]-hardness of Dominating Set, data reduction rules are extensively used in practice.
Fields of Study & Subjects
Distributed systems and fault tolerance
Cloud Computing and Resource Management
Graph Theory and Algorithms
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 114–126
- Publication date
- 1 January 2026
- Language
- EN