1
$\begingroup$

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[1]-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[1]-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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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[1]-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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user1246462
    Commented Sep 4, 2016 at 17:46
  • $\begingroup$ 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"? ​ ​ ​ ​ $\endgroup$
    – user6973
    Commented Sep 4, 2016 at 18:59
  • $\begingroup$ 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. $\endgroup$
    – user1246462
    Commented Sep 4, 2016 at 20:05
  • $\begingroup$ (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.) ​ ​ ​ ​ $\endgroup$
    – user6973
    Commented Sep 4, 2016 at 20:11

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.