Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems

DOI10.1007/978-3-540-85097-7_5zbMath1168.68440OpenAlexW2167625605MaRDI QIDQ5505642

Nadja Betzler, Johannes Uhlmann

Publication date: 27 January 2009

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85097-7_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control ⋮ The complexity of priced control in elections ⋮ Normalized range voting broadly resists control ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control ⋮ Parameterized computational complexity of control problems in voting systems

Cites Work

• Unnamed Item
• Anyone but him: the complexity of precluding an alternative
• How hard is it to control an election?
• Threshold dominating sets and an improved characterization of \(W[2\)]
• On complexity of lobbying in multiple referenda
• Copeland Voting Fully Resists Constructive Control
• When are elections with few candidates hard to manipulate?
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control

This page was built for publication: Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems