标题:Parameterized Complexity of Voter Control in Multi-Peaked Elections
作者:Yang, Yongjie; Guo, Jiong
作者机构:[Yang, Yongjie] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.; [Guo, Jiong] Shandong Univ, Sch Comp Sci & Technol, Jinan, 更多
通讯作者:Yang, YJ;Yang, Yongjie
通讯作者地址:[Yang, YJ]Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.
来源:THEORY OF COMPUTING SYSTEMS
出版年:2018
卷:62
期:8
页码:1798-1825
DOI:10.1007/s00224-018-9843-8
关键词:Condorcet; Copeland; Election control; Maximin; Multi-peaked election; Parameterized complexity; Single-peaked election
摘要:We study the parameterized complexity of voter control problems in -peaked elections, where is a positive integer. In particular, we focus on the constructive/destructive control by adding/deleting votes for Condorcet, Maximin and Copeland. It is known that in general elections all these problems are NP-hard, except for the destructive control by adding/deleting votes for Condorcet which is polynomial-time solvable. We strengthen these results by showing that, when restricted to -peaked elections where =3,4, the above NP-hard problems not only remain NP-hard but also are W[1]-hard with respect to the number of added/deleted votes.
收录类别:EI;SCOPUS;SCIE;SSCI
最新影响因子:0.645
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85040794554&doi=10.1007%2fs00224-018-9843-8&partnerID=40&md5=54469233084cf0830a1700fe401bec76
TOP