Enumeration of Minimal Hitting Sets Parameterized by Treewidth
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912204868026368 |
|---|---|
| author | Kenig, Batya Mizrahi, Dan Shlomo |
| author_facet | Kenig, Batya Mizrahi, Dan Shlomo |
| contents | 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. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15776 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Enumeration of Minimal Hitting Sets Parameterized by Treewidth Kenig, Batya Mizrahi, Dan Shlomo Databases Data Structures and Algorithms 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. 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. |
| title | Enumeration of Minimal Hitting Sets Parameterized by Treewidth |
| topic | Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.15776 |