Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension

arXiv2305.06974MaRDI QIDQ6510072FDOQ6510072

Authors: Valentin Bartier, Oscar Defrain, Fionn Mc Inerney 

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.

This page was built for publication: Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510072)