P141: Enumeration of all minimal transversal in a hypergraph
P141: Enumeration of all minimal transversal in a hypergraph
Input:
A hypergraph $\mathcal{H}\in A(k, r)$.
Output:
All minimal transversal in $\mathcal{H}$.
Complexity:
$O(n^{k+r+1}|\mathcal{H}^d|^{r+1})$ total time and $O(N^{r+1})$ total space.
Comment:
$A(k, r)$ is the class of hyperedges with $(k, r)$-bounded intersections, i.e. in which the intersection of any $k$ distinct hyperedges has size at most $r$. Minimal transversals of hypergraphs in some restricted classes can be enumerating in polynomial delay and space.