CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The union of minimal hitting sets: Parameterized combinatorial bounds and counting

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
24th Symposium on Theoretical Aspects of Computer Science STACS 2007, Lecture Notes in Computer Science (0302-9743). Vol. 4393 (2007), p. 332-343.
[Konferensbidrag, refereegranskat]

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 of a minimum hitting set. Our result for r=2 is tight. The exact worst-case size for any r>2 remains widely open. By several hypergraph decompositions we achieve nontrivial bounds with potential for further improvements.

Nyckelord: algorithms, parameterization, combinatorial inference, counting, hypergraph transversals

Denna post skapades 2007-03-07. Senast ändrad 2015-02-11.
CPL Pubid: 26569