Group control for procedural rules:parameterized complexity and consecutive domains  

作　　者：Yongjie YANG Dinko DIMITROV 

机构地区：[1]Chair of Economic Theory,Saarland University,Saarbrücken 66123,Germany

出　　处：《Frontiers of Computer Science》2024年第3期133-141,共9页中国计算机科学前沿（英文版）

摘　　要：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-startrespecting 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-startrespecting 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 algorithmic lowerbounds.

关 键 词：group control by adding individuals group identification parameterized complexity consecutive ones property FPT -hard 

分 类 号：O157.5[理学—数学]