Parameterized complexity of candidate control in elections and related digraph problems

There are different ways for an external agent to influence the outcome of an election. We concentrate on “control” by adding or deleting candidates. Our main focus is to investigate the parameterized complexity of various control problems for different voting systems. To this end, we introduce natural digraph problems that may be of independent interest. They help in determining the parameterized complexity of control for different voting systems including Llull, Copeland, and plurality voting. Devising several parameterized reductions, we provide an overview of the parameterized complexity of the digraph and control problems with respect to natural parameters such as adding/deleting only a bounded number of candidates or having only few voters.