A hypergraph is a generalized structure of a graph in which an edge, called a hyperedge, can have more than two vertices. A subset T is said to be a transversal of a given hypergraph if it intersects every (non-empty) set of vertices in the hypergraph. A hypergraph is called an exact transversal hypergraph (xt-hypergraph) if every transversal of it is an exact transversal.
In the paper, Eiter first proposes an algorithm for xt-hypergraph recognition and establishes that recognizing xt-hypergraphs can be done in polynomial time with a runtime bounded by O(mS2), where m is the order of the hypergraph concerned and S is the input size. Following this, he proposes an algorithm to generate minimal transversals of a hypergraph and proves that the minimal traversals of an xt-hypergraph can be obtained in inverse lexicographic order with a delay of O(nS), and hence the maximal independent set can be obtained in lexicographic order with a delay of O(nS).
In the second half of the paper, the author describes some applications of the study to Boolean μ-functions. Let fE be a Boolean function corresponding to a monotone Boolean expression E in conjunctive normal form (CNF) or disjunctive normal form (DNF). The first theorem of the section states that deciding whether the function fE is μ-equivalent is possible in n2m3, where m is the number of clauses of E. It is also proved that deciding whether a Boolean function fE corresponding to a monotone Boolean expression E is a μ-function is co-NP-complete. As the final result of the paper, the author establishes that the prime implicants of the dual of an n-ary monotone μ-function f can be generated in lexicographic order with a delay of O(nS), provided the prime implicants of f are given.
The paper is written beautifully and the content is innovative and insightful.
