This is a follow-up on this question. Consider the same setup:

Assume that we have a set system $mathfrak T = {mathcal T_1, mathcal T_2, dots, mathcal T_N }$ where each $mathcal T_k$ is a collection of subsets of $(n) := {1,dots,n}$ of the form

$$ mathcal T_k = (m_k, M_k) := {T subseteq (n):; m_k subseteq T subseteq M_k }. $$

Moreover, we know that $mathcal T_k$s are mutually disjoint, i.e., $mathcal T_k cap mathcal T_{k’} = emptyset$ when $k neq k’$.

If the union of the sets in $mathfrak T$ does not cover $2^{(n)}$, can we find the **smallest** set not covered (or a smallest one if there are multiple) in polynomial-time?

Alternatively, given $s < n$, can we find a set of cardinality $le s$ that is not covered by $mathfrak T$, in time polynomial in $s$ (assuming such set exists)?