Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
复制标题
最大数和精确数问题的参数化复杂性和可核化性
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Magnus Wahlström
中科院分区：
文献类型：
--
作者：
Stefan Kratsch;D. Marx;Magnus Wahlström
对于布尔关系的有限集合Γ，<scp>内斯</scp>（Γ）和<scp>内斯</scp>（Γ）是广义可满足性问题，其中每个约束关系都来自于Γ，任务分别是找到至少/恰好<i>k个</i>变量为1的满意分配。<scp></scp><scp></scp>我们研究这些问题的参数化复杂性，包括他们是否承认多项式核的问题。对于M<scp>ax</scp> O<scp>内斯</scp> SAT（Γ），我们给出了五个不同复杂度的分类：多项式时间可解的，允许多项式核，固定参数易处理的，对于固定<i>k</i>在多项式时间内可解的，以及对于<i>k</i>= 1已经是NP困难的。对于E<scp>xact</scp><scp>内斯</scp> SAT（Γ），我们通过仔细研究固定参数易处理的情况并对E<scp>xact</scp><scp>内斯</scp> SAT（Γ）允许多项式核的集合Γ进行分类来改进先前获得的分类。
For a finite set Γ of Boolean relations, M<scp>ax</scp> O<scp>nes</scp> SAT(Γ) and E<scp>xact</scp> O<scp>nes</scp> SAT(Γ) are generalized satisfiability problems where every constraint relation is from Γ, and the task is to find a satisfying assignment with at least/exactly <i>k</i> variables set to 1, respectively. We study the parameterized complexity of these problems, including the question whether they admit polynomial kernels. For M<scp>ax</scp> O<scp>nes</scp> SAT(Γ), we give a classification into five different complexity levels: polynomial-time solvable, admits a polynomial kernel, fixed-parameter tractable, solvable in polynomial time for fixed <i>k</i>, and NP-hard already for <i>k</i> = 1. For E<scp>xact</scp> O<scp>nes</scp> SAT(Γ), we refine the classification obtained earlier by taking a closer look at the fixed-parameter tractable cases and classifying the sets Γ for which E<scp>xact</scp> O<scp>nes</scp> SAT(Γ) admits a polynomial kernel.