A Multistage View on 2-Satisfiability

A Multistage View on 2-Satisfiability
复制标题

DOI：
10.1007/978-3-030-75242-2_16
复制
发表时间：
2020-11
期刊：
ArXiv
影响因子：
--
通讯作者：
T. Fluschnik
T. Fluschnik
中科院分区：
其他
文献类型：
--
作者：
T. Fluschnik

文献摘要

相似文献

我们研究了多阶段模型中的q-SAT问题，重点研究了线性时间可解的2-SAT问题。在这里，给定一个q-CNF公式序列和一个非负整数d，问题是是否存在一个满足真值赋值的序列，使得对于每两个连续的真值赋值，其值改变的变量的数量至多为d。我们证明了即使在非常有限的情况下，多阶段2-SAT也是困难的。此外，我们还提出了多阶段2-SAT的参数化算法（包括核化），并证明它们是渐进最优的。
We studyq-SATin the multistage model, focusing on the linear-time solvable 2-SAT. Herein, given a sequence ofq-CNF formulas and a non-negative integerd, 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 mostd. We prove thatMultistage 2-SATis-hard even in quite restricted cases. Moreover, we present parameterized algorithms (including kernelization) forMultistage 2-SATand prove them to be asymptotically optimal.