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