Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems

DOI10.1007/978-3-540-85097-7_5MaRDI QIDQ5505642zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Parameterized complexity of control problems in Maximin election
• Elections with few voters: candidate control can be easy
• Parameterized computational complexity of control problems in voting systems
• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
• Parameterized complexity of control and bribery for \(d\)-approval elections

Cites work

• Anyone but him: the complexity of precluding an alternative
• Copeland Voting Fully Resists Constructive Control
• How hard is it to control an election?
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• On complexity of lobbying in multiple referenda
• Threshold dominating sets and an improved characterization of \(W[2]\)
• When are elections with few candidates hard to manipulate?

Cited in

(13)

• Parameterized computational complexity of control problems in voting systems
• Resolute control: forbidding candidates from winning an election is hard
• Parameterized complexity of control and bribery for \(d\)-approval elections
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Parameterized complexity of control and bribery for \(d\)-approval elections
• On making a distinguished vertex minimum degree by vertex deletion
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• The complexity of priced control in elections
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• Parameterized Computational Complexity of Dodgson and Young Elections
• Normalized range voting broadly resists control
• Elections with few voters: candidate control can be easy
• Parameterized complexity of control problems in Maximin election

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

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