# Positive 1-in-3 SAT FPT or Fixed Parameter Intractable

There are a number of satisfiability problems that are difficult to solve even in the fixed parameter sense. For example, Weighted q-CNF Satisfiability is W-complete when parameterized by the number of variables that are set to true.

My question is: is there any literature on whether Positive 1-in-3 is W-hard or fixed parameter tractable when parameterized by the number of variables that are set to true? Positive 1-in-3 SAT is the problem where all literals in an expression are positive and exactly one literal in each clause is true.

## 1 Answer

No, since even the generalization to 1-in-at-most-3 is FPT for the same reason as vertex cover.
(With at most 3 variables per clause, there will be at most 3 cases for each step.)

I feel like that generalization should have a simple
poly-size kernel, but can't figure out any way of showing that.

The corresponding problem for at-most-1-in-3 constraints, where one wants
exactly k variables to be true, is W-hard by reduction from independent set:

If k<2 then brute force, else:
There's a variable for each vertex and one other variable.
The constraints are ​ u , other_variable , v ​ for edges u,v.
Since 2≤k and other_variable is in every constraint, other_variable must be false, so
the satisfying assignments with exactly k Trues correspond to the independent k-sets.

• If the bounded search tree method works for the 1-in-at-most-3 case, why doesn't it also work for the Weighted q-CNF SAT problem for when $q = 3$? Given that there is $3$ literals in a clause, couldn't the condition be pick one of the three literals to set true or pick no literals at all? Unlike vertex cover, you still have to find ${n \choose k}$ combinations of clauses each of which contains one literal which is true. – user1246462 Sep 4 '16 at 17:46
• Setting a literal to true does not necessarily set its variable to the limited value, so it can easily be the case that much more than k choices are needed. ​ Why do you "still have to find" that many "combinations of clauses"? ​ ​ ​ ​ – user6973 Sep 4 '16 at 18:59
• I see. Both are nice generalizations of the problem, although I've cleared up my problem statement now to ask about the Positive 1-in-3 SAT exact case that was the original intent of the question. – user1246462 Sep 4 '16 at 20:05
• (The acceptance may indicate that you already realize this, but: ​ Note that your problem is no harder than for 1-in-at-most-3 constraints, so your problem is also FPT.) ​ ​ ​ ​ – user6973 Sep 4 '16 at 20:11