2021/02/17 by Matthias Bentert, Tomohiro Koana, Bentert, Matthias +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2102.08905
openalex publication_date 2021/02/17 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. While typically studied from a geographical point of view, addressing social network structures, the investigation of gerrymandering over graphs was recently initiated by Cohen-Zemach et al. [AAMAS 2018]. Settling three open questions of Ito et al. [AAMAS 2019], we classify the computational complexity of the NP-hard problem Gerrymandering over Graphs when restricted to paths and trees. Our results, which are mostly of negative nature (that is, worst-case hardness), in particular yield two complexity dichotomies for trees. For instance, the problem is polynomial-time solvable for two parties but becomes weakly NP-hard for three. Moreover, we show that the problem remains NP-hard even when the input graph is a path.