<p>The problem does not have a polynomial kernel unless NP is in coNP/poly. The cross-composition technique from our paper applies in a nontrivial way.</p>

<p>Let me show how the classic Vertex Cover problem OR-cross-composes into the k-FLIP-SAT problem; by the results in the cited paper, this is sufficient. Concretely, we build a polynomial-time algorithm whose input is a sequence of Vertex Cover instances $(G_1,k), (G_2, k), \ldots, (G_t, k)$ that all share the same value of $k$ and all have exactly $n$ vertices. The output is an instance of $k$-FLIP SAT with a parameter value of $O(k + \log t)$, which is sufficiently small for a cross-composition, such that the $k$-FLIP SAT instance has answer yes iff one of the input graphs has a vertex cover of size $k$. By duplicating one input (which does not change the value of the OR) we can ensure that the number of inputs $t$ is a power of two.</p>

<p>The composition proceeds as follows. Number the vertices in graph each input graph $G_i$ as $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$. Make a corresponding variable in the FLIP-SAT instance for each vertex of each input graph. Additionally, make a selector variable $u_i$ for each input instance number $i \in [t]$. For each input graph $G_i$, we add some clauses to the formula. For each edge $\{v_{i,x}, v_{i,y}\}$ of graph $G_i$, add the clause $(v_{i,x} \vee v_{i,y} \vee \neg u_i)$ to the formula, which will encode "either one of the endpoints of this edge is set to true, or the instance $i$ is not active". In the initial assignment, all vertex-variables are set to false and all selector variables $u_i$ are set to false, so that these clauses are all satisfied. To build the OR-behavior into the composition we will augment the formula to ensure that a satisfying assignment sets at least one selector to true, and must then also form a vertex cover of the selected graph.</p>

<p>To make sure we can do this selection while keeping the flip distance small compared to the number of inputs $t$, we use the structure of a complete binary tree with $t$ leaves, which has height $\log t$. Number the leaves from $1$ to $t$ and associate the $i$-th leaf with the variable $u_i$ that controls if input $i$ is active or not. Create a new variable for each internal node of the binary tree. For each internal node, let its corresponding variable be $x$ and the variables of its two children be $y$ and $z$. Add the clause $(\neg x \vee y \vee z)$ to the formula which captures the implication $(x \rightarrow (y \vee z))$, enforcing that $x$ can only be true if one of its children is true. To complete the formula, add a singleton clause saying that the variable of the root node of the binary tree must be true. In the initial truth assignment, the values of all variables for internal nodes is set to false, which satisfies all clauses of the formula except for the singleton clause requiring the root node of the tree to have its variable true.</p>

<p>This completes the description of the formula and truth assignment. Set the parameter $k'$ of the FLIP DISTANCE problem to be equal to $(k + \log t + 1)$, which is suitably bounded for a cross-composition. It remains to show that we can flip $k'$ variables to make the formula true iff some input graph $G_i$ has a vertex cover of size $k$.</p>

<p>In the reverse direction, suppose that $G_i$ has a size-$k$ vertex cover. Set the $k$ variables corresponding to the $k$ vertices in the cover to true by flipping them. Set the selector variable $u_i$ to true to encode that input $i$ is activated, and flip the variables of the $\log t$ internal binary tree nodes on the path of leaf $i$ to the root to true. It is easy to verify that this is a satisfying assignment: the implications in the binary tree are all satisfied, the root node's value is set to true, the clauses that check edges of $G_{i'}$ for $i' \neq i$ remain satisfied because $u_{i'}$ remains false, while the clauses for graph $G_i$ are satisfied because for every edge we set at least one endpoint to true.</p>

<p>For the forward direction, suppose that the formula can be satisfied by flipping at most $k + \log t + 1$ variables. Then we must flip the variable of the root node to true. The implications in the binary tree enforce that at least one selector variable of a leaf is set to true, say $u_i$. To satisfy the implications encoded in the binary tree, all internal nodes on the path from $u_i$ to the root were set to true, accounting for $1 + \log t$ flips. Since $u_i$ is set to true, the clauses made for graph $G_i$ are not satisfied on the literal $\neg u_i$, so they are satisfied because one of the endpoints of each edge of $G_i$ is set to true. Since at least $1 + \log t$ variables of the binary tree were flipped, at most $k$ vertex-variables are flipped to true in this solution. This encodes a vertex cover of size $k$ in $G_i$ and proves that one of the inputs is a YES-instance. This completes the proof.</p>

