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

DOI10.1016/J.IPL.2015.09.008zbMATH Open1346.68101OpenAlexW2152019671WikidataQ62039068 ScholiaQ62039068MaRDI QIDQ894461FDOQ894461

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

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

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)

Cites Work

• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Title not available (Why is that?)
• General factors of graphs
• How hard is it to control an election?
• Swap bribery
• How hard is bribery in elections?
• Control and bribery in voting
• Graph factors and factorization: 1985--2003: a survey
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard

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)