[Back]

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