Exact cover is NPC. http://en.wikipedia.org/wiki/Exact_cover#Equivalent_problems
Given a collection $\mathcal{S}$ of subsets of a set $X$, an exact cover is a >>subcollection $\mathcal{S}^*$ of $\mathcal{S}$ such that each element in $X$ >>is contained in exactly one subset in $\mathcal{S}^*.$
The optimization version of exact cover problem adds one more concern to maximize the cardinality of $\mathcal{S}^*$. We elaborate the optimization version of exact cover problem further by giving each set a weight. the formal statement of weighted exact cover problem is as follows,
Given a universe $U$, and collection $S=\{s_1, s_2, \ldots, s_m\}$ which contains set $s_i\subseteq U, i\in \{1,2,\ldots,m\}$, each subset $s_i$ is given a weight $w_i$. Whether there exists collection of subsets $\mathcal{C}$ where $\mathcal{C}\ni s_j, j\in\{1,2,\dots,m\}$, so that the union of $\mathcal{C}$ equals to $U$, and for $j\neq j'$, $j,j'\in \{1,2,\dots,m\}$, there is $s_j\cap s_{j'} = \emptyset$, furthermore, the sum weight of the sets in $\mathcal{C}$ is greater than one given number $\lambda$.
My question is, how to prove this problem to be NPC or NP-hard.
I guess weighted exact cover problem is NP-hard, because to check whether desired set collection exists or not, people first need to decide whether an exact set cover exists. I think this logic is right, as exact cover is NPC, the proposed problem involves one more procedure to check whether the found subcollection satisfies condition of $\lambda$. But I think it should not be so easy.
