2026-07-21T19:38:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22949 2025-10-02T12:19:26Z ddc:004 open_access

Enumeration of Minimal Hitting Sets Parameterized by Treewidth Kenig, Batya Mizrahi, Dan Shlomo Enumeration Hitting sets Enumerating the minimal hitting sets of a hypergraph is a problem which arises in many data management applications that include constraint mining, discovering unique column combinations, and enumerating database repairs. Previously, Eiter et al. [Thomas Eiter et al., 2003] showed that the minimal hitting sets of an n-vertex hypergraph, with treewidth w, can be enumerated with delay O^*(n^w) (ignoring polynomial factors), with space requirements that scale with the output size. We improve this to fixed-parameter-linear delay, following an FPT preprocessing phase. The memory consumption of our algorithm is exponential with respect to the treewidth of the hypergraph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Batya Kenig and Dan Shlomo Mizrahi 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.8 urn:nbn:de:0030-drops-229498 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode