Packing Compact Subgraphs with Applications to Districting

Packing disjoint subgraphs is a fundamental problem that has many applications. The most notable applications are in political districting, in which connectivity, contiguity and compactness is highly preferred and sometimes enforced by state law [4]. Furthermore, the $c$-balanced property guarantees that each political group has a decent amount of representation, which can be viewed as compliance with the Voting Rights Act of 1965 [41]. The weight threshold is another natural property such that each district is significant in size/population. In general, the districting problem can also be applied to the allocation of other types of resources and services [13, 51].

Earlier work of [33] considered the $c$-balanced districting problem, which is one case of the districting problem defined earlier. [33] provided various hardness results and approximation algorithms for different families of graphs. There are two major directions left open in [33]. First, most of the positive results (without additional assumptions on the districts or on very special graphs such as complete graphs or trees) are only for star districts, which are (strong) radius-1 subgraphs. It was not clear how the results could be extended to higher, constant values of radius-$k$. Second, and more importantly, one of the most prominent applications in political districting considers planar graphs (e.g., the geographical subdivision into townships and counties). The best approximation factor for packing $c$-balanced star districts in a planar graph in [33] is $O(\log n)$ without a matching lower bound. Resolving this issue by either developing a constant-factor approximation or proving a stronger hardness result is a major open question.

Our problem is connected to computational (re)districting for schools and elections, which dates back to the 1960s [45]. Since then, extensive work (see [9]) has studied them as an algorithmic problem, typically focusing on specific constraints such as balance or compactness. For balancedness, recent work introduces vote-band metrics [27], which require a certain fraction of votes to fall within a specified range (e.g., 45-55%) for competitive elections. Subsequently, [19, 33] introduce the $c$-balanced district problem. Other research focuses on optimizing balance scores directly [40]. Regarding compactness, one line of work treats it as a transportation cost [2, 38, 22], such notions also relate to the fair clustering problem [12, 18, 49, 17]. Other research focuses on optimizing compactness scores [8, 50, 53, 48] or using Voronoi or power diagrams with some variant of $k$-means [67, 24, 25, 39]. Besides the optimization approach, another popular method uses sampling to generate a distribution over districts and create a collection of district plans for selection [5, 21, 28, 59, 16].

Finally, several papers take a fair division approach [54, 64, 26]. The problem is quite different, however, as fairness in this context is defined concerning parties (types) and the number of seats they would win (i.e., the number of districts where they would have a majority) compared to other districts, rather than the internal composition of individual districts.

Besides its applications in political districting, packing compact subgraphs from a given family, such as paths, cycles, and stars, is a fundamental problem in its own right. Let $\mathscr{H}$ be a family of graphs. A $\mathscr{H}$-packing of a graph $G$ is a set of vertex disjoint subgraphs such that each subgraph is isomorphic to some element of $\mathscr{H}$. These types of problems have been studied in many papers with various hardness and approximation results, such as packing stars [63, 6, 56, 68, 66], induced stars [52], constant sized graphs [57, 14, 55], cycles and paths [44, 47, 66, 10], cliques and bicliques [46, 42, 43], and low-diameter spanning trees [20]. Another line of work [1, 36, 35, 34, 58, 69] explores covering and partitioning graph with $k$-clubs, as a generalization to the clique cover problem. $S\subseteq V$ is a $k$-club in graph $G$ if $S$ induces a subgraph in $G$ with diameter at most $k$ (cliques are $k$-club for $k=1$). $k$-club with at least $t$ vertices is called a $(t,k)$-club. The Minimum $k$-club cover problem asks for minimum number of $k$-clubs that cover all vertices in the graph and [35, 69] explore hardness and approximation algorithms for different values of $k$. The Maximum Disjoint $(t,k)$-club covering problem asks for vertex disjoint $(t,k)$-clubs that cover maximum number of vertices in the graph $G$. [36, 58] study this problem for $k=2,3$ on general and bipartite graphs. Note that none of the above work consider the composition properties of the subgraphs. Thus, the results are only marginally relevant to this paper.

In this paper, we resolve both problems left open in [33], significantly expanding the theoretical understanding of this problem. Our results are summarized in Table 1.

