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$
8
  • 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$ Jul 30, 2014 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, 2014 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$ Jul 30, 2014 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, 2014 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, 2014 at 17:35

0