Abstract :
Call anhypergraph, that is a family of subsets (edges) from a finite vertex set, an exact transversal hypergraphiff 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 P= NP. The results obtained are applied to monotone Boolean μ-functions, that are Boolean functions defined by a monotone Boolean expression (that is, built with , 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.
