| 摘要: |
| 给定候选人集合C,投票集合V=(v1,v2,…,vn)和候选人c∈C,是否存在V的子集V′,|V′|≤k,使得c∈r(V＼V′).该问题在不同的得分规则下复杂性是不同的.在plurality规则的基础上证明了Reto规则下Vote Control问题是多项式时间可解的,并给出了k′-approval规则下该问题是NP-Complete的证明. |
| 关键词: Vote Control问题 复杂性 得分规则 |
| DOI： |
| 分类号:TP399 |
| 基金项目:河南省科技攻关项目(122102310442) |
|
| The complexity of Vote Control problem under simple rules |
|
QIN Qin,WANG Xue-rui, LI Jian
|
|
College of Computer Science and Technology, Henan Institute of Engineering,Zhengzhou 450007,China
|
| Abstract: |
| Given a set of candidatesC, a profile of partial votesV=(v1,v2,…,vn), and a distinguished candidatec∈C,is there a subset V′,|V′|≤k such that c∈r(V＼V′). The complexity of this problem is different under different scoring rules. The vote control problem was proved under Reto rule can be solved in polynomial time based on plurality rule, the NP-Complete proof of vote control problem underk′-approval rule was also obtained. |
| Key words: Vote Control problem complexity scoring rule |
