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?


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$ – Radu GRIGore Nov 23 '11 at 19:06
  • $\begingroup$ The approximation threshold is actually $3 - \epsilon$. $\endgroup$ – MCH Nov 23 '11 at 21:57
  • 1
    $\begingroup$ @MCH: Reference? $\endgroup$ – Tsuyoshi Ito Nov 24 '11 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$ – Jan Johannsen Nov 24 '11 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$ – krumpelstiltskin Nov 26 '11 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, privacy policy and cookie policy

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