2004-44: Computing Many Maximal Independent Sets for Hypergraphs in Parallel

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