Minimal dominating sets enumeration with FPT-delay parameterized by the degeneracy and maximum degree
share
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é, 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 Δ, i.e., an algorithm with delay f(d,Δ)· 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.
READ FULL TEXT