hide
Free keywords:
-
Abstract:
Given a finite set $V$, and integers $k \geq 1$ and $r \geq 0$,
denote by $\AA(k,r)$ the class of hypergraphs $\cA \subseteq 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(\cA,\cI)$:
given a hypergraph $\cA$ and a subfamily $\cI \subseteq \In$,
of its maximal independent sets (MIS) $\In$, either extend this subfamily by
constructing a new MIS $I \in \In \setminus \cI$
or prove that there are no more MIS, that is $\cI = \In$.
We show that for hypergraphs $\cA\in\AA(k,r)$ with $k+r\le const$, problem
MIS$(\cA,\cI)$ is NC-reducible to problem MIS$(\cA',\emptyset)$ of generating a
single MIS for
a partial subhypergraph $\cA'$ of $\cA$. 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 $\AA(1,c)$, $\AA(c,0)$, and $\AA(2,1)$, where $c$ is a constant. We
also show that,
for $\cA \in \AA(k,r)$, where $k+r\le const$, the problem of
generating all MIS of $\cA$ can be solved in incremental polynomial-time with
space polynomial only in the size of $\cA$.
