# Tag Info

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
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

### 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