Consider a connected undirected graph $G=(V,E)$ with $n=|V|$ vertices and $m=|E|$ edges. We define a general district packing problem. The input graph is associated with an objective weight function $w:V\to {\mathbb{Z}}_{\ge 0}$ and potentially a list of feature weight functions $w_1,\mathrm{\dots },w_d:V\to {\mathbb{Z}}_{\ge 0}$. These feature weights can be independent of each other as well as of objective weights. A district is a subset of vertices $T\subseteq V$ such that the induced subgraph $G[T]$ is connected and satisfies specific validity constraints: compactness (constraints on topology) and composition (constraints on feature weights). A (partial) districting solution is a collection of vertex-disjoint districts $𝒯=\{T_1,\mathrm{\dots }\}$. We remark that finding a complete partition of the graph into vertex-disjoint districts (i.e., ${\bigcup }_{T\in 𝒯}T=V$) may not be possible; rather, we seek a packing of disjoint districts with a maximum total objective weight.

For the compactness constraints, besides connectivity, we consider radius or diameter bounds. Specifically, the distance $d_G(u,v)$ between vertices $u$ and $v$ in $G$ is the number of edges on the shortest path between $u$ and $v$. A district $T$ has bounded strong radius $k$ if there exists a vertex $\gamma \in T$ such that for all other vertices $u\in T$ , $d_{G[T]}(u,\gamma )\le k$. Similarly, $T$ has bounded weak radius $k$ if there exists a vertex $\gamma \in V$ such that for all other vertices $u\in T$, $d_G(u,\gamma )\le k$. A districting $𝒯$ satisfies strong (or weak) radius bound $k$ if every $T\in 𝒯$ has bounded strong (or weak) radius $k$. A district $T$ has bounded strong diameter if all pairs of vertices $u,v$ in $T$ have distance in the induced subgraph at most $k$, i.e., $d_{G[T]}(u,v)\le k$. It has bounded weak diameter if for every pair of vertices $u,v\in T$, their distance in the original graph $G$ is at most $k$, i.e., $d_G(u,v)\le k$.

Composition constraints impose limits on the feature weights of each district. First, we can extend our weight to a single district $T$ and a districting solution $𝒯$. For any weight function (representing either the objective $w$ or a feature $w_i$), the district weight is $w(T)={\sum }_{v\in T}w(v)$, and the total weight of the districting solution $𝒯$ is $w(𝒯)={\sum }_{T\in 𝒯}w(T)$. We consider two types of composition requirements:

We first examine the districting problem from a bird’s-eye view and explain how the technical tools introduced in this work can be applied more generally.

Recall that $x_S$ is the primal variable in the LP formulation for a district $S$, $x_S\in [0,1]$. We consider districts of strong radius $k$. The LP framework allows addressing feasibility and packing in an orthogonal manner. The separation oracle helps to find a feasible district that substantially improves the LP solution, and the randomized rounding manages packing.

The performance of the randomized rounding procedure is governed by a second-order correlation term ${\sum }_{A\cap B\ne \mathrm{\varnothing }}{x}_A{x}_B,$ which measures the extent to which overlapping districts interfere during rounding. Given a graph $G$ and $𝒮$ (a collection of connected subgraphs of $G$), we say that $G,𝒮$ has correlation ratio $\tau$ if ${\sum }_{S:v\in S}{x}_S\le 1$, and ${\sum }_{A\cap B\ne \mathrm{\varnothing }}{x}_A{x}_B\le \tau {\sum }_S{x}_S,$ for all $v$ and $\{x_S\}$. Lemma 2 gives an $O(\tau )$ approximation guarantee if we can establish any bound on $\tau$. In particular, in Lemma 3 we show that if $G$ is $H$-minor-free for some $H$ of size $h$, then $\tau$ can be bounded by a function $q(h,k)$ that depend solely on $h$ and $k$. Establishing this bound yields a constant-factor approximation. The main technical difficulty is that intersecting districts may overlap in highly structured ways. Even when each district has a strong radius $k$, a fixed district $A$ could, a priori, intersect with many other districts $B$. A naïve charging argument could therefore lead to an $O(n)$ blow-up.¹¹1For example, consider $A$ being a star of $\mathrm{\Omega }(n)$ vertices, with each leaf intersecting distinct districts. In this case, the terms $x_A$ involved in the correlation sum are at least $\mathrm{\Omega }(n)x_A$. This shows some districts will be charged for $\mathrm{\Omega }(n)$ times in a naïve charging argument.

