Advertisement
Published in:
2007 | OriginalPaper | Chapter
The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
≥
k
*
is allowed.) Our result for
r
= 2 is tight. The exact worst-case size for any
r
≥ 3 remains widely open. By several hypergraph decompositions we achieve nontrivial bounds with potential for further improvements.