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 {\lambda}. 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 {\lambda}, 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.
翻译:在液态民主中,每个选民要么自己投票,要么将自己的选票委托给其他选民。这产生了一个称为代表团图的图表。为了决定最终投票的选民以及他们投票的一组选民,我们需要在代表团图中解决周期问题。这产生了解决代表团问题,我们需要在代表团图中找到一个循环的子图,这样,他们投票的选民人数就受到某种整数的 lambda 的制约。对选民投票使系统设计者能够限制任何个人选民权力的选民人数设定一个上限。解决代表团的问题已经众所周知是NP-硬的。我们在这份文件中研究这一问题的参数复杂性。我们表明,解决代表团对于参数 lambda 、 汇点数和代表团图的最大程度来说,是PNP 硬的。我们还表明,即使代表团的票数与代表团图的树枝节有关,但解代表团的票数也是W[1]硬的。我们用其他参数来补充我们的负面结果,我们用FPT算法来显示其他参数。我们最后展示了一个相关的代表团。我们决心是巨大的问题。