zbMATH — the first resource for mathematics

The union of minimal hitting sets: parameterized combinatorial bounds and counting. (English) Zbl 1186.05087
Thomas, Wolfgang (ed.) et al., STACS 2007. 24th annual symposium on theoretical aspects of computer science, Aachen, Germany, February 22–24, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-70917-6/pbk). Lecture Notes in Computer Science 4393, 332-343 (2007).
Summary: We study how many vertices in a rank-\(r\) hypergraph can belong to the union of all inclusion-minimal hitting sets of at most \(k\) vertices. This union is interesting in certain combinatorial inference problems with hitting sets as hypotheses, as it provides a problem kernel for likelihood computations (which are essentially counting problems) and contains the most likely elements of hypotheses. We give worst-case bounds on the size of the union, depending on parameters \(r,k\) and the size \(k^{*}\) of a minimum hitting set. (Note that \(k \geq k^{*}\) is allowed.) Our result for \(r = 2\) is tight. The exact worst-case size for any \(r \geq 3\) remains widely open. By several hypergraph decompositions we achieve nontrivial bounds with potential for further improvements.
For the entire collection see [Zbl 1115.68007].

05C65 Hypergraphs
68R10 Graph theory (including graph drawing) in computer science
68W40 Analysis of algorithms
Full Text: DOI