Gerrymandering Planar Graphs

• URL: http://arxiv.org/abs/2312.14721v2
• Date: Mon, 8 Jan 2024 01:10:44 GMT
• Title: Gerrymandering Planar Graphs
• Authors: Jack Dippel, Max Dupr\'e la Tour, April Niu, Sanjukta Roy, Adrian Vetta
• Abstract summary: We study the computational complexity of the redistricting problem (gerrymandering) We prove that the gerrymandering problem is solvable in time in $lambda$-outerplanar graphs.
• Score: 1.237454174824584
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the computational complexity of the map redistricting problem (gerrymandering). Mathematically, the electoral district designer (gerrymanderer) attempts to partition a weighted graph into $k$ connected components (districts) such that its candidate (party) wins as many districts as possible. Prior work has principally concerned the special cases where the graph is a path or a tree. Our focus concerns the realistic case where the graph is planar. We prove that the gerrymandering problem is solvable in polynomial time in $\lambda$-outerplanar graphs, when the number of candidates and $\lambda$ are constants and the vertex weights (voting weights) are polynomially bounded. In contrast, the problem is NP-complete in general planar graphs even with just two candidates. This motivates the study of approximation algorithms for gerrymandering planar graphs. However, when the number of candidates is large, we prove it is hard to distinguish between instances where the gerrymanderer cannot win a single district and instances where the gerrymanderer can win at least one district. This immediately implies that the redistricting problem is inapproximable in polynomial time in planar graphs, unless P=NP. This conclusion appears terminal for the design of good approximation algorithms -- but it is not. The inapproximability bound can be circumvented as it only applies when the maximum number of districts the gerrymanderer can win is extremely small, say one. Indeed, for a fixed number of candidates, our main result is that there is a constant factor approximation algorithm for redistricting unweighted planar graphs, provided the optimal value is a large enough constant.

Related papers

• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections. The margin of victory, or simply margin, is the smallest number of ballots that, if manipulated, can alter the set of winners. Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
  arXiv  Detail & Related papers  (2025-01-24T13:39:23Z)
• On Socially Fair Low-Rank Approximation and Column Subset Selection [62.44413238556872]
  Low-rank approximation and column subset selection are two fundamental and related problems that are applied across a wealth of machine learning applications. We show that surprisingly, even constant-factor approximation fair low-rank approximation requires exponential time under certain standard complexity hypotheses. We give an algorithm for fair low-rank approximation that, for a constant number of groups and constant-factor accuracy, runs in $2textpoly(k)$ time rather than the na"ive $ntextpoly(k)$.
  arXiv  Detail & Related papers  (2024-12-08T20:34:16Z)
• Don't Trust A Single Gerrymandering Metric [0.0]
  We show that each of these metrics is gameable when used as a single, isolated quantity to detect gerrymandering. We do this by using a hill-climbing method to generate district plans that are constrained by the bounds on the metric but also maximize or nearly maximize the number of districts won by a party. One clear consequence of these results is that they demonstrate the folly of specifying a priori bounds on a metric that a redistricting commission must meet in order to avoid gerrymandering.
  arXiv  Detail & Related papers  (2024-09-25T02:40:09Z)
• Drawing Competitive Districts in Redistricting [1.5654305985353367]
  We discuss the problem of drawing plans with at least a fixed number of competitive districts. We show that the task of drawing plans with competitive districts is NP-hard, even on very natural instances. We show that a simple hill-climbing procedure can in practice find districtings on real states in which all the districts are competitive.
  arXiv  Detail & Related papers  (2024-04-17T00:09:41Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  We present an incomplete-time approach to determining the winning regions of parity games via graph neural networks. It correctly determines the winning regions of $$60% of the games in our data set and only incurs minor errors in the remaining ones.
  arXiv  Detail & Related papers  (2022-10-18T15:10:25Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning [58.23459346724491]
  We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions. We draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties.
  arXiv  Detail & Related papers  (2022-05-16T17:40:22Z)
• Mathematically Quantifying Non-responsiveness of the 2021 Georgia Congressional Districting Plan [3.097163558730473]
  We use a Metropolized-sampling technique through a parallel tempering method combined with ReCom. We develop these improvements through the first case study of district plans in Georgia. Our analysis projects that any election in Georgia will reliably elect 9 Republicans and 5 Democrats under the enacted plan.
  arXiv  Detail & Related papers  (2022-03-13T02:58:32Z)
• Implications of Distance over Redistricting Maps: Central and Outlier Maps [10.318010762465939]
  In representative democracy, a redistricting map is chosen to partition an electorate into districts which each elects a representative. A valid redistricting map must satisfy a collection of constraints such as being compact, contiguous, and of almost-equal population. This enables a partisan legislature to gerrymander by choosing a map which unfairly favors it.
  arXiv  Detail & Related papers  (2022-03-02T04:59:30Z)
• Fairmandering: A column generation heuristic for fairness-optimized political districting [0.0]
  American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. Existing computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness. We claim that this is a flawed approach because compactness and fairness are qualities, and introduce a scalable two-stage method to explicitly optimize for arbitrary piecewise-linear definitions of fairness.
  arXiv  Detail & Related papers  (2021-03-21T19:22:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.