Parameterized Algorithms for Gerrymandering on Graphs
Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. In this talk, we will look at the problem of gerrymandering over a network structure, where the voters are embedded in a graph, and the task is to partition the vertex set into k pairwise disjoint connected sets (called districts) such that the target candidate wins more districts than any other candidate. The problem is NP-hard even for paths. In this talk, we will look at some parameterized algorithms for this problem.