P140: Enumeration of all maximal independent sets in a hypergraph of bounded intersections
P140: Enumeration of all maximal independent sets in a hypergraph of bounded intersections
Input:
A hypergraph $\mathcal{H} \in A(k, r)$, where $k + r \le$ constant.
Output:
All maximal independent sets in $\mathcal{H}$.
Complexity:
Incremental polynomial time with polynomial 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$.