NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting

DOI10.1016/j.ipl.2015.09.008zbMath1346.68101OpenAlexW2152019671WikidataQ62039068 ScholiaQ62039068MaRDI QIDQ894461

Robert Bredereck, Nimrod Talmon

Publication date: 1 December 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.09.008

zbMATH Keywords

computational complexitycomputational social choiceapproval votinggraph problemsmanipulating elections

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Voting theory (91B12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items (1)

Computational complexity characterization of protecting elections from bribery

Cites Work

• Unnamed Item
• Unnamed Item
• Graph factors and factorization: 1985--2003: a survey
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• General factors of graphs
• How hard is it to control an election?
• Swap Bribery
• How Hard Is Bribery in Elections?
• Reducibility among Combinatorial Problems
• Control and Bribery in Voting

This page was built for publication: NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting