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

作者：Bredereck Robert; Talmon Nimrod^*

来源：Information Processing Letters, 2016, 116(2): 147-152.

DOI：10.1016/j.ipl.2015.09.008

• Computational complexity
• Computational social choice
• Graph problems
• Manipulating elections
• Approval voting

Given an undirected graph and an integer q, the EDGE COVER problem asks for a subgraph with at most q edges such that each vertex has degree at least one. We show NP-hardness of two generalizations of the EDGE COVER problem, which were conjectured to be polynomial-time solvable, solving three open questions from computational social choice. Both generalizations introduce weights on the edges and an individual demand b(v) for each vertex v. The first generalization, named SIMPLE b-EDGE WEIGHTED COVER, requires the edge set to have a total weight of at most q while each vertex v is to be adjacent to at least b(v) edges. The second generalization, named SIMPLE WEIGHTED b-EDGE COVER, requires the edge set to contain at most q edges while each vertex v is to be adjacent to edges of total weight at least b(v).

• 出版日期2016-2