DIMACS TR: 2004-31

A Global Parallel Algorithm for Finding All Minimal Transversals of Hypergraphs of Bounded Edge-size

Authors: E. Boros, K. Elbassioni, V. Gurvich and L. Khachiyan

We give a deterministic parallel algorithm that, for any given hypergraph $\cH\subseteq 2^V$ with maximum edge-size less than $\delta$, outputs all minimal transversals (or equivalently all maximal independent sets) of $\cH$ in time $O(\delta^2\log^2 n\log m)$ using $O(n^{\delta\log\delta+2} m^{\delta})$ processors on a CREW-PRAM, where $m$ is the total number of minimal transversals and $n=|V|$. This algorithm can be modified so that, for any integer $k$, it outputs $k$ minimal transversals of $\cH$ in time $O(\delta^2\log^2 n \log k+T)$ using $O(n^{\delta\log\delta+1} k^{\delta}+k\Pi)$ processors, where $T$ and $\Pi$ are respectively the parallel time and the number of processors required to generate a single minimal transversal of $\cH$. The latter problem is known to be in RNC for hypergraphs of bounded edge-size. This strengthens and generalizes a previously known result for graphs. We also obtain a similar result for hypergraphs whose transversal hypergraphs are $\delta$-conformal for some constant $\delta$.

Key Words:
Bounded dimension, conformal hypergraph, dualization, global parallel algorithm, hypergraph, incremental generating, maximal independent set, minimal transversal.

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

DIMACS Home Page