On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs

Given a finite set V, and integers k ≥ 1 and r ≥ 0, let us denote by A (k, r) the class of hypergraphs A ⊆ 2^V with (k, r)-bounded intersections, i.e. in which the intersection of any k distinct hyperedges has size at most r. We consider the problem MIS (A, I): given a hypergraph A, and a subfamily I ⊆ I (A) of its maximal independent sets (MIS) I (A), either extend this subfamily by constructing a new MIS I ∈ I (A) {set minus} I or prove that there are no more MIS, that is I = I (A). It is known that, for hypergraphs of bounded dimension A (1, δ), as well as for hypergraphs of bounded degree A (δ, 0) (where δ is a constant), problem MIS (A, I) can be solved in incremental polynomial time. In this paper, we extend this result to any integers k, r such that k + r = δ is a constant. More precisely, we show that for hypergraphs A ∈ A (k, r) with k + r ≤ const, problem MIS (A, I) is NC-reducible to the problem MIS (A^′, 0{combining long solidus overlay}) of generating a single MIS for a partial subhypergraph A^′ of A. In particular, this implies that MIS (A, I) is polynomial, and we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximally independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes A (1, δ), A (δ, 0), and A (2, 1), where δ is a constant. We also show that, for A ∈ A (k, r), where k + r ≤ const, the problem of generating all MIS of A can be solved in incremental polynomial-time and with space polynomial only in the size of A.