AI summaryⓘ
The authors study the problem of dividing a graph into separate, connected pieces called districts, which are small and meet certain rules like having balanced types of nodes or a minimum weight. They improve earlier results by showing their method gives much better approximations for finding balanced star-shaped districts, especially in types of graphs like planar and minor-free graphs. They also extend their approach to cover districts of a fixed radius and allow very close but slightly relaxed balance conditions for nearly optimal coverage. Additionally, they discuss how the problem changes when focusing on minimum district weight instead of balancedness and explore how hard it is to solve these variants.
graph partitioningconnected subgraphsplanar graphsminor-free graphsbounded expansion graphsapproximation algorithmsmax coverage problembalancednessradius-k districtspolitical districting
Authors
Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, Fang-Yi Yu
Abstract
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.