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

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

<p>It is very similar to the problem k-FLIP SAT (see <a href="https://cstheory.stackexchange.com/q/33604/3247">my previous question</a> for details); but here the number of truth values used cannot change.</p>

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

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

CC BY-SA 3.0
2016-03-04T14:36:00.617Z
You may want to look at random k-SAT and phase transition litriture and the structure of the space of solutions.
Kaveh
CC BY-SA 3.0
2016-03-04T14:38:34.520Z
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.
Kaveh
CC BY-SA 3.0
2016-03-04T15:21:48.630Z
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.
Igor Shinkar
CC BY-SA 3.0
2016-03-05T13:39:28.180Z
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.
Serge Gaspers
CC BY-SA 3.0
2016-03-05T18:50:53.227Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2018-02-27T23:34:26.733Z
@Serge Gaspers isn’t Min-Ones 2-SAT FPT by local search? I agree with Marzio De Biasi that the problem asked about is W[1]-hard (by reduction from Clique or Independent Set) though.
daniello
CC BY-SA 3.0
2018-03-01T12:38:23.367Z
@daniello: I agree. Sorry for the oversight. One can reduce from Min-Ones-Sat instead, which is W[2]-hard.
Serge Gaspers
<reference-request><sat><parameterized-complexity>
"k-Swap SAT" problem
Marzio De Biasi
# "k-Swap SAT" problem

(Asked by: username_0 on 2016-03-04)

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](https://cstheory.stackexchange.com/q/33604/3247) 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).

**Tags:** reference-request, sat, parameterized-complexity

> **Comments:**
> **username_1**: You may want to look at random k-SAT and phase transition litriture and the structure of the space of solutions.  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: @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.  
> **username_4**: @username_3 isn’t Min-Ones 2-SAT FPT by local search? I agree with username_0 that the problem asked about is W[1]-hard (by reduction from Clique or Independent Set) though.  
> **username_3**: @username_4: I agree. Sorry for the oversight. One can reduce from Min-Ones-Sat instead, which is W[2]-hard.  

---

## 0 answers

