# Tag Info

7

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. In fact, "Exact Cover" is contained in W[1]. It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & Grohe), and therefore lies in W[1]: ...

3

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 hard clause $\bigvee_{e\in S} X_S$, making sure that at least one set that contains $e$ is selected. For each set $S$ with weight $W$ produce the soft ...

1

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 corresponding subset $S_v$ in your set system that contains the (closed) neighborhood of $v$. Then finding a cardinality-$k$ independent set in $G$ is equivalent ...

1

Problem 1 is known as SET PACKING. Like other packing problems, it's annoyingly hard. The best known bound is a $O(\sqrt{|S|})$ approximation and it is indeed APX-hard.

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