Gerrymandering on graphs: computational complexity and parameterized algorithms

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic game theory and complexity (91A68) Voting theory (91B12) History, political science (91F10)

Abstract: Partitioning a region into districts to favor a particular candidate or a party is commonly known as gerrymandering. In this paper, we investigate the gerrymandering problem in graph theoretic setting as proposed by Cohen-Zemach et al. [AAMAS 2018]. Our contributions in this article are two-fold, conceptual and computational. We first resolve the open question posed by Ito et al. [AAMAS 2019] about the computational complexity of the problem when the input graph is a path. Next, we propose a generalization of their model, where the input consists of a graph on

n

vertices representing the set of voters, a set of

m

candidates

m a t h c a l C

, a weight function

w_{v} : m a t h c a l C i g h t a r r o w {m a t h b b Z}^{+}

for each voter

v i n V (G)

representing the preference of the voter over the candidates, a distinguished candidate

p i n m a t h c a l C

, and a positive integer

k

. The objective is to decide if one can partition the vertex set into

k

pairwise disjoint connected sets (districts) s.t

p

wins more districts than any other candidate. The problem is known to be NPC even if

k = 2

,

m = 2

, and

G

is either a complete bipartite graph (in fact

K_{2, n}

) or a complete graph. This means that in search for FPT algorithms we need to either focus on the parameter

n

, or subclasses of forest. Circumventing these intractable results, we give a deterministic and a randomized algorithms for the problem on paths running in times

2.61 9^{k} (n + m)^{O (1)}

and

2^{k} (n + m)^{O (1)}

, respectively. Additionally, we prove that the problem on general graphs is solvable in time

2^{n} (n + m)^{O (1)}

. Our algorithmic results use sophisticated technical tools such as representative set family and Fast Fourier transform based polynomial multiplication, and their (possibly first) application to problems arising in social choice theory and/or game theory may be of independent interest to the community.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Gerrymandering on graphs: computational complexity and parameterized algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670918)