## DIMACS TR: 2004-44

##
Computing Many Maximal Independent Sets for Hypergraphs in Parallel

### Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan

**
ABSTRACT
**
A hypergraph $\cH\subseteq 2^V$ is called {\em uniformly
$\delta$-sparse} if for every nonempty subset $X\subseteq V$ of
vertices, the average degree of the sub-hypergraph of $\cH$ induced by $X$
is at most $\delta$. We show that there is a
deterministic algorithm that, given a uniformly $\delta$-sparse hypergraph
$\cH$, and a positive integer $k$, outputs $k$ or
all minimal transversals for $\cH$ in $O(\delta \log
(1+k)\mbox{polylog}(\delta|V|))$-time using $|V|^{O(\log
\delta)}k^{O(\delta)}$ processors. Equivalently, the algorithm can be
used to compute in parallel $k$ or all maximal
independent sets for $\cH$.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-44.ps.gz

DIMACS Home Page