2018/08/27 by Richard Kueng, Dustin G. Mixon, Kueng, Richard +3 · 1 voice
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1808.08905
openalex publication_date 2018/08/27 · arxiv published 2018/08/27 · arxiv updated 2018/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Gerrymandering is a long-standing issue within the U.S. political system, and it has received scrutiny recently by the U.S. Supreme Court. In this note, we prove that deciding whether there exists a fair redistricting among legal maps is NP-hard. To make this precise, we use simplified notions of "legal" and "fair" that account for desirable traits such as geographic compactness of districts and sufficient representation of voters. The proof of our result is inspired by the work of Mahanjan, Minbhorkar and Varadarajan that proves that planar k-means is NP-hard.