Is the set cover problem NP-complete when the cardinality of the collection of sets is equal to the cardinality of the universe?
Yes, it is still NP-complete. If you have an instance with $n &lt; m$, then you can pad $U$ with $m - n + 1$ new elements and add new subset containing only the new elements. The original instance has a solution of size $s$ if and only the padded instance has a solution of size $s + 1$. The reduction is obviously polynomial time.