Given a matrix $A = (a_{ij})_{m \times n}$, where $a_{ij} \in S := \{1,2,\ldots,k\}$, assume that every row of $A$ contains all members from $S$, i.e, $$\bigcup_j \{a_{ij}\} = S \tag{property $\mathcal{M}$}$$ Given $p$, my question is how to select $p$ columns of $A$ such that the obtained matrix has property $\mathcal{M}$.
I have been thinking for a while but I am stuck. Does anyone have any idea? or some related problem. Thanks!
A related but more general problem is set covering, which is to find the minimum number of sets to cover a given ground set. In your problem, the sets correspond to the columns of $A$, and the ground set is the set of pairs $(i,s)$, where $i$ is a row and $s\in S$.