7
votes
Accepted
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.
...
- 5,742
4
votes
Accepted
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, ...
- 9,495
3
votes
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 ...
- 1,312
1
vote
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 ...
1
vote
Accepted
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 ...
- 5,742
Only top scored, non community-wiki answers of a minimum length are eligible