Group control for procedural rules: parameterized complexity and consecutive domains

Abstract

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 -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 -hardness of GCAI by showing that, with respect to the natural parameter the number of added individuals, GCAI for both rules are -hard. Notably, the -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 -hardness also imply several algorithmic lower bounds.