NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting
详细信息 查看全文
- 作者：Robert Bredereck robert.bredereck@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author ; Nimrod Talmon ; nimrodtalmon77@gmail.com" class="auth_mail" title="E-mail the corresponding author
- 关键词：Computational complexity ; Computational social choice ; Graph problems ; Manipulating elections ; Approval voting
- 刊名：Information Processing Letters
- 出版年：2016
- 出版时间：February 2016
- 年：2016
- 卷：116
- 期：2
- 页码：147-152
- 全文大小：332 K
文摘
- •
We prove NP-hardness of two generalizations of the EDGE COVER problem.
- •
We resolve two open questions from the literature regarding the complexity of these two generalizations.
- •
We resolve the complexity of three open questions from computational social choice regarding control and bribery for Approval voting.