Gerrymandering Trees: Parameterized Hardness
share
In a representative democracy, elections involve partitioning geographical space into districts which each elect a single representative. Legislation is then determined by votes from these representatives, and thus political parties are incentivized to win as many districts as possible (ideally a plurality). Gerrymandering is the process by which these districts' boundaries are manipulated to give favor to a certain candidate or party. Cohen-Zemach et al. (AAMAS 2018) proposed Gerrymandering as a formalization of this problem on graphs (as opposed to Euclidean space) where districts partition vertices into connected subgraphs. More recently, Gupta et al. (SAGT 2021) studied its parameterized complexity and gave an FPT algorithm for paths with respect to the number of districts k. We prove that Gerrymandering is W[2]-hard on trees (even when the depth is two) with respect to k, answering an open question of Gupta et al. Moreover, we prove that Gerrymandering remains W[2]-hard in trees with ℓ leaves with respect to the combined parameter k+ℓ. To complement this result, we provide an algorithm to solve Gerrymandering that is FPT in k when ℓ is a fixed constant.
READ FULL TEXT