论文标题
关于流动民主的参数化复杂性
On Parameterized Complexity of Liquid Democracy
论文作者
论文摘要
在流动民主制度中，每个选民都会投票自己，要么将她的投票委派给其他选民。这引起了所谓的委托图。为了决定最终与他们投票的选民子集一起投票的选民，我们需要解决代表团图中的周期。这引起了解决委托问题，我们需要找到委托图的无环子图，以便他们给出的投票的选民数量在上面是某些整数λ的限制。将选民投票给选民提供的选民人数使系统设计师能够限制任何个人选民的权力。解决方案委托问题已经知道是NP-HARD。在本文中，我们研究了此问题的参数化复杂性。我们表明，关于参数λ，接收器节点的数量和委托图的最大程度，解决方案委托是偏见。我们还表明，即使相对于委托图的树宽，解决方案委托也是w [1] -hard。我们通过在其他一些参数方面表现出FPT算法来补充我们的负面结果。我们最终表明，我们称之为分数委托的相关问题是多项式时间可解决的。
In liquid democracy, each voter either votes herself or delegates her vote to some other voter. This gives rise to what is called a delegation graph. To decide the voters who eventually votes along with the subset of voters whose votes they give, we need to resolve the cycles in the delegation graph. This gives rise to the Resolve Delegation problem where we need to find an acyclic sub-graph of the delegation graph such that the number of voters whose votes they give is bounded above by some integer λ. Putting a cap on the number of voters whose votes a voter gives enable the system designer restrict the power of any individual voter. The Resolve Delegation problem is already known to be NP-hard. In this paper we study the parameterized complexity of this problem. We show that Resolve Delegation is para-NP-hard with respect to parameters λ, number of sink nodes and the maximum degree of the delegation graph. We also show that Resolve Delegation is W[1]-hard even with respect to the treewidth of the delegation graph. We complement our negative results by exhibiting FPT algorithms with respect to some other parameters. We finally show that a related problem, which we call Resolve Fractional Delegation, is polynomial time solvable.
