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$ 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$ 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$ 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$ Commented Sep 4, 2016 at 20:11

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.