Recognition: unknown
Packing Compact Subgraphs with Applications to Districting
Pith reviewed 2026-05-10 16:37 UTC · model grok-4.3
The pith
A refined analysis upgrades the approximation for packing balanced star districts from O(log n) to O(1) in planar graphs and their generalizations.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
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+ε) 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
What carries the argument
Refined analysis of a packing algorithm for star (or fixed-radius) subgraphs that exploits the density and expansion properties of planar, minor-free, and bounded-expansion graphs.
If this is right
- O(1) approximation for balanced star packing holds in planar, minor-free, and bounded-expansion graphs.
- O(1) approximation extends to packing radius-k districts in planar and apex-minor-free graphs.
- (1+ε) approximation for maximum coverage is possible under arbitrarily small relaxation of balancedness for fixed-radius districts.
- The same O(1) guarantees apply when each district satisfies a minimum weight threshold instead of balancedness.
- Hardness and inapproximability results are established for selected combinations of graph class and district type.
Where Pith is reading between the lines
- If real-world districting maps are sufficiently close to planar or bounded-expansion graphs, the constant-factor guarantees could translate into practical covering algorithms.
- The refined analysis may apply to other compact shapes or additional constraints not considered here.
- Testing the structural assumptions on actual geographic data would indicate how often the O(1) factor remains useful outside the idealized graph families.
Load-bearing premise
The input graphs must belong to the planar, minor-free, or bounded-expansion classes and the districts must be exactly stars or subgraphs of fixed small radius.
What would settle it
A concrete planar graph together with a set of balanced star districts in which the algorithm packs only an o(1) fraction of the optimal number of districts would falsify the constant-factor guarantee.
Figures
read the original 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the problem of packing disjoint compact connected subgraphs (such as stars or fixed-radius subgraphs) in a graph, with additional constraints like balanced weights or minimum weight thresholds, motivated by applications in political districting. The main contribution is a refined analysis of an existing algorithm that improves the approximation ratio for packing balanced star districts from O(log n) to O(1) in planar graphs, with extensions to minor-free graphs and graphs of bounded expansion. Additional results include O(1) approximations for radius-k districts in planar and apex-minor-free graphs, (1+ε) approximations under relaxed balancedness, analogous results for minimum weight requirements, and hardness of approximation results.
Significance. The results are significant as they provide constant-factor approximations for a practically motivated problem in restricted but relevant graph classes. The refined analysis without modifying the algorithm is a strength, potentially leading to better practical performance. The broadening to bounded-expansion graphs and the (1+ε) result with relaxation are valuable. The hardness results help delineate the limits of approximability. The work builds on prior art with clear improvements.
minor comments (2)
- Abstract: Consider adding a sentence clarifying the dependence of the O(1) constant on the specific graph class parameters (e.g., expansion or minor-freeness bounds).
- Ensure theorems explicitly restate the graph class and district type assumptions for each result to improve readability across sections.
Simulated Author's Rebuttal
We thank the referee for the positive assessment of our work, the accurate summary of our contributions, and the recommendation for minor revision. We appreciate the recognition of the refined analysis that improves the approximation ratio without altering the algorithm, as well as the value placed on the extensions to broader graph classes and the hardness results.
Circularity Check
Minor self-citation for base algorithm; refined analysis independent
full rationale
The paper cites Dharangutte et al. 2025 (overlapping authors) only for the existing algorithm and its prior O(log n) bound, then claims a refined analysis yields O(1) for the same algorithm on planar/minor-free/bounded-expansion graphs. This is a standard analytic improvement, not a reduction of the new bound to a fitted parameter or self-referential definition. No equations, ansatzes, or uniqueness theorems in the abstract or description reduce the O(1) claim to the input by construction. Extensions to radius-k districts and relaxed balancedness are presented as additional results from the same analysis. The self-citation is not load-bearing for the central improvement.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Graphs are planar, minor-free, or of bounded expansion
- domain assumption Districts are stars or fixed-radius-k connected subgraphs
Reference graph
Works this paper leans on
-
[1]
Fair clustering with multiple colors.CoRR, abs/2002.07892, 2020
2 [Bak94] Brenda S Baker. Approximation algorithms for NP-complete problems on planar graphs.J. ACM, 41(1):153–180, January 1994. 9, 17 [BFG+26] Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, William Lochet, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, and Kirill Simonov. Packing short cycles.ACM Trans. Algorithms, 22(1):8:1–8:35, ...
-
[2]
Diameter and treewidth in minor-closed graph families.Algorithmica, 27(3):275–291, June 2000
2 [Epp00] D Eppstein. Diameter and treewidth in minor-closed graph families.Algorithmica, 27(3):275–291, June 2000. 6, 9, 18 [FJH11] Roland G Fryer Jr and Richard Holden. Measuring the compactness of political dis- tricting plans.The Journal of Law and Economics, 54(3):493–535, 2011. 2 [FK73] Allen D Franklin and Ernest Koenigsberg. Computed school assign...
-
[3]
We initialize the entry with zero weight:D(t,{γ}, ρ(γ) = 0, π(γ) = 1)◁{0}
Iftis a leaf withX t ={γ}, the only valid partial solution consists solely of the centerγ. We initialize the entry with zero weight:D(t,{γ}, ρ(γ) = 0, π(γ) = 1)◁{0}. 30
-
[4]
Lets ′ be the restriction ofsfort ′ by removingv ∗
Iftintroduces a vertexv ∗ ̸=γwith childt ′, we iterate over all tracesfort. Lets ′ be the restriction ofsfort ′ by removingv ∗. We updateD(t, s)◁ D(t ′, s′)whenssatisfies one of the following conditions: (a)v ∗ ∈P 0 (i.e.,v ∗ is not selected). (b){v ∗} ∈Pforms a singleton component. In this case, we requireπ(v∗) = 0(as the vertex has not found a parent ye...
-
[5]
We iterate over every traces′ for nodet ′ and project it to a tracesfor tby removingv ∗
Iftforgets vertexv ∗ with childt ′, we verify the parent status and update the weights before removing the vertex. We iterate over every traces′ for nodet ′ and project it to a tracesfor tby removingv ∗. (a) Ifv ∗ ∈P ′ 0 is not selected, we updateD(t, s)◁ D(t′, s′). (b) Ifv ∗ is selected withv∗ ∈P ′ l for somel̸= 0, we proceed only if|P ′ l |>1andπ ′(v∗) ...
-
[6]
Iftintroduces an edge(u ∗, v∗)with childt ′, we iterate over every traces′ in the child table D(t′,·)and generate new traces fortbased on the following cases: (a) If at least one endpoint is not selected,u ∗ ∈P ′ 0 orv ∗ ∈P ′
-
[7]
The trace remains unchangeds=s ′, and we update: D(t, s)◁ D(t ′, s′)
The edge is not part of the partial solutionG[U]. The trace remains unchangeds=s ′, and we update: D(t, s)◁ D(t ′, s′). (b) When both endpoints are selected,u∗, v∗ /∈P′ 0, and the edge connects the two vertices. LetPbe the partition obtained by merging the components containingu∗ andv ∗ inP ′. We proceed only if the distance profile is consistent, and con...
-
[8]
A pair iscompatibleif the set of selected vertices is identical (P 1 0 =P 2 0 =P 0) and the distance profiles match (ρ1 =ρ 2)
When vertextjoins childrent 1 andt 2, we iterate over all pairs of tracess1 = (P1, ρ1, π1)for t1 ands 2 = (P2, ρ2, π2)fort 2. A pair iscompatibleif the set of selected vertices is identical (P 1 0 =P 2 0 =P 0) and the distance profiles match (ρ1 =ρ 2). For each compatible pair, we derive a merged traces= (P, ρ, π)as the following: •The partitionPis formed...
-
[9]
The only valid partial solution is the singletonU t ={γ}with distanceρ(γ) = 0and parent statusπ(γ) = 1(by definition for the root of the solution)
Whentis a leaf,X t ={γ}. The only valid partial solution is the singletonU t ={γ}with distanceρ(γ) = 0and parent statusπ(γ) = 1(by definition for the root of the solution). This satisfies the base case, becauseU∩(V t \X t) =∅for allU∈ U γ
-
[10]
Ifv ∗ is not selected, the trace simply extends withv∗ ∈P 0
When introducingv ∗, we iterate over all possible extensions of the child’s traces′. Ifv ∗ is not selected, the trace simply extends withv∗ ∈P 0. Ifv ∗ is selected (Item 2b), we enumerate all possible distance guessesrforρ(v ∗)which ensure the completeness. We setπ(v ∗) = 0since v∗ has no edges yet
-
[11]
Sincev∗ is removed from the active bag, it cannot be adjacent to any vertices introduced in the future; thus, its parent statusπ(v ∗)and distanceρ(v ∗)are final
When forgettingv ∗, we finalize its status and update the weights. Sincev∗ is removed from the active bag, it cannot be adjacent to any vertices introduced in the future; thus, its parent statusπ(v ∗)and distanceρ(v ∗)are final. For completeness, consider any valid global solution U∈ U γ containingv ∗. Because all neighbors ofv∗ inG[U]are inV t′, the trac...
-
[12]
If both are selected (Item 4b), we merge their respective components
When introducing an edge(u∗, v∗), if either endpoint is unselected (Item 4a), we ignore the edge and copy the child’s weights. If both are selected (Item 4b), we merge their respective components. We then check the triangle inequality and enumerate all valid updates to the parent vectorπ. This ensures that if(u∗, v∗)establishes the parent relationship for...
-
[13]
For the approximation error, we sum the weights in sets from the children withε t1 andε t2, and then run Trimℓ,δ
When joining childrent1 andt 2, we merge pairs of compatible traces sharing the same selected sets and distance profiles. For the approximation error, we sum the weights in sets from the children withε t1 andε t2, and then run Trimℓ,δ. By Lemma A.1, the resulting error bound satisfiesε t ≥ε t1 +ε t2 +δ. 32 Finally, attherootnodeX root ={γ}, everyselectedv...
-
[14]
Therefore, ℓ1(w′) = (c−1)w ′ 1 −w ′ 2 ≥ℓ 1(w∗) = (c−1)w ∗ 1 −w ∗ 2 ≥0byℓ 1-dominance
Then, there exists a districtS∈W 1 ⊆W ∗ withw ′ =w(S)thatε-approximates andℓ 1-dominatesw ∗. Therefore, ℓ1(w′) = (c−1)w ′ 1 −w ′ 2 ≥ℓ 1(w∗) = (c−1)w ∗ 1 −w ∗ 2 ≥0byℓ 1-dominance. Additionally, (c−1)w ′ 2 −w ′ 1 ≥e −ε(c−1)w ∗ 2 −e εw∗ 1 (ε-approximated) ≥ e−ε(c−1)−e ε w∗ 1 (w∗ 2 ≥w ∗ 1) ≥0(whenevere 2ε <(c−1)) The above two show thatSisc-balanced. Asw ′ 4/...
-
[15]
Iftis a leaf (X t =∅), we set the empty state with zero weight,D(t,∅)◁{0}
-
[16]
Lets ′ be the restriction ofsfort ′ by removingv ∗
Iftintroduces a vertexv ∗ with childt ′, we iterate over allsfort. Lets ′ be the restriction ofsfort ′ by removingv ∗. We updateD(t,s)◁ D(t ′,s ′)whenssatisfies one of the following conditions: (a)v ∗ ∈P 0 is not selected. (b) Whenv ∗ ∈P i is selected withi̸= 0and{v ∗} ∈P i,l forms a singleton component, if v∗ ̸=γ i, we requireπi(v∗) = 0andρ i(v∗)∈ {0, . ...
-
[17]
We iterate over every traces′ fort ′ and project it to a tracesfortby removingv ∗
Iftforgets vertexv ∗ with childt ′, we verify the parent status and update the weights before removing the vertex. We iterate over every traces′ fort ′ and project it to a tracesfortby removingv ∗. (a) Ifv ∗ isnotselected(v ∗ ∈P ′ 0), weupdateD(t,s)◁D(t ′,s ′)similartoItem3ainsectionA.2. (b) Ifv ∗ is selected in districti ∗ (i.e.,v ∗ belongs to a componen...
-
[18]
For any states′ inD(t ′,·), (a) Ifu ∗ ∈P ′ i andv ∗ ∈P ′ i′ withi̸=i ′ ori=i ′ = 0, we simply ignore the edge and D(t,s ′)◁ D(t ′,s ′)
Whentintroduces edge(u ∗, v∗)and has childt ′, we merge the partition, verify the distance profile, and update the parent status. For any states′ inD(t ′,·), (a) Ifu ∗ ∈P ′ i andv ∗ ∈P ′ i′ withi̸=i ′ ori=i ′ = 0, we simply ignore the edge and D(t,s ′)◁ D(t ′,s ′). (b) Ifu ∗, v∗ ∈P ′ i∗ are in the same district, we run the same procedure as Item 4b in sec...
-
[19]
Whentjoins childrent 1 andt 2, we iterate over compatible pairss1,s 2 inD(t 1,·)andD(t 2,·) respectively so thatP 1 i =P 2 i ,ρ 1 i =ρ 2 i, andγ 1 i =γ 2 i for alliand updateD(t,s)as Item 5. After computing the transitions forD(t,s)at each nodet, we apply a trimming step withδalg = min{ε, δ/3}/|VT|to keep the size of the dynamic programming table polynomi...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.