S. Gupta, P. Jain, F. Panolan, S. Roy, S. Saurabh:

"Gerrymandering on Graphs: Computational Complexity and Parameterized Algorithms";

Talk: International Symposium on Algorithmic Game Theory, Aarhus, Denmark; 2021-09-21 - 2021-09-24; in: "International Symposium on Algorithmic Game Theory", LNCS / Springer, 12885 (2021), ISBN: 978-3-030-85946-6; 140 - 155.

This paper studies gerrymandering on graphs from a computational

viewpoint (introduced by Cohen-Zemach et al. [AAMAS 2018]

and continued by Ito et al. [AAMAS 2019]). Our contributions are twofold:

conceptual and computational. We propose a generalization of the

model studied by Ito et al., where the input consists of a graph on n

vertices representing the set of voters, a set of m candidates C, a weight

function wv : C → Z+ for each voter v ∈ V (G) representing the preference

of the voter over the candidates, a distinguished candidate p ∈ C,

and a positive integer k. The objective is to decide if it is possible to

partition the vertex set into k districts (i.e., pairwise disjoint connected

sets) such that the candidate p wins more districts than any other candidate.

There are several natural parameters associated with the problem:

the number of districts (k), the number of voters (n), and the number of

candidates (m). The problem is known to be NP-complete even if k = 2,

m = 2, and G is either a complete bipartite graph (in fact K2,n, i.e.,

partitions of size 2 and n) or a complete graph. Moreover, recently we

and Bentert et al. [WG 2021], independently, showed that the problem is

NP-hard for paths. This means that the search for FPT algorithms needs

to focus either on the parameter n, or subclasses of forest (as the problem

is NP-complete on K2,n, a family of graphs that can be transformed

into a forest by deleting one vertex). Circumventing these intractability

results we successfully obtain the following algorithmic results

http://dx.doi.org/10.1007/978-3-030-85947-3_10

https://publik.tuwien.ac.at/files/publik_300320.pdf

Created from the Publication Database of the Vienna University of Technology.