Finding the maximum number of maximal independent sets in an $n$-vertex graph $G$, $i(G)$, from a restricted class is an extensively studied problem. Let $kK_2$ denote the matching of size $k$, that is a graph with $2k$ vertices and $k$ disjoint edges. A graph with an induced copy of $kK_2$ contains at least $2^k$ maximal independent sets. The other direction was established in a series of papers finally yielding $i(G) \le (n/k)^{ 2k}$ for a graph $G$ without an induced $(k+1)K_2$. Alekseev proved that $i(G)$ is at most the number of induced matchings of $G$. This work generalises the aforementioned results to clutters. The right substructures in this setting are minors rather than induced subgraphs. Maximal independent sets of a clutter $\mathcal{ H}$ are in one-to-one correspondence to the sets of its blocker, $b(\mathcal{ H})$, hence $i(\mathcal{ H}) = |b(\mathcal{ H})|$. We show that \[ |b(\mathcal{ H})| \le \sum_{ m=0}^{ k \cdot f(r)}{ |\mathcal{ H}| \choose m} { r \choose 2}^m \] for a $(k+1)K_2$-minor-free clutter $\mathcal{ H}$ where $f(r) = (2r-3)2^{ r-2}$ and $r$ is the maximum size of a set in $\mathcal{ H}$. A key step in the proofs is, similarly to Alekseev's result, showing that $i(\mathcal{ H})$ is bounded by the number of a substructure called semi-matching, and then proving a dependence between the number of semi-matchings and the number of minor matchings. Note that similarly to graphs, a clutter containing a $kK_2$ minor has at least $2^k$ maximal independent sets. From a computational perspective, a polynomial number of independent sets is particularly interesting. Our results lead to polynomial algorithms for restricted instances of many problems including Set Cover and k-SAT.
Categories: math.CO