Pith. sign in

REVIEW

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

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2305.06974 v4 pith:VT6FQN6M submitted 2023-05-11 cs.DS cs.DMmath.CO

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

classification cs.DS cs.DMmath.CO
keywords algorithmdegeneracyparameterizedfpt-delayminimaldelaydeltadimension
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original 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$. Recently at IWOCA 2019, Conte, Kant\'e, Marino, and Uno asked whether this XP-delay algorithm parameterized by $d$ could be made FPT-delay for a weaker notion of degeneracy, or even parameterized by the maximum degree $\Delta$, i.e., whether it can be turned into an algorithm with delay $f(\Delta)\cdot n^{O(1)}$ for some computable function $f$. Moreover, and as a first step toward answering that question, they note that they could not achieve these time bounds even for the particular case of minimal dominating sets enumeration. In this paper, using ordered generation, we show that an FPT-delay algorithm can be devised for minimal transversals enumeration parameterized by the degeneracy and dimension, giving a positive and more general answer to the latter question.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.