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)) ; Leonid Molokov (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
Journal of Discrete Algorithms (1570-8667). Vol. 7 (2009), 4, p. 391-401.
[Artikel, refereegranskad vetenskaplig]

A k-hitting set in a hypergraph is a set of at most k vertices that intersects all hyperedges. We study the union of all inclusion-minimal k-hitting sets in hypergraphs of rank r (where the rank is the maximum size of hyperedges). We show that this union is relevant for certain combinatorial inference problems and give worst-case bounds on its size, depending on r and k. For r=2 our result is tight, and for each r>2 we have an asymptotically optimal bound and make progress regarding the constant factor. The exact worst-case size for r>2 remains an open problem. We also propose an algorithm for counting all k-hitting sets in hypergraphs of rank r. Its asymptotic runtime matches the best one known for the much more special problem of finding one k-hitting set. The results are used for efficient counting of k-hitting sets that contain any particular vertex.

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



Denna post skapades 2009-10-22. Senast ändrad 2015-02-11.
CPL Pubid: 100555