The control complexity of r-Approval: From the single-peaked case to the general case
作者：
Highlights：
• We obtain dichotomy results for r-Approval control problems in k-peaked elections.
• We show that many r-Approval control problems are NP-hard in 2,3-peaked elections.
• We obtain FPT and W-hardness results with respect to the solution size.
• We show that every graph of maximum degree 3 has a special 2-interval representation.
• We develop an FPT-algorithm for a generalization of the r-Set Packing problem.
摘要
•We obtain dichotomy results for r-Approval control problems in k-peaked elections.•We show that many r-Approval control problems are NP-hard in 2,3-peaked elections.•We obtain FPT and W-hardness results with respect to the solution size.•We show that every graph of maximum degree 3 has a special 2-interval representation.•We develop an FPT-algorithm for a generalization of the r-Set Packing problem.
论文关键词：Single-peaked elections,Multipeaked elections,Approval voting,Control,Parameterized complexity
论文评审过程：Received 12 August 2016, Revised 30 April 2017, Accepted 10 June 2017, Available online 21 June 2017, Version of Record 7 August 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.06.004
