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

05/11/2023
by   Valentin Bartier, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset