문제

Let's say we have a universe $U$ of $n$ elements and a collection $S$ of $m$ subsets of $U$, i.e., $S=\{S_1,\ldots,S_m\}$, and a positive integer $k$. If I ask "is there a set cover of $U$ of size $k$ or less", then this is NP-complete.

Now suppose that I add the following:

  1. $|S_1| \gt |S_2| \gt \ldots \gt |S_m|$.

Is this still NP-complete?

I guess that, given 1., we know that the sets $S_i$ are all distinct and then the only cover for $U$ is $S$ but I am not sure about this.

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top