CC BY-SA 3.0
2016-01-20T19:58:36.817Z
Thanks!!! (I immediately removed the "et al." from the reference ;-). Nice proof (IMO you should publish it in a paper).
Marzio De Biasi
CC BY-SA 3.0
2016-01-20T12:18:55.020Z
2016-01-20T12:18:55.020Z
Bart Jansen
<p>The k-FLIP SAT parametrized problem is defined as:</p>

<p><strong>Input:</strong> a 3-CNF formula $\varphi$ with $n$ variables and a truth assignment $\sigma : [n] \to \{0,1\}$<br>
<strong>Parameter:</strong> $k$<br>
<strong>Question:</strong> can we transform the assignment $\sigma$ into a satifying assignment $\sigma'$ for $\varphi$ <em>flipping</em> the truth value of at most $k$ variables? </p>

<p>The problem is <strike>clearly</strike> in FPT (<a href="http://dx.doi.org/10.1016/j.disopt.2010.07.003" rel="nofollow">Stefan Szeider: The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Discrete Optimization 8(1): 139-145 (2011)</a>) </p>

<blockquote>
  <p>Does it admit a polynomial kernel ? (under reasonable complexity assumptions)</p>
</blockquote>

<p>The recent cross-composition techniques (see <a href="http://arxiv.org/abs/1206.5941" rel="nofollow">Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch, "Kernelization Lower Bounds By Cross-Composition"</a>) seem unuseful for this problem. And they also seem unuseful for similar problems that ask if a given solution to an NP-hard problem can be found from a given instance by local search (limiting the search to the neighbours of the given instance, under some natural distance measure).</p>

CC BY-SA 3.0
2016-01-21T05:59:35.200Z
Cool, but why is this problem clearly FPT? If you make it 2-CNF with exactly k variable flips instead of at most, then I believe the problem is fpt-equivalent to k-clique. I've been working on a paper that includes some results on exact-k-flip problems.
Michael Wehar
CC BY-SA 3.0
2016-01-21T07:54:22.867Z
I think that saying it's in FPT means that it's solvable in $f(k) \cdot n^{O(1)}$ time.
Michael Wehar
CC BY-SA 3.0
2016-01-21T07:57:55.840Z
I think that saying it's in XP means that it's solvable in $n^{f(k)}$ time.
Michael Wehar
CC BY-SA 3.0
2016-01-21T08:03:15.923Z
I don't know the relationship between the exact-k-flip problem and the atmost-k-flip problem.  I initially thought that you were saying the atmost-k-flip problem is easier in the sense that atmost-k-flip is FPT.  I say easier because exact-k-flip can't be FPT unless ETH is false.  The reason for this is because it is equivalent to k-clique and it's known that $f(k) \cdot n^{O(1)}$ time algorithms for k-clique imply ETH is false.
Michael Wehar
CC BY-SA 3.0
2016-01-21T08:17:01.080Z
@MichaelWehar: ops, you're right (I delete the wrong fool comment), the question needs to be polished (I defined the problem as "at-most k FLIPS"). ASAP I'll take a look to the paper(s) (one of them should be Stefan Szeider, "The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT") in which it is said that k-FLIP SAT is FPT for clauses with bounded-size.
Marzio De Biasi
CC BY-SA 3.0
2016-01-21T08:18:08.650Z
Cool!  Let me take a look.  :)
Michael Wehar
CC BY-SA 3.0
2016-01-21T08:24:52.500Z
It seems that you are right!  The paper does claim that 2-CNF atmost-k-flip is FPT (Theorem 4).  But, as I said, if 2-CNF exact-k-flip were FPT, then ETH would be false.
Michael Wehar
CC BY-SA 3.0
2016-01-21T08:33:38.150Z
This seems strange.  I must have made a mistake or overlooked something.  Let me go through this again and take a look back here tomorrow.  :)
Michael Wehar
CC BY-SA 3.0
2016-01-21T08:36:51.400Z
@MichaelWehar: I'll dig into it, too. Very informally the "at-most" version restricts the local search to a "sphere" the "exact" version restricts the local search to the "surface" of the "sphere" :-)
Marzio De Biasi
CC BY-SA 3.0
2016-01-21T13:57:22.000Z
The "at-most version" is indeed strictly easier, here's an FPT algorithm. If all clauses are satisfied, output YES. If some clause is false and k = 0, output NO. Otherwise, pick an unsatisfied clause. To satisfy it, at least 1 of its 3 variables has to be flipped. For each of its 3 literals, recurse on the instance where the variable of that literal is flipped and decrease k by one. You get a search tree of size $O(3^k)$. The work done in each node is polynomial; we get an FPT algorithm. This fails for "exactly k": if all clauses are satisfied but k > 0 you have to flip a variable anyway.
Bart Jansen
CC BY-SA 3.0
2016-01-22T18:24:38.770Z
@BartJansen You're right!  Great!  So it seems that atmost-k-flip is FPT, exact-k-flip is w[1]-complete, and atleast-k-flip is NP-complete for every fixed k.
Michael Wehar
<parameterized-complexity><fixed-parameter-tractable>
Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas
Marzio De Biasi
# Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas

(Asked by: username_0 on 2016-01-19)

The k-FLIP SAT parametrized problem is defined as:

**Input:** a 3-CNF formula $\varphi$ with $n$ variables and a truth assignment $\sigma : [n] \to \{0,1\}$  
**Parameter:** $k$  
**Question:** can we transform the assignment $\sigma$ into a satifying assignment $\sigma'$ for $\varphi$ *flipping* the truth value of at most $k$ variables?

The problem is clearly in FPT ([Stefan Szeider: The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Discrete Optimization 8(1): 139-145 (2011)](http://dx.doi.org/10.1016/j.disopt.2010.07.003))

> Does it admit a polynomial kernel ? (under reasonable complexity assumptions)

The recent cross-composition techniques (see [Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch, "Kernelization Lower Bounds By Cross-Composition"](http://arxiv.org/abs/1206.5941)) seem unuseful for this problem. And they also seem unuseful for similar problems that ask if a given solution to an NP-hard problem can be found from a given instance by local search (limiting the search to the neighbours of the given instance, under some natural distance measure).

**Tags:** parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: Cool, but why is this problem clearly FPT? If you make it 2-CNF with exactly k variable flips instead of at most, then I believe the problem is fpt-equivalent to k-clique. I've been working on a paper that includes some results on exact-k-flip problems.  
> **username_1**: I think that saying it's in FPT means that it's solvable in $f(k) \cdot n^{O(1)}$ time.  
> **username_1**: I think that saying it's in XP means that it's solvable in $n^{f(k)}$ time.  
> **username_1**: I don't know the relationship between the exact-k-flip problem and the atmost-k-flip problem.  I initially thought that you were saying the atmost-k-flip problem is easier in the sense that atmost-k-flip is FPT.  I say easier because exact-k-flip can't be FPT unless ETH is false.  The reason for this is because it is equivalent to k-clique and it's known that $f(k) \cdot n^{O(1)}$ time algorithms for k-clique imply ETH is false.  
> **username_0**: @MichaelWehar: ops, you're right (I delete the wrong fool comment), the question needs to be polished (I defined the problem as "at-most k FLIPS"). ASAP I'll take a look to the paper(s) (one of them should be Stefan Szeider, "The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT") in which it is said that k-FLIP SAT is FPT for clauses with bounded-size.  
> **username_1**: Cool!  Let me take a look.  :)  
> **username_1**: It seems that you are right!  The paper does claim that 2-CNF atmost-k-flip is FPT (Theorem 4).  But, as I said, if 2-CNF exact-k-flip were FPT, then ETH would be false.  
> **username_1**: This seems strange.  I must have made a mistake or overlooked something.  Let me go through this again and take a look back here tomorrow.  :)  
> **username_0**: @MichaelWehar: I'll dig into it, too. Very informally the "at-most" version restricts the local search to a "sphere" the "exact" version restricts the local search to the "surface" of the "sphere" :-)  
> **username_2**: The "at-most version" is indeed strictly easier, here's an FPT algorithm. If all clauses are satisfied, output YES. If some clause is false and k = 0, output NO. Otherwise, pick an unsatisfied clause. To satisfy it, at least 1 of its 3 variables has to be flipped. For each of its 3 literals, recurse on the instance where the variable of that literal is flipped and decrease k by one. You get a search tree of size $O(3^k)$. The work done in each node is polynomial; we get an FPT algorithm. This fails for "exactly k": if all clauses are satisfied but k > 0 you have to flip a variable anyway.  
> **username_1**: @BartJansen You're right!  Great!  So it seems that atmost-k-flip is FPT, exact-k-flip is w[1]-complete, and atleast-k-flip is NP-complete for every fixed k.  

---

## 1 answers

### Answer by username_2 on 2016-01-20. Score: 13 | Accepted answer

The problem does not have a polynomial kernel unless NP is in coNP/poly. The cross-composition technique from our paper applies in a nontrivial way.

Let me show how the classic Vertex Cover problem OR-cross-composes into the k-FLIP-SAT problem; by the results in the cited paper, this is sufficient. Concretely, we build a polynomial-time algorithm whose input is a sequence of Vertex Cover instances $(G\_1,k), (G\_2, k), \ldots, (G\_t, k)$ that all share the same value of $k$ and all have exactly $n$ vertices. The output is an instance of $k$-FLIP SAT with a parameter value of $O(k + \log t)$, which is sufficiently small for a cross-composition, such that the $k$-FLIP SAT instance has answer yes iff one of the input graphs has a vertex cover of size $k$. By duplicating one input (which does not change the value of the OR) we can ensure that the number of inputs $t$ is a power of two.

The composition proceeds as follows. Number the vertices in graph each input graph $G\_i$ as $v\_{i,1}, v\_{i,2}, \ldots, v\_{i,n}$. Make a corresponding variable in the FLIP-SAT instance for each vertex of each input graph. Additionally, make a selector variable $u\_i$ for each input instance number $i \in [t]$. For each input graph $G\_i$, we add some clauses to the formula. For each edge $\{v\_{i,x}, v\_{i,y}\}$ of graph $G\_i$, add the clause $(v\_{i,x} \vee v\_{i,y} \vee \neg u\_i)$ to the formula, which will encode "either one of the endpoints of this edge is set to true, or the instance $i$ is not active". In the initial assignment, all vertex-variables are set to false and all selector variables $u\_i$ are set to false, so that these clauses are all satisfied. To build the OR-behavior into the composition we will augment the formula to ensure that a satisfying assignment sets at least one selector to true, and must then also form a vertex cover of the selected graph.

To make sure we can do this selection while keeping the flip distance small compared to the number of inputs $t$, we use the structure of a complete binary tree with $t$ leaves, which has height $\log t$. Number the leaves from $1$ to $t$ and associate the $i$-th leaf with the variable $u\_i$ that controls if input $i$ is active or not. Create a new variable for each internal node of the binary tree. For each internal node, let its corresponding variable be $x$ and the variables of its two children be $y$ and $z$. Add the clause $(\neg x \vee y \vee z)$ to the formula which captures the implication $(x \rightarrow (y \vee z))$, enforcing that $x$ can only be true if one of its children is true. To complete the formula, add a singleton clause saying that the variable of the root node of the binary tree must be true. In the initial truth assignment, the values of all variables for internal nodes is set to false, which satisfies all clauses of the formula except for the singleton clause requiring the root node of the tree to have its variable true.

This completes the description of the formula and truth assignment. Set the parameter $k'$ of the FLIP DISTANCE problem to be equal to $(k + \log t + 1)$, which is suitably bounded for a cross-composition. It remains to show that we can flip $k'$ variables to make the formula true iff some input graph $G\_i$ has a vertex cover of size $k$.

In the reverse direction, suppose that $G\_i$ has a size-$k$ vertex cover. Set the $k$ variables corresponding to the $k$ vertices in the cover to true by flipping them. Set the selector variable $u\_i$ to true to encode that input $i$ is activated, and flip the variables of the $\log t$ internal binary tree nodes on the path of leaf $i$ to the root to true. It is easy to verify that this is a satisfying assignment: the implications in the binary tree are all satisfied, the root node's value is set to true, the clauses that check edges of $G\_{i'}$ for $i' \neq i$ remain satisfied because $u\_{i'}$ remains false, while the clauses for graph $G\_i$ are satisfied because for every edge we set at least one endpoint to true.

For the forward direction, suppose that the formula can be satisfied by flipping at most $k + \log t + 1$ variables. Then we must flip the variable of the root node to true. The implications in the binary tree enforce that at least one selector variable of a leaf is set to true, say $u\_i$. To satisfy the implications encoded in the binary tree, all internal nodes on the path from $u\_i$ to the root were set to true, accounting for $1 + \log t$ flips. Since $u\_i$ is set to true, the clauses made for graph $G\_i$ are not satisfied on the literal $\neg u\_i$, so they are satisfied because one of the endpoints of each edge of $G\_i$ is set to true. Since at least $1 + \log t$ variables of the binary tree were flipped, at most $k$ vertex-variables are flipped to true in this solution. This encodes a vertex cover of size $k$ in $G\_i$ and proves that one of the inputs is a YES-instance. This completes the proof.

> **Comments:**
> **username_0**: Thanks!!! (I immediately removed the "et al." from the reference ;-). Nice proof (IMO you should publish it in a paper).  

---

