<p>I would start by having a look at papers citing <a href="http://mrfellows.net/papers/DF95_FPTandCompletenessI.pdf">Downey and Fellows' paper</a>, in which they consider the following problem and prove its $W[1]$-completeness.</p>

<p><strong>WEIGHTED $q$-CNF SAT</strong></p>

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

<p><strong>Parameter:</strong> A positive integer $k$.</p>

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

CC BY-SA 3.0
2011-11-23T15:37:09.657Z
2011-11-23T15:37:09.657Z
Anthony Labarre
<p>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$.</p>

<p>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&gt;0$. This was shown in the following paper:</p>

<p>Irit Dinur, Venkatesan Guruswami, Subhash Khot and Oded Regev.
<a href="http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/hvc-DGKR.pdf">A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover</a>,
SIAM Journal on Computing, 34(5):1129–1146, 2005.</p>

CC BY-SA 3.0
2011-11-23T19:06:51.770Z
Another keyword would be "3-Hitting Set." I don't have access to the following paper now, but the title seems relevant: http://scholar.google.co.uk/scholar?hl=en&q=An+efficient+fixed-parameter+algorithm+for+3-Hitting+Set
Radu GRIGore
CC BY-SA 3.0
2011-11-23T21:57:53.370Z
The approximation threshold is actually $3 - \epsilon$.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-11-24T00:16:50.313Z
@MCH: Reference?
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-24T04:39:33.800Z
@Radu GRIGore:  i believe the link you give is the FPT algorithm mentioned in the answer by Jan Johannsen.  thanks for the help you two.
krumpelstiltskin
CC BY-SA 3.0
2011-11-24T04:41:24.000Z
@TsuyoshiIto: the reference for 3−ϵ is the paper given by Jan.
krumpelstiltskin
CC BY-SA 3.0
2011-11-24T08:56:23.463Z
No, its $2-\epsilon$: for $k$-uniform hypergraph vertex cover, they show hardness of approximation to within $(k-1-\epsilon)$.
Jan Johannsen
CC BY-SA 3.0
2011-11-24T09:04:23.277Z
The paper linked by Radu indeed gives a fixed parameter algorithm for 3-Hitting Set, aka 3-uniform hypergraph vertex cover. An improved algorithm was given in the following paper, for which I don't have a link right now:

H. Fernau. A top-down approach to search-trees: improved algorithmics for 3-Hitting Set. Algorithmica, 57:97–18, 2010.
Jan Johannsen
CC BY-SA 3.0
2011-11-26T03:09:41.467Z
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.
krumpelstiltskin
CC BY-SA 3.0
2011-11-23T16:17:42.987Z
2011-11-23T16:17:42.987Z
Jan Johannsen
<p>I am interested in a SAT variation where the CNF formula is monotone (no variables are negated). Such a formula is obviously satisfiable.</p>

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

<p>MINIMUM TRUE MONOTONE 3SAT</p>

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

<p>Could someone give me some helpful remarks on this problem?</p>

<cc.complexity-theory><np-hardness><sat>
Minimum True Monotone 3SAT
krumpelstiltskin
# Minimum True Monotone 3SAT

(Asked by: username_0 on 2011-11-23)

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?

**Tags:** cc.complexity-theory, np-hardness, sat


---

## 2 answers

### Answer by username_2 on 2011-11-23. Score: 21 | Accepted answer

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](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/hvc-DGKR.pdf),
SIAM Journal on Computing, 34(5):1129–1146, 2005.

> **Comments:**
> **username_3**: Another keyword would be "3-Hitting Set." I don't have access to the following paper now, but the title seems relevant: http://scholar.google.co.uk/scholar?hl=en&q=An+efficient+fixed-parameter+algorithm+for+3-Hitting+Set  
> **username_4**: The approximation threshold is actually $3 - \epsilon$.  
> **username_5**: @MCH: Reference?  
> **username_0**: @username_3:  i believe the link you give is the FPT algorithm mentioned in the answer by username_2.  thanks for the help you two.  
> **username_0**: @TsuyoshiIto: the reference for 3−ϵ is the paper given by Jan.  
> **username_2**: No, its $2-\epsilon$: for $k$-uniform hypergraph vertex cover, they show hardness of approximation to within $(k-1-\epsilon)$.  
> **username_2**: The paper linked by Radu indeed gives a fixed parameter algorithm for 3-Hitting Set, aka 3-uniform hypergraph vertex cover. An improved algorithm was given in the following paper, for which I don't have a link right now:  H. Fernau. A top-down approach to search-trees: improved algorithmics for 3-Hitting Set. Algorithmica, 57:97–18, 2010.  
> **username_0**: 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.  

---

### Answer by username_1 on 2011-11-23. Score: 7

I would start by having a look at papers citing [Downey and Fellows' paper](http://mrfellows.net/papers/DF95_FPTandCompletenessI.pdf), 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"?


---

