Parameterized complexity of candidate control in elections and related digraph problems
From MaRDI portal
Publication:1040585
DOI10.1016/j.tcs.2009.05.029zbMath1176.68138OpenAlexW2077594988MaRDI QIDQ1040585
Nadja Betzler, Johannes Uhlmann
Publication date: 25 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.029
NP-hardnesscomputational social choiceplurality votingdigraph modification problems\(W\)[1-/\(W\)[2]-hardness]Copeland\(^\alpha \) voting
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
Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity? ⋮ Algorithms for gerrymandering over graphs ⋮ Resolute control: forbidding candidates from winning an election is hard ⋮ Studies in Computational Aspects of Voting ⋮ Optimal defense against election control by deleting voter groups ⋮ The control complexity of \(r\)-Approval: from the single-peaked case to the general case ⋮ Gerrymandering on graphs: computational complexity and parameterized algorithms ⋮ Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems ⋮ Constraint-based electoral districting using a new compactness measure: an application to Portugal ⋮ On the Computational Complexity of Variants of Combinatorial Voter Control in Elections ⋮ Parameterized complexity of control problems in Maximin election ⋮ Is computational complexity a barrier to manipulation? ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Multivariate complexity analysis of Swap Bribery ⋮ Control complexity in Bucklin and fallback voting: a theoretical analysis ⋮ Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections ⋮ Multivariate Complexity Analysis of Swap Bribery ⋮ A parameterized perspective on protecting elections ⋮ On Making a Distinguished Vertex Minimum Degree by Vertex Deletion ⋮ Binary linear programming solutions and non-approximability for control problems in voting systems ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Fixed-parameter algorithms for Kemeny rankings ⋮ Parameterized complexity of voter control in multi-peaked elections ⋮ Controlling sub-tournaments: easy or hard problem? Theoretical vs. practical analysis ⋮ Combinatorial voter control in elections
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for the coalitional manipulation problem
- Graphs, networks and algorithms
- 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\)]
- The computational difficulty of manipulating an election
- On complexity of lobbying in multiple referenda
- Parametrized complexity theory.
- Fixed-Parameter Algorithms for Kemeny Scores
- Copeland Voting Fully Resists Constructive Control
- Parameterized Computational Complexity of Dodgson and Young Elections
- When are elections with few candidates hard to manipulate?
- Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- How Hard Is Bribery in Elections?
- A Richer Understanding of the Complexity of Election Systems
- On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time
- A Short Introduction to Computational Social Choice
- Digraphs