To overcome this, we exploit the structural sparsity of minor-free graphs. Specifically, an $H$-minor-free graph has bounded degeneracy – there is an orientation of the edges such that the out-degree of any vertex is bounded by $O(h\sqrt{\log h})$ [65, 3]. Using this property, we design a probabilistic charging scheme based on a sequence of random edge orientations and contractions. For each intersecting pair $(A,B)$, we identify a carefully structured “intersecting pivot” along a canonical path between their centers. We then show that with probability ${\mathrm{\Omega }}_{h,k}(1)$, the pair can be charged to one endpoint district in a way that ensures:

• $\mathrm{■}$

  Each intersecting pair is charged with constant probability.

• $\mathrm{■}$

  Each district receives only $O_{h,k}(1)$ total charge.

This argument combines bounded degeneracy, controlled path contractions, and a forward-trajectory encoding that limits the number of distinct pivots that can be associated with a fixed district. The result is a constant bound on the correlation term, completing the rounding analysis. The analysis here is independent of how the LP fractional solution is computed and thus can be combined with any algorithm or implementation that produces an (approximate) fractional solution.

A similar argument extends to bounded-expansion graphs (Section 4.3), since such graphs have constant “density” everywhere and also enjoy bounded degeneracy. With a slightly modified contraction, the correlation term is bounded by a factor that depends only on the density parameter. We remark that the randomized rounding algorithm we use is fairly standard [23, 15], but the analysis of its performance is new and may find further applications.

The new analysis of randomized rounding, combined with the separation oracle for star districts in [33], immediately yields an $O(1)$-approximation algorithm for packing $c$-balanced or $B$-threshold star districts in planar, minor-free, and bounded-expansion graphs.

In order to handle districts of a general radius $k$ with $k>1$, we also need to extend the separation oracle for star districts in [33] to accommodate a general radius $k$ (Appendix A). To do that, we formulate a vector-valued subset sum problem on a connected compact subgraph. Similar to the standard subset sum, we trim the solution space by keeping a succinct representation of the subsets that approximate every possible solution with a multiplicative factor and maximize a linear score. This new framework can be applied to both $c$-balanced districts and threshold districts, as well as to a generic connected knapsack problem (see [32]). For the connected subgraph sum problem, we present an FPTAS on graphs of bounded treewidth. On a planar graph or an apex-minor-free graph, the $k$-hop neighborhood of any center vertex has bounded treewidth [37, 11]. Thus, we can enumerate every possible center vertex and apply the separation oracle in each bounded radius-$k$ neighborhood. This provides an efficient separation oracle for planar and apex minor-free graphs.

Section B improves the approximation guarantee for apex-minor-free graphs using a different paradigm with two elements: the Baker’s layering approach [7] for planar and apex minor-free graphs [30] and a PTAS for subgraph packing for graphs of bounded treewidth.

We explain the main idea for planar graphs. The Baker’s approach considers a BFS from an arbitrary root and removes the vertices on the layers $=imodt$, for some $0\le i\le t-1$. With a fixed $i$, this will partition the graph into connected components, each with at most $t$ consecutive layers of the BFS. Thus, each piece is $t$-outerplanar and thus has treewidth at most $3t-1$ [11].

Suppose, for now, we have a magic algorithm $𝒜$ that solves compact subgraph packing in a graph of bounded treewidth. We apply algorithm $𝒜$ for each piece, such that all obtained districts from the connected components combined form a feasible packing solution for the original graph $G$. If we try this for all possible values of $i$ between $0$ and $t-1$, and take the maximum solution, this is a $(1+\epsilon )$ approximation to the optimal with $t=O(k/\epsilon )$. The reason is that in an optimal solution, only the subgraphs that are “influenced” by the removed layers are destroyed. These vertices are within $O(k)$ hops from the removed layers since each compact subgraph has radius $k$. By the pigeonhole principle, at least one of the $t$ candidate solutions keeps all but $O(k/t)=O(\epsilon )$ fraction of the optimal weight.

The central technical task is therefore to find the algorithm $𝒜$ that solves the problem of packing compact districts on bounded-treewidth graphs. Unlike the separation oracle problem (which asks for a single feasible district), packing requires simultaneously selecting multiple disjoint connected subgraphs subject to either balancedness or threshold constraints. This introduces a significantly more complex state space.

We develop a dynamic programming scheme over a tree decomposition that encodes partial district configurations within each bag. The DP must simultaneously track the connectivity information of partially formed districts and the cumulated weight (for threshold constraints) or the weight balance (for $c$-balanced districts). Our DP mechanism has to relax the parameter $c$ slightly (for the $c$-balanced districts) or the weight threshold $B$ (for the threshold districts) by a factor.

In this section, we briefly describe the linear programming approach for the district packing problem, together with the randomized rounding framework based on the support variables of an optimal linear program solution. The approximation guarantee of this framework relies on bounding certain second-order terms involving the support variables. In particular, throughout this section we aim to prove the following key technical Lemma 3 for minor-free graphs and Theorem 13 for bounded expansion graphs.

Combining the above lemma with the linear programming formulation and the randomized rounding framework yields the following results.

We prove Theorem 4 and Theorem 5 at the end of this section. The high level approach of proving Lemma 3 is to partition the pairs of intersecting districts into different cases, and give the upper bound to each of the case. To start with the simplest case, we first introduce the following notions of center vertices and intersecting pivots.

The analysis of the easy case does not simply generalize to the non-trivial case where $i_{A,B},c_A$ and $c_B$ are all distinct. One potentially convincing reason is that if we fix the district $A$, all the intersecting pivots $i_{A,B}$ might be distinct, which implies that the sum over all intersecting districts ${\sum }_{B:A\cap B\ne \mathrm{\varnothing }}{x}_A{x}_B$ could be as large as $|A|\cdot x_A=\mathrm{\Omega }(n)\cdot x_A$ in the worst case.

Fortunately, one can utilize the bounded degeneracy property of $H$-minor-free graphs for a fixed minor $H$ of size $h$. A $d$-degenerate graph is an undirected graph in which every subgraph has at least one vertex of degree at most $d$. The degeneracy of a graph is the smallest value $d$ for which it is $d$-degenerate. The following fact bounds the degeneracy of $H$-minor-free graphs.

With this property, we are able to design a randomized charging scheme, such that for each pair of intersecting districts $(A,B)$, with probability ${\mathrm{\Omega }}_{h,k}(1)$, the cost $x_A{x}_B$ will be charged to either $x_A$ or $x_B$ and simultaneously each $x_A$ or $x_B$ will be charged by at most $O_{h,k}(1)$ times. This completes the proof by the standard probabilistic method. We summarize the above discussion into the following lemma, which directly leads to Lemma 3.

Before proving Lemma 8, we first show that Lemma 8 implies the correctness of Lemma 3, the main technical lemma of this section.

While the correlation ratio is constant on $H$-minor-free graphs (Lemma 3), it has an $\mathrm{\Omega }(\sqrt{n})$ lower bound on general graphs [33]. This dichotomy naturally raises the question of how broadly the constant bound persists, and whether one can obtain a smooth tradeoff between these two regimes. In this subsection, we take a step in this direction by considering bounded expansion graphs [60, 61, 62] (refer Definition 1), a class that formalizes the notion of everywhere sparsity. To better demonstrate our results, we first introduce a recursively defined sequence ${\{d_r^f\}}_{r=0}^{\mathrm{\infty }}$.

If the context is clear we will omit $f$ and use $d_r$ to denote $d_r^f$. We remark that when $f$ is a polynomial, $d_r^f$ is doubly exponential in $r$.

It is straightforward to check that (from Definition 12), whenever $k$ is a constant, despite being enormous, the approximation ratio is still a constant.

Algorithm $ℛ$ in Lemma 8 does not directly imply Theorem 13, because in each contraction which produces $G_r$ from $G_{r-1}$, the diameter of each contracted vertex subset is not bounded. Fortunately, with a slight tweak to algorithm $ℛ$, we are able to guarantee the diameter on each contraction, thereby proving Theorem 13.