Minimal dominating sets enumeration with FPT-delay parameterized by the degeneracy and maximum degree

Abstract

At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an \(n^{O(d)}\)-delay algorithm listing all minimal transversals of an \(n\)-vertex hypergraph of degeneracy \(d\), for an appropriate definition of degeneracy. Recently at IWOCA 2019, Conte, Kant\'e, Marino, and Uno asked whether, even for a more restrictive notion of degeneracy, this XP-delay algorithm parameterized by \(d\) could be made FPT-delay parameterized by \(d\) and the maximum degree \(\Delta\), i.e., an algorithm with delay \(f(d,\Delta)\cdot n^{O(1)}\) for some computable function \(f\). We answer this question in the affirmative whenever the hypergraph corresponds to the closed neighborhoods of a graph, i.e., we show that the intimately related problem of enumerating minimal dominating sets in graphs admits an FPT-delay algorithm parameterized by the degeneracy and the maximum degree.