Parameterized complexity of Exact Cover
Correction: I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods. ...
Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover
It's also NP-hard, because Set Cover on sets of constant size is NP-hard, and given an instance of Set Cover with constant-size sets, you can add all the (polynomially many) subsets of the given sets, ...
exact cover set problem
To convert to MaxSAT: For each set $ S $ introduce a fresh variable $ X_S $. If two sets $ S $ and $ D $ intersect, produce the hard clause $\lnot X_S\lor \lnot X_D$. For each element $e$ produce the ...
Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets
I think the problem of hyperedge coloring of a 3-regular 3-uniform hypergraph (with 3 colors) is reducible to this problem and vice versa, where the set X is corresponds to the vertex set V and each ...
Covering by disjoint sets
Your first problem is more or less in-approximable. It contains "Independent Set" as a special case. For a graph $G=(V,E)$, define your ground set as $U:=V$ and for every vertex $v\in V$ construct a ...
Only top scored, non community-wiki answers of a minimum length are eligible