12
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
21
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\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
    Commented Nov 23, 2011 at 19:06
  • $\begingroup$ The approximation threshold is actually $3 - \epsilon$. $\endgroup$
    – Mahdi Cheraghchi
    Commented Nov 23, 2011 at 21:57
  • 1
    $\begingroup$ @MCH: Reference? $\endgroup$
    – Tsuyoshi Ito
    Commented 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$
    – Jan Johannsen
    Commented 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$
    – krumpelstiltskin
    Commented Nov 26, 2011 at 3:09
7
$\begingroup$

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

Improve this answer
$\endgroup$

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.