The control complexity of r-Approval: from the single-peaked case to the general case

DOI10.1016/J.JCSS.2017.06.004MaRDI QIDQ2402374zbMATH OpenOpenAlexFDO

Authors Yongjie Yang, Jiong Guo

Publication date 7 September 2017

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.4471

zbMATH Keywords

controlparameterized complexityapproval votingmultipeaked electionssingle-peaked elections

Mathematics Subject Classification ID

Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)

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. We show that most NP-hardness results in general elections also hold in k-peaked elections even for $k=2,3$. On the other hand, we derive polynomial-time algorithms for some problems for $k=2$. All our NP-hardness results apply to Approval and sincere-strategy preference-based Approval as well. Our study leads to many dichotomy results for the problems considered in this paper, with respect to the values of $k$ and $r$. In addition, we study $r$-Approval control problems from the viewpoint of parameterized complexity and achieve both fixed-parameter tractability results and W-hardness results, with respect to the solution size. Along the way exploring the complexity of 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 where every 2-interval corresponding to a vertex contains a trivial interval and, moreover, 2-intervals may only intersect at the endpoints of the intervals. Second, we develop a fixed-parameter tractable algorithm for a generalized $r$-Set Packing problem with respect to the solution size, where each element in the given universal set is allowed to occur in more than one r-subset in the solution.

Recommendations

• Parameterized complexity of voter control in multi-peaked elections
• On the complexity of constructive control under nearly single-peaked preferences
• Parameterized complexity of control and bribery for \(d\)-approval elections
• scientific article; zbMATH DE number 6747953
• Parameterized complexity of control and bribery for \(d\)-approval elections

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• An efficient parameterized algorithm for m-set packing
• Anyone but him: the complexity of precluding an alternative
• Are there any nicely structured preference profiles nearby?
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• Complexity of the hamiltonian cycle in regular graph problem
• Computational aspects of nearly single-peaked electorates
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Graph-Theoretic Concepts in Computer Science
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• How hard is it to control an election?
• Iterative Expansion and Color Coding
• Kernelization complexity of possible winner and coalitional manipulation problems in voting
• Large-scale election campaigns: combinatorial shift bribery
• On the complexity of scheduling tasks with discrete starting times
• Parameterized and Exact Computation
• Parameterized complexity of candidate control in elections and related digraph problems
• Parameterized complexity of control problems in Maximin election
• Parameterized computational complexity of control problems in voting systems
• Possible winner problems on partial tournaments: a parameterized study
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• Single-peaked orders on a tree
• Some simplified NP-complete graph problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The complexity of fully proportional representation for single-crossing electorates
• The complexity of manipulative attacks in nearly single-peaked electorates
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control

Cited in

(4)

• Parameterized complexity of voter control in multi-peaked elections
• On the complexity of bribery with distance restrictions
• On the complexity of constructive control under nearly single-peaked preferences
• Structured preferences: a literature survey

This page was built for publication: The control complexity of \(r\)-Approval: from the single-peaked case to the general case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2402374)