# Minimum True Monotone 3SAT

I am interested in a SAT variation where the CNF formula is monotone (no variables are negated). Such a formula is obviously satisfiable.

But say the number of true variables is a measure of how good our solution is. So we have the following problem:

MINIMUM TRUE MONOTONE 3SAT

INSTANCE: Set U of variables, collection C of disjunctive clauses of 3 literals, where a literal is a variable (not negated).
SOLUTION: A truth assignment for U that satisfies C.
MEASURE: The number of variable that are true.

Could someone give me some helpful remarks on this problem?

This problem is the same as the Vertex Cover problem for $3$-uniform hypergraphs: given a collection $H$ of subsets of $V$ of size $3$ each, find a minimal subset $U\subseteq V$ that intersects each set in $H$.

It is therefore NP-hard, but fixed parameter tractable. It is also NP-hard to approximate to within a factor of $2-\epsilon$ for every $\epsilon>0$. This was shown in the following paper:

Irit Dinur, Venkatesan Guruswami, Subhash Khot and Oded Regev. A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover, SIAM Journal on Computing, 34(5):1129–1146, 2005.

• Another keyword would be "3-Hitting Set." I don't have access to the following paper now, but the title seems relevant: scholar.google.co.uk/… Commented Nov 23, 2011 at 19:06
• The approximation threshold is actually $3 - \epsilon$. Commented Nov 23, 2011 at 21:57
• @MCH: Reference? Commented Nov 24, 2011 at 0:16
• No, its $2-\epsilon$: for $k$-uniform hypergraph vertex cover, they show hardness of approximation to within $(k-1-\epsilon)$. Commented Nov 24, 2011 at 8:56
• oops... @MCH: i'm interested to see the $3 - \epsilon$ result as well. it would imply that the trivial approximation algorithm is the best we can hope for. Commented Nov 26, 2011 at 3:09

I would start by having a look at papers citing Downey and Fellows' paper, in which they consider the following problem and prove its $W[1]$-completeness.

WEIGHTED $q$-CNF SAT

Instance: A CNF formula $X$ (i.e., a formula in Conjunctive Normal Form) in which every clause contains $q$ variables.

Parameter: A positive integer $k$.

Question: Does X have a satisfying assignment of weight $k$, where the weight of an assignment is the number of variables it sets to "true"?