Abstract
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
)
∖
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̸
)
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
.