Compression with wildcards: All exact or all minimal hitting sets

Abstract

Our objective is the compressed enumeration (based on wildcards) of all minimal hitting sets of general hypergraphs. To the author’s best knowledge, the only previous attempt towards compression, due to Toda, is based on binary decision diagrams and much different from our techniques. Traditional one-by-one enumeration schemes cannot compete when the number of minimal hitting sets is large and the degree of compression is high. Our method works particularly well in these two cases: either compressing all minimum cardinality hitting sets, or compressing all exact hitting sets.

Keywords

• hitting set (minimal, minimum, exact)
• compressed enumeration
• vertical layout
• 05c65
• 05a15
• 05b35
• 05c85