Combinatorial Bounds via Measure and Conquer: Bounding Minimal Dominating Sets and Applications

We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O(1.7159(n)). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159(n), thus improving on the trivial O(2(n)/root n) bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms. Based on this result, we derive an O(2.8718(n)) algorithm for the domatic number problem.