TY - CHAP

T1 - Generating maximal independent sets for hypergraphs with bounded edge-intersections

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Khachiyan, Leonid

PY - 2004

Y1 - 2004

N2 - Given a finite set V, and integers k ≥ 1 and r ≥ 0, 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 τ. 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)\I or prove that there are no more MIS, that is I = I(A). We show that for hypergraphs A ∈ A(k,r) with k + r ≤ const, problem MIS(A,I) is NC-reducible to problem MIS(A′,θ) of generating a single MIS for a partial subhypergraph A′ of A. In particular, for this class of hypergraphs, we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximal independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes A (1,c), A(c,0), and A(2,1), where c 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 with space polynomial only in the size of A.

AB - Given a finite set V, and integers k ≥ 1 and r ≥ 0, 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 τ. 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)\I or prove that there are no more MIS, that is I = I(A). We show that for hypergraphs A ∈ A(k,r) with k + r ≤ const, problem MIS(A,I) is NC-reducible to problem MIS(A′,θ) of generating a single MIS for a partial subhypergraph A′ of A. In particular, for this class of hypergraphs, we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximal independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes A (1,c), A(c,0), and A(2,1), where c 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 with space polynomial only in the size of A.

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

U2 - 10.1007/978-3-540-24698-5_52

DO - 10.1007/978-3-540-24698-5_52

M3 - Chapter

AN - SCOPUS:26844484980

SN - 3540212582

SN - 9783540212584

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 488

EP - 498

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Farach-Colton, Martin

PB - Springer Verlag

ER -