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

DOI10.1016/J.IPL.2015.09.008MaRDI QIDQ894461zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Recommendations

• Algorithms - ESA 2003
• The minimum generalized vertex cover problem
• Elections with few candidates: prices, weights, and covering problems
• The maximum vertex coverage problem on bipartite graphs
• FPTAS for counting weighted edge covers

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Control and bribery in voting
• General factors of graphs
• Graph factors and factorization: 1985--2003: a survey
• How hard is bribery in elections?
• How hard is it to control an election?
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• Reducibility among combinatorial problems
• Swap bribery

Cited in

(1)

• Computational complexity characterization of protecting elections from bribery

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

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