Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, Fang-Yi Yu
11 min
This paper tackles a core algorithmic challenge in political districting: how to divide a graph (representing geographic regions) into compact, connected, vertex-disjoint subgraphs (districts) that maximize population coverage while satisfying fairness constraints like balance or minimum size. Graphs model voting precincts as vertices with weights (e.g., population), and edges represent geographic adjacency. Compactness ensures districts are geographically coherent—avoiding gerrymandering—via radius-k or diameter-k constraints. The objective is to pack as many such districts as possible without overlap, covering maximum total weight.
Why care? Real-world districting must balance compactness (short travel distances), connectivity/contiguity, population equality, and fair representation (e.g., Voting Rights Act compliance for minority groups). Prior work had weak O(log n) approximations; this paper delivers breakthroughs like constant-factor and near-optimal PTAS results for planar/minor-free graphs modeling maps.
Compactness is defined via radius-k (all vertices within distance k from a center) or diameter-k (max distance ≤k), either strongly (in induced subgraph) or weakly (in original graph). Stars (radius-1) are simplest: one center connected to leaves.
Composition requirements:
Problem: Max-weight packing of such districts. NP-hard, but approximations shine on planar graphs (maps), minor-free (no dense substructures), and bounded expansion graphs.
Constant O(1)-approximation for balanced star districts:
PTAS for relaxed districting:
All results adapt to weight thresholds instead of balance.
Inapproximability: Shows packing compact subgraphs with thresholds is hard (e.g., APX-hard for stars in general graphs). Even in planar graphs, gaps persist for strict balance without relaxation.
Key insight: Geometry (planarity) + structure (minor-freeness) enables dynamic programming and rounding, but general graphs resist constants.
Algorithmic pipeline:
Intuition: In planar graphs, low treewidth lets you 'peel' layers; refined analysis bounds loss from rounding dependencies. For PTAS, ε-net sampling + local optimality.
This bridges graph algorithms and computational social choice, opening doors to practical districting tools.
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs (Dharangutte et al. 2025). In particular, we improve the approximation factor from $O(\log n)$ to $O(1)$ for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an $O(1)$ approximation for packing radius-$k$ districts (with a constant $k$) in planar and apex-minor-free graphs. In order to get a $(1+\varepsilon)$ approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to $1$), for bounded radius-$k$ districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types.
Alex: Got it. Then how do they turn those fractions into actual picks?
Sam: They convert those fractions into actual picks using random choices: sort the districts by weight, and for each, flip a coin weighted by its fraction to include it if it doesn't overlap what's already picked. The hitch is overlaps—if too many partial districts touch the same spots, the random picks fight each other, wasting chances.
Alex: So that's where the interference comes in? How do they prove it doesn't waste too much?
Sam: They measure interference with a correlation ratio—basically, how much the fractions of touching districts multiply up compared to their total. In maps without tangled minor structures—like planar ones without certain knotted subgraphs—this ratio stays bounded by a fixed number, no matter the map size. The proof uses a probabilistic charging trick: imagine orienting edges randomly in rounds, like cars picking lanes to merge onto highways. Picture two overlapping districts as cars on colliding paths toward a shared merge point, or pivot, along the shortest route between their centers. By randomly pointing edges forward k times and shrinking paths step-by-step, most colliding pairs hit a pivot where one car's path leads there reliably, charging the blame to just a few spots per district. Since these sparse maps have low out-degree—like few highway exits per spot—each district gets charged only a fixed number of times, while pairs get caught constantly. This keeps the correlation ratio fixed, turning the rounding loss into a constant factor.
Alex: So the random orientations act like shuffling traffic to count collisions fairly, without gridlock piling up.
Sam: Exactly. And to solve the LP itself without listing every possible district, they use a separation oracle: given vertex prices from the dual problem, it hunts for an underpriced valid district—like spotting a bargain bundle that beats the current prices. For radius-k districts, they build it with dynamic programming on small neighborhoods of bounded treewidth, trimming extras for a near-optimal finder.
Alex: So the separation oracle handles finding good single districts efficiently... but for packing many without overlaps, they need something more. Does the paper push the approximation even closer to optimal?
Sam: Yes, they do—for certain maps like apex-minor-free ones, which are planar graphs with maybe one extra tangled spot removed. The approach layers the map like onion skins using breadth-first search from a root: number levels by distance, then for a chosen step t, remove every t-th layer, splitting the map into thin connected pieces. Each piece has bounded treewidth—a structure like a tree where branches hold small groups of connected spots, making problems solvable by checking states bag by bag. Researchers call this Baker's layering; it ensures at least one layering keeps most of an optimal packing intact, losing only a small ε fraction by the pigeonhole principle.
Alex: Okay, thin layers with tree-like structure... so dynamic programming can fill them like solving a puzzle level by level. But packing multiple balanced districts there—how does the DP track that without exploding?
Sam: The DP on the tree decomposition records for each bag—those small vertex groups—whether parts of districts are forming, like open chains needing connection, plus running totals of voter weights for balance or thresholds. It relaxes the balance slightly, say from c to c times (1+ε), to keep states manageable since weights are trimmed to succinct approximations. This solves packing exactly on each thin piece, then picks the best layering for a (1+ε)-approximation overall. The paper notes this handles both c-balanced and threshold districts.
Alex: So by slicing thin and relaxing just a bit, you get arbitrarily close to optimal on these maps.
Sam: Precisely. And for bounded expansion graphs—sparse networks everywhere—they tweak the random contractions to control diameters, extending the constant correlation bound with huge but fixed factors depending on radius k. It keeps the O(1)-approximation for star districts there too.
Alex: The separation oracle uses dynamic programming on treewidth-bounded neighborhoods... but to find violating districts efficiently, how does it narrow down those without checking everything?
Sam: The key is spotting bundles of connected areas—subgraphs—that add up to a good total value under dual prices from the math solver. Instead of listing every possible bundle, which could be endless, they seek a shortlist that covers all options closely: for any real bundle's weight vector, there's one in the list within a small multiplicative error, like 1 plus a tiny ε, and at least as good on a scoring line. This shortlist acts like a trimmed summary—researchers call it the trimmed connected subgraph sum problem. Each area gets a vector of numbers: objective weight, the two voter types for balance, and the dual price. The scoring lines check balance—for c-balanced districts, one line is (c-1) times type one minus type two; if positive, it violates balance one way. They run the trimmer twice, once per line, to catch violations. This finds a bundle where the price paid is less than its true worth by a bit, while matching at least half the best possible. On apex-minor-free graphs—planar ones minus maybe one knotty spot—the neighborhood around a center has fixed treewidth, like a chain of small bags you process state-by-state in DP: track partial sums, open connections, approximated weights. This gives a fully polynomial approximation scheme, or FPTAS: time polynomial in map size n, but blows up mildly with dimension d and 1/ε.
Alex: And for the PTAS on relaxed balance? Like allowing δ more leeway in c?
Sam: The DP on bounded treewidth handles δ-relaxed packing directly—loosen balance to c(1+ε), track in states. Combine with Baker's layering: slice levels every t steps, solve per thin piece, pick best shift. Loses only ε fraction of optimal weight, since few districts span deleted layers. Yields 1+ε approximation for radius-k on planar or apex-minor-free maps.
Alex: Solid for slightly flexible real-world rules... keeps computational districting tractable. But what about the limits? The paper doesn't claim perfection everywhere, right?
Sam: Correct. For general graphs—even planar ones with no restrictions—packing these districts is NP-hard, meaning no efficient algorithm guarantees the best possible coverage unless problems we think are intractable become easy. They prove you can't approximate better than roughly the square root of the map size in general cases, even for simple star-shaped districts. Even finding one valid district under diameter bounds—not radius—is NP-hard. And for three voter types in balanced districts, no approximation works at all, since it boils down to exact subset sums, which are notoriously hard.
Alex: So on messy real-world maps without those minor-free assumptions, it's fundamentally tough. That sets realistic expectations. Any key bottlenecks holding back exact optimal on clean maps?
Sam: The rounding approach leaves a fixed gap from overlaps—you can't close it fully without new ideas, as prior work noted. The dynamic programming for near-optimal needs trimming partial sums, which works for relaxed balance but strains under exact multi-district tracking, blowing up computation. No clear path yet to optimal exact packing on apex-minor-free graphs.
Alex: Makes sense... so the constant approximation and PTAS for relaxed cases fill a meaningful gap for practical tools, especially where maps fit planar-like structures.
Sam: Precisely. These results enable software for drawing districts that respect compactness laws—like keeping areas close and balanced—while covering substantial population. On grid-like maps, even exact near-optimal is possible with tweaks. Open questions remain, like extending oracles to wider sparse graphs or parametrizing by overlap measures for tailored guarantees.
Alex: That's a grounded advance... tying math rigor to fairer map-making without overreaching. Thanks for joining me, Sam.
Sam: My pleasure. Thanks for listening to ResearchPod.