首页|Group control for procedural rules:parameterized complexity and consecutive domains
Group control for procedural rules:parameterized complexity and consecutive domains
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
万方数据
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 algorithmic lower bounds.
group control by adding individualsgroup identificationparameterized complexityconsecutive ones propertyFPTW[2]-hard
Yongjie YANG、Dinko DIMITROV
展开 >
Chair of Economic Theory,Saarland University,Saarbrücken 66123,Germany
Open Access funding enabled and organized by Projekt DEAL
NETL
NSTL
万方数据
