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:


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?


2 Answers 2


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.

  • $\begingroup$ 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/… $\endgroup$ Nov 23, 2011 at 19:06
  • $\begingroup$ The approximation threshold is actually $3 - \epsilon$. $\endgroup$ Nov 23, 2011 at 21:57
  • 1
    $\begingroup$ @MCH: Reference? $\endgroup$ Nov 24, 2011 at 0:16
  • 1
    $\begingroup$ No, its $2-\epsilon$: for $k$-uniform hypergraph vertex cover, they show hardness of approximation to within $(k-1-\epsilon)$. $\endgroup$ Nov 24, 2011 at 8:56
  • 1
    $\begingroup$ 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. $\endgroup$ 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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.