Manipulating Districts to Win Elections: Fine-Grained
\nComplexity

Eduard Eiben, Fedor V. Fomin, Fahad Panolan, Kirill SimonovResearch 2020

Abstract

Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political
\nadvantage for a particular party. Lewenberg, Lev, and Rosenschein [AAMAS 2017] initiated the algorithmic
\nstudy of a geographically-based manipulation problem, where voters must vote at the ballot box closest to them.
\nIn this variant of gerrymandering, for a given set of possible locations of ballot boxes and known political preferences of n voters, the task is to identify locations for k boxes out of m possible locations to guarantee victory
\nof a certain party in at least ` districts. Here integers k and ` are some selected parameter.
\nIt is known that the problem is NP-complete already for 4 political parties and prior to our work only heuristic
\nalgorithms for this problem were developed. We initiate the rigorous study of the gerrymandering problem from
\nthe perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and
\nupper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by k + n
\nand that it does not admit an f(n, k)·mo(
\n√
\nk)
\nalgorithm for any function f of k and n only, unless the Exponential
\nTime Hypothesis (ETH) fails. Our lower bounds hold already for 2 parties. On the other hand, we give an
\nalgorithm that solves the problem for a constant number of parties in time (m + n)
\nO(
\n√
\nk)
\n.
BibTeX
@inproceedings{eiben2020manipulating,
  author = {Eduard Eiben and Fedor V. Fomin and Fahad Panolan and Kirill Simonov},
  title = {{Manipulating Districts to Win Elections: Fine-Grained\&\#13;\textbackslash\{\}nComplexity}},
  booktitle = {Research},
  year = {2020},
}

Loading related content...

Figure