The control complexity of \(r\)-Approval: from the single-peaked case to the general case
From MaRDI portal
Publication:2402374
DOI10.1016/j.jcss.2017.06.004zbMath1372.68149arXiv1304.4471OpenAlexW2666826464MaRDI QIDQ2402374
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
Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)
Related Items (max. 100)
On the complexity of bribery with distance restrictions ⋮ Parameterized complexity of voter control in multi-peaked elections ⋮ Structured preferences: a literature survey
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- Parameterized complexity of control problems in Maximin election
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Anyone but him: the complexity of precluding an alternative
- Parameterized computational complexity of control problems in voting systems
- Parameterized complexity of candidate control in elections and related digraph problems
- Single-peaked orders on a tree
- On the complexity of scheduling tasks with discrete starting times
- How hard is it to control an election?
- Some simplified NP-complete graph problems
- Complexity of the hamiltonian cycle in regular graph problem
- Control complexity in Bucklin and fallback voting: a theoretical analysis
- Possible winner problems on partial tournaments: a parameterized study
- The complexity of fully proportional representation for single-crossing electorates
- Are there any nicely structured preference profiles nearby?
- Large-Scale Election Campaigns: Combinatorial Shift Bribery
- Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
- Computational Aspects of Nearly Single-Peaked Electorates
- Iterative Expansion and Color Coding
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- An efficient parameterized algorithm for m-set packing
- Parameterized and Exact Computation
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: The control complexity of \(r\)-Approval: from the single-peaked case to the general case
