论文标题
程序规则的组控制：参数化的复杂性和连续域
Group Control for Procedural Rules: Parameterized Complexity and Consecutive Domains
论文作者
论文摘要
我们通过在两个程序规则的群体识别设置中添加个人（GCAI）来考虑群体控制 - 共识启动的尊重规则和自由派的尊重规则。众所周知，对于这两个规则的GCAI都是NP顽强的，但是对于固定参数而言，相对于杰出个体的数量，固定参数是否可以保持开放。我们在肯定中解决两个开放问题。此外，我们通过表明关于自然参数的添加个体的数量，这两个规则的GCAI的数量均为W [2] -HARD，从而增强了GCAI的NP硬度。值得注意的是，即使在一个非常特殊的情况下，个人资格满足所谓的连续财产，即使限制了一个非常特殊的案例，也存在W [2]的hard。但是，对于共识启动的规则，在此特殊情况下，问题成为多项式时间。我们还研究了一个双重限制，其中的个人取消资格符合连续的财产，并表明在这两个规则的限制下，这两种规则都可以解决多项式时间。我们的显示W [2] - hADTES的减少也暗示了有关核化和精确算法的几个下限。
We consider Group Control by Adding Individuals (GCAI) in the setting of group identification for two procedural rules -- the consensus-start-respecting rule and the liberal-start-respecting rule. It is known that GCAI for both rules are NP-hard, but whether they are fixed-parameter tractable with respect to the number of distinguished individuals remained open. We resolve both open problems in the affirmative. In addition, we strengthen the NP-hardness of GCAI by showing that, with respect to the natural parameter the number of added individuals, GCAI for both rules are W[2]-hard. Notably, the W[2]-hardness for the liberal-start-respecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones property. However, for the consensus-start-respecting rule, the problem becomes polynomial-time solvable in this special case. We also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property, and show that under this restriction GCAI for both rules turn out to be polynomial-time solvable. Our reductions for showing W[2]-hardness also imply several lower bounds concerning kernelization and exact algorithms.
