Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On Parameterized Complexity of Liquid Democracy   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.

15
The categories of this paper are: nucl-ex
20
The categories of this paper are: acc-phys
7
The categories of this paper are: hep-th
16
The categories of this paper are: stat
33
The categories of this paper are: plasm-ph
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
36
The categories of this paper are: cmp-lg
5
The categories of this paper are: gr-qc
21
The categories of this paper are: adap-org
26
The categories of this paper are: bayes-an
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
17
The categories of this paper are: q-fin
30
The categories of this paper are: q-alg
4
The categories of this paper are: cond-mat