Efficiently enumerating hitting sets of hypergraphs arising in data profiling

DOI10.1137/1.9781611975499.11MaRDI QIDQ5232759zbMATH OpenOpenAlexFDO

Authors Thomas Bläsius, Tobias Friedrich, Julius Lischeid, Kitty Meeks, Martin Schirneck

Publication date 13 September 2019

Published in 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.01310

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: The transversal hypergraph problem is the task of enumerating the minimal hitting sets of a hypergraph. It is a long-standing open question whether this can be done in output-polynomial time. For hypergraphs whose solutions have bounded size, Eiter and Gottlob [SICOMP 1995] gave an algorithm that runs in output-polynomial time, but whose space requirement also scales with the output size. We improve this to polynomial delay and polynomial space. More generally, we present an algorithm that on $n$-vertex, $m$-edge hypergraphs has delay $O(m^{k^{\ast }+1}{n}^2)$ and uses $O(mn)$ space, where $k^{\ast }$ is the maximum size of any minimal hitting set. Our algorithm is oblivious to $k^{\ast }$, a quantity that is hard to compute or even approximate. Central to our approach is the extension problem for minimal hitting sets, deciding for a set $X$ of vertices whether it is contained in any solution. With $|X|$ as parameter, we show that this is one of the first natural problems to be complete for the complexity class $W[3]$. We give an algorithm for the extension problem running in time $O(m^{|X|+1}n)$. We also prove a conditional lower bound under the Strong Exponential Time Hypothesis, showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.

Recommendations

• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph
• Efficient algorithms for dualizing large-scale hypergraphs
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals

Cited in

(15)

• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• The complexity of dependency detection and discovery in relational databases
• On the complexity of solution extension of optimization problems
• Optimal-size problem kernels for d-Hitting Set in linear time and space
• Parameterized complexity of computing maximum minimal blocking and hitting sets
• A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• scientific article; zbMATH DE number 7651160 (Why is no real title available?)
• Minimal Roman dominating functions: extensions and enumeration
• Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
• Minimal Roman dominating functions: extensions and enumeration
• Roman hitting functions
• From amortized to worst case delay in enumeration algorithms

This page was built for publication: Efficiently enumerating hitting sets of hypergraphs arising in data profiling

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