2
$\begingroup$

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.

$\endgroup$

closed as off-topic by Emil Jeřábek, Ryan Budney, Stefan Kohl, S. Carnahan Jul 31 '14 at 14:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Emil Jeřábek, Ryan Budney, Stefan Kohl, S. Carnahan
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ As written, $\lambda$ does not do anything. Do you perhaps intend it to be part of the input rather than output? Or maybe a fixed parameter of the problem? Either way, exact cover is obviously a special case of your problem where all the weights are the same and $\lambda$ is set smaller, so I don’t understand where is supposed to be the problem. $\endgroup$ – Emil Jeřábek Jul 30 '14 at 15:15
  • $\begingroup$ Thanks Emil. $\lambda$ is one input. As to canonical exact cover problem, each set is assigned with identical weight, people check whether the number of sets (also is the sum of weights in the same time) exceeds one given integer number. My proposed problem has two differences with the canonical one, firstly, sets are given different weights, secondly, 'average weight' in stead of summation of weights are considered. $\endgroup$ – ulyssis2 Jul 30 '14 at 16:33
  • $\begingroup$ The canonical exact cover problem does not involve any sums of weights, it just asks whether $U$ can be written as a disjoint union of a subcollection of $S$. This is a special case of your problem with all weights 1, and $\lambda=1/2$ (say). $\endgroup$ – Emil Jeřábek Jul 30 '14 at 16:47
  • $\begingroup$ OK, I somehow misunderstood the canonical exact set cover, the weighted exact set cover problem which involves restriction on summation is a very different problem. One draft (arxiv.org/abs/1302.5820) gives proof on NP hardness of weighted exact set cover. $\endgroup$ – ulyssis2 Jul 30 '14 at 17:34
  • $\begingroup$ I agree with you that canonical exact cover is one special case of my proposed problem, but I want to see how to prove my problem to be NP-hard. $\endgroup$ – ulyssis2 Jul 30 '14 at 17:35