Manipulating Districts to Win Elections: Fine-Grained Complexity

Eibe, Eduard and Fomin, Fedor V and Panolan, Fahad and et al, . (2020) Manipulating Districts to Win Elections: Fine-Grained Complexity.


Download (444kB) | Preview


Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AAMAS 2017] initiated the algorithmic study of a geographically-based manipulation problem, where voters must vote at the ballot box closest to them. In 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 of a certain party in at least ` districts. Here integers k and ` are some selected parameter. It is known that the problem is NP-complete already for 4 political parties and prior to our work only heuristic algorithms for this problem were developed. We initiate the rigorous study of the gerrymandering problem from the perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and upper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by k + n and that it does not admit an f(n, k)·mo( √ k) algorithm for any function f of k and n only, unless the Exponential Time Hypothesis (ETH) fails. Our lower bounds hold already for 2 parties. On the other hand, we give an algorithm that solves the problem for a constant number of parties in time (m + n) O( √ k) .

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Article
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 24 Feb 2020 10:55
Last Modified: 24 Feb 2020 10:55
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 7461 Statistics for this ePrint Item