A Multistage View on 2-Satisfiability
share
We study q-SAT in the multistage model, focusing on the linear-time solvable 2-SAT. Herein, given a sequence of q-CNF fomulas and a non-negative integer d, the question is whether there is a sequence of satisfying truth assignments such that for every two consecutive truth assignments, the number of variables whose values changed is at most d. We prove that Multistage 2-SAT is NP-hard even in quite restricted cases. Moreover, we present parameterized algorithms (including kernelization) for Multistage 2-SAT and prove them to be asymptotically optimal.
READ FULL TEXT