TY - JOUR

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

AU - Khachiyan, Leonid

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

N1 - Funding Information:
I This research was supported in part by the National Science Foundation, grant IIS-0118635. The research of the second and fourth authors was also supported in part by the Office of Naval Research, grant N00014-92-J-1375. The authors are also grateful for partial support by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science. ∗Corresponding author. E-mail addresses: [email protected] (E. Boros), [email protected] (K. Elbassioni), [email protected] (V. Gurvich). @Our friend and co-author, Leonid Khachiyan passed away with tragic suddenness, while we were working on the final version of this paper.

PY - 2007/8/31

Y1 - 2007/8/31

N2 - Given a finite set V, and integers k ≥ 1 and r ≥ 0, let us denote by A (k, r) the class of hypergraphs A ⊆ 2V 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.

AB - Given a finite set V, and integers k ≥ 1 and r ≥ 0, let us denote by A (k, r) the class of hypergraphs A ⊆ 2V 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.

KW - Bounded degree

KW - Bounded dimension

KW - Conformal hypergraph

KW - Dualization

KW - Incremental generating

KW - Maximal independent set

KW - Minimal transversal

KW - Polynomial space

UR - http://www.scopus.com/inward/record.url?scp=34547522369&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2007.03.005

DO - 10.1016/j.tcs.2007.03.005

M3 - Article

AN - SCOPUS:34547522369

SN - 0304-3975

VL - 382

SP - 139

EP - 150

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

ER -