I would like to know if the following NP-complete problem has a name and has been studied:

Input: Given a CNF formula $\varphi$ on $n$ variables, a truth assignment $\sigma:[n] \to \{T,F\}$ and an integer $k$;
Question: Can we transform $\sigma$ into a satisfying assignment for $\varphi$, swapping the truth values of at most $k$ pairs of variables.

It is very similar to the problem k-FLIP SAT (see my previous question for details); but here the number of truth values used cannot change.

In particular, I would like to know if there are some results about its parameterized complexity in the general case and under some restrictions (e.g. q-CNF formulas, max occurrences of a variable).

I did a few searches on google, but didn't find anything (but probably I'm not using the correct terms).

  • $\begingroup$ You may want to look at random k-SAT and phase transition litriture and the structure of the space of solutions. $\endgroup$
    – Kaveh
    Mar 4, 2016 at 14:36
  • $\begingroup$ E.g. see the work by Achlioptas and colleagues. If the clause ratio is in the hard section the closest solution to randomly selected assignment is $\Theta(n)$ far if I recall correctly. $\endgroup$
    – Kaveh
    Mar 4, 2016 at 14:38
  • 2
    $\begingroup$ I think it is W[1]-hard by a reduction from the parameterized 2-SAT problem.In this problem we are given a 2-SAT instance, and the goal is to find a satisfying assignment with at most k ones. $\endgroup$ Mar 4, 2016 at 15:21
  • 1
    $\begingroup$ Yes. For a Min-Ones-2-Sat instance, start from the all-0 assignment, add k dummy variables whose truth values do not affect the satisfiability of the formula, and set them to 1. $\endgroup$ Mar 5, 2016 at 13:39
  • $\begingroup$ @IgorShinkar: thanks! Meanwhile I found a W[1]-hardness reduction from independent set (that - I bet - is probably similar to the one used for Min-Ones-2-Sat). If you want convert the comment to an answer (the technique suggested by Serge is ok) but I'll wait to see is someone has a reference/known name for the problem. $\endgroup$ Mar 5, 2016 at 18:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.