# "k-Swap SAT" problem

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).

• You may want to look at random k-SAT and phase transition litriture and the structure of the space of solutions. Mar 4, 2016 at 14:36
• 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. Mar 4, 2016 at 14:38
• 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. Mar 4, 2016 at 15:21
• 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. Mar 5, 2016 at 13:39
• @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. Mar 5, 2016 at 18:50