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. ...
user avatar
  • 5,722
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 5,722

Only top scored, non community-wiki answers of a minimum length are eligible