Article ID Journal Published Year Pages File Type
4951215 Journal of Computer and System Sciences 2017 18 Pages PDF
Abstract
We investigate the complexity of r-Approval control problems in k-peaked elections, where at most k peaks are allowed in each vote with respect to an order of the candidates. Our study leads to many dichotomy results with respect to the values of k and r. All our NP-completeness results apply to Approval and sincere-strategy preference-based Approval as well. In addition, we study r-Approval control problems from the viewpoint of parameterized complexity and achieve both fixed-parameter tractability results and W[1]-hardness results, with respect to the solution size. Along the way exploring the control problems, we obtain two byproducts which are of independent interest. First, we prove that every graph of maximum degree 3 admits a specific 2-interval representation. Second, we develop a fixed-parameter tractable algorithm for a generalized r-Set Packing problem.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,