Exact Transversal Hypergraphs and Application to Boolean μ-Functions

✍ Scribed by Thomas Eiter

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 353 KB
• Volume: 17
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1994.1013

✦ Synopsis

Call an hypergraph, that is a family of subsets (edges) from a finite vertex set, an exact transversal hypergraph iff each of its minimal transversals, i.e., minimal vertex subsets that intersect each edge, meets each edge in a singleton. We show that such hypergraphs are recognizable in polynomial time and that their minimal transversals as well as their maximal independent sets can be generated in lexicographic order with polynomial delay between subsequent outputs, which is impossible in the general case unless (\mathbf{P}=) NP. The results obtained are applied to monotone Boolean (\mu)-functions, that are Boolean functions defined by a monotone Boolean expression (that is, built with (\wedge, \vee) only) in which no variable occurs repeatedly. We also show that recognizing such functions from monotone Boolean expressions is co-NP-hard, thus complementing Mundici's result that this problem is in co-NP.