Hardness and Approximation Algorithms for Balanced Districting Problems

There are three elements in the balanced districting problem that make it challenging and interesting, from a technical perspective: 1) connectivity – the induced subgraph of a district is connected 2) packing and coverage maximization – no vertex belongs to two districts and we maximize the total weights of included vertices; 3) balancedness – the two types of weights in a district need to be roughly balanced. These elements are shared with a number of well known hard problems, suggesting that our problem is also computationally challenging. For example, the exact set cover problem asks if there is a perfect coverage and packing in a set cover instance. The packing element is shared with maximum independent set problem – a vertex included will forbid its neighbors to be included. And the balancedness is shared with subset sum problem. Therefore by using the hardness of these problems we can show hardness and hardness of approximation of the balanced districting problem for a variety of graph classes. The hardness of the balanced districting problem is immediately shown by a reduction from exact set cover problem. By a reduction from maximum independent set problem, we can show that the balanced districting problem does not have an approximation of $n^{1/2-\delta }$ for any constant $\delta >0$ in a general graph of $n$ vertices unless $𝖯=\mathrm{𝖭𝖯}$ and is $\mathrm{𝖠𝖯𝖷}$-hard for bounded degree graphs. From a reduction from the planar 1-in-3SAT problem, the balanced districting problem is $\mathrm{𝖭𝖯}$-hard for a planar graph, and even if each district has at most three vertices – a crucial condition since the problem can be solved exactly by maximum weighted matching if each district is only allowed to have two vertices. If the input graph is a tree or a complete graph – extremely simple topologies for which many $\mathrm{𝖭𝖯}$-hard problems can be solved in polynomial time, the balanced districting problem is still $\mathrm{𝖭𝖯}$-hard due to the balancedness requirement by a reduction from subset sum. All of the hardness proofs hold even if we limit the output districts to be only of a star topology. This set of hardness results can be seen from the Top section of Table 1.

On the positive side, it is natural to ask if existing techniques for solving or approximating these related problems can be borrowed for the balanced districting problem. The answer turns out to be often “not really”, even if we only look for balanced star districts. The additional requirements in our problem often break some crucial steps. For example, the problem of maximum independent set has an easy $\mathrm{\Omega }(n)$ lower bound if the input graph is sparse (or planar) – thus a simple random greedy algorithm with conflict checking gives an easy constant approximation algorithm. But such lower bound no longer holds true for our problem if the weights are not balanced. Even for star districts, when the maximum degree is not bounded by a constant, the number of potential balanced districts can be exponential in $n$, the size of the network.

We show in Section 6 of the full version that ideas using a greedy approach and local search method give us approximation algorithms, but only for very special cases. Namely, if the districts have rank-$k$, we can try the greedy maximum hypergraph matching to have a $k$-approximation to the optimal solution. When all weights are binary ($1$ or $0$), we can use a greedy algorithm with local search to get a $c$ approximation to the optimal $c$-balanced star districting solution. Similarly, if the graph has maximum degree $\mathrm{\Delta }$, we can get a $(\mathrm{\Delta }+\frac{1}{\mathrm{\Delta }})$-approximation for $c$-balanced star districting.

To really tackle the problem with arbitrary weights, for districts that are not limited by rank and graphs beyond constant bounded degree, we first examine what we can do with complete graphs or tree graphs – here the topology is made some of the simplest possible, and we would like to address the challenge from packing and balancedness. In this setting we can obtain FPTAS for both complete graphs and tree graphs (Section 5)– although the algorithm is much more involved due to the additional requirements of packing and connectivity (for tree graphs, as connectivity is trivial for complete graphs). Our FPTAS uses a dynamic programming technique that maintains one district’s possible weights and introduces a new prioritized trimming method to approximate weights while ensuring that the resulting district satisfies the $c$-balanced constraint and approximates the optimal weight. The FPTAS for the complete graph is later used as a subroutine for solving the relaxed LP formulation for other graph settings.

Beyond complete graphs and tree graphs, we develop a general framework (Section 4) that produce approximation algorithms for star districts on different types of graphs. All these algorithms start from a relaxed linear program where we formulate a variable $x_S$ for each potential balanced star district $S$, which can take non-integer values and for all districts that share the same vertex, the sum of their variables is at most $1$. Despite potentially exponentially many variables (and constraints in the dual program) that preclude standard solutions, we adapt the whack-a-mole framework [9], which can be seen as a lazy multiplicative weight update algorithm, on dual variables, and we design a “separation oracle” that selects a violating constraint in the dual program in time polynomial in $n$ and $1/\epsilon$ that can significantly improve the solution. Consequentially, the linear program can be solved in time polynomial in $n$ and $1/\epsilon$ up to any precision $1-\epsilon$ and the number of non-zero primal variables (i.e., the candidate balanced star districts) is also polynomial. Intriguingly, our separation oracle is based on our FPTAS on compute graphs for balanced districting.

Now we will round the fractional solution to an integer solution and in the process we may lose an approximation factor. We use a simple randomized rounding method where we sort the districts with non-zero values in decreasing order of total weight, and flip a coin with probability proportional to $x_S$ to include a potential district $S$, if $S$ does not overlap with any districts already included. In order to bound the loss of quality in the rounding process, we need to upper bound the correlation of the variables, namely, sum of $x_A\cdot x_B$ for all pairs of overlapping districts $A,B$. These are the (fractional) districts that have to be dropped due to conflict. To establish the approximation factor, we wish to bound the total sum of correlation by a factor multiplied with the total sum over all possible districts ${\sum }_S{x}_S$ – exactly the optimal LP solution. We show that this ratio is $O(\sqrt{n})$, which immediately gives an $O(\sqrt{n})$-approximate solution for star districts on a general graph. Notice that this is tight due to the hardness of approximation results.

Due to the strong motivation from political redistricting and resource allocation considering geographical proximity/constraints, the planar graph is of particular interest to us. One of the main technical contributions is a polylogarithmic-approximation algorithm for balanced star districting on planar graphs and related algorithms for minor-free graphs and outer planar graphs. For a planar graph we now adopt a balanced planar separator and use a divide-and-conquer analysis. Namely, we only need to analyze the overlapping districts with at least one of them including vertices in the separator. Now a crucial observation is, if we can partition the planar separator into $k$ 5-hop independent sets, then we can decompose the total sum of correlation by the independent sets – fix an 5-hop independent set $X$, two star districts that touch different vertices in $X$ are disjoint and star districts that share the same vertex in $X$ have their total district value bounded by $1$ due to the primal constraint. This allows us to upper bound the correlation term for the star districts touching the separator by a factor of $k$ of the sum of $x_S$ with districts $S$ on the separator. Recursively, this gives an $O(\log n)$ factor loss in the final approximation.

We remark that the above analysis asks for a new property of a balanced separator – one that can be decomposed into a small number of 5-hop independent sets (called a “scattering” separator) – and we do not care about the size of the separator. This is possible for a planar graph if we use the fundamental cycle separator, which is composed of two shortest paths, and thus at most $10$ $5$-hop independent sets. For a $H$-minor-free graph with $H$ as a graph of $h$ vertices, we show the existence of a similar separator, which can be decomposed into $O(h^2)$ 5-hop independent sets. Thus the final approximation ratio for $H$-minor-free graphs is $O(h^2\log n)$. For outer planar graphs, we can skip the recursive step and work with graph partitions with $5$-hop independent sets and get $O(1)$-approximation. We believe that this technique of using balanced scattering separators is interesting in its own and may find additional applications in other problems with some packing (non-overlapping) requirement on the solution.

On general graphs, the formulated linear program could have an integrality gap as large as $\mathrm{\Omega }(\sqrt{n})$. Since our rounding algorithm turns an fractional solution into an integral one, this barrier unavoidably blends into our analysis to the proposed rounding algorithm, producing an provable $O(\sqrt{n})$ bound. However, by thinking about this argument contrapositively, an upper bound to our rounding algorithm leads to the integrality gap of the formulated LP, which could be an interesting takeaway. On the other hand, we also show that there are planar graphs (specifically grid graphs) such that our rounding algorithm produces a $>1$ constant approximation ratio. This observation suggests that we cannot hope for a PTAS using this approach, even on planar graphs.

Our problem is connected to computational (re)districting for schools and elections, which dates back to the 1960s. [42] Since then, an extensive line of work (see [8] for a survey) has formulated the redistricting task as an optimization problem with a certain objective and constraints, e.g,. balancedness, contingency, or compactness. Our redistricting problem focuses on optimizing the population in balanced and contiguous districts. One concept related to our notion of balance is competitiveness. Recent work introduces vote-band metrics [30], which require a certain fraction of votes to fall within a specified range (e.g., 45-55%) for competitive elections. Subsequently, [22] also adopt similar notions called $\delta$-Vote-Band Competitive which is equivalent to our $c$-balancedness by setting $c=2/(1-2\delta )$. While related, our work diverges technically, offering both hardness and algorithmic results for several common graphs. [30] empirically evaluates ensemble methods for district distributions. [22] explored the hardness and heuristic algorithms for maximizing the number of districts meeting the target competitiveness constraints, with additional requirements that all districts have roughly the same population limited compactness consideration.

One approach treats contiguity as a transportation cost and designs linear programming models to minimize this total cost [1, 34, 24]. Interestingly, the fair clustering problem can also be viewed as optimizing contingency [12, 19, 44, 18]. Other research focuses on optimizing compactness scores [6, 45, 48, 43] or using Voronoi or power diagrams with some variant of $k$-means [57, 26, 27, 35]. Finally, another line of work optimizes balance scores [38]. These approaches differ from ours in that they treat specific aspects of districting (contiguity, compactness, balance, etc.) as objectives, rather than maximizing the population that meets these criteria.

Besides the optimization approach, another popular approach uses sampling to generate a distribution over districts and create a collection of district plans for selection. [3, 23] One widely used method is ReCom [31], an MCMC algorithm. However, these approaches may suffer from slow mixing times and lack formal guarantees. [51] Finally, several papers take a fair division approach [49, 53, 29]. The problem is quite different, however, as fairness 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.

Beyond districting problems, as outlined in the technical overview, our problem connects to several classical algorithm problems. If we only want to maximize the population of a single connected and balanced district, the problem becomes a balanced connected subgraph problem [10, 11, 50]. However, the previous work in this area typically considers unit weights for either type, which does not adequately represent the districting problem that operates in an aggregated block-level setting. Our problem can be seen as packing subgraphs on graph [28], e.g., edges (maximum matching), triangles [47], circles [32]. Finally, we note a line of work on a balanced, connected graph partition [17, 21], and balanced bin-packing problem [33], which, however, aim to generate a partition where each component has similar weights.

In order to solve the relaxed linear program of Equation 2, we use weighted variables: for each district $S$, we define variable $x_S^{\prime }:=w(S)x_S$. Hence, the equivalent linear program (and its dual linear program) we will be solving can be described as follows.

We note that the total number of primal variables (i.e., the number of potential $c$-balanced star districts) could be exponentially many in terms of the graph size. However, due to the special structure of this problem, seeking for an approximate solution does not require the participation of every variable. We summarize the result of solving the relaxed linear program as Theorem 6 below.

In order to have a polynomial time algorithm, we want an efficient separation oracle. The following lemma (Lemma 7) reduces the task of finding a violating district to solving the $c$-balanced star districting problem in a complete graph.

The output $I$ of the algorithm can be seen as a random variable. Let $w(I)$ be the total weight of the districts within $I$. A straightforward analysis (see Lemma 13) shows that

The right hand side of the above expression contains a weighted correlation term. The technique by Chan and Har-Peled [15] transforms the above weighted correlation terms into unweighted ones. They mentioned that, a desired $O(\tau )$-approximate solution can be achieved, as long as for any $\delta$-thresholded subset ${𝒮}_{\ge \delta }:=\{S\in {𝒮}_{\mathrm{LP}}|w(S)\ge \delta \}$, the total unweighted correlation terms between overlapped districts can be upper bounded by the sum over all primal variables within the subset:

The above condition implies the following (see Lemma 14):

where ${\mathrm{OPT}}_{\mathrm{LP}}$ is the optimal value of the LP problem. Thus, $I$ is an $O(\tau )$-approximate solution in expectation. We remark that due to the factor $2$ appearing in the denominator, this linear program with randomized rounding approach (although not contradicting) is unlikely to achieve a PTAS.

The above analysis to the rounding algorithm enables the approach of seeking a suitable $\tau$ value, such that Equation 3 holds. The rest of the section focuses on providing upper bounds of $\tau$ on various classes of input graphs.

We remark that this algorithm is achieving nearly the best approximation factor since it is $\mathrm{𝖭𝖯}$-hard to have approximation factor of $n^{1/2-\delta }$ for any constant $\delta >0$. Related to this, we would like to examine the potential loss in different steps of our algorithm. In the first step, we relax the integer linear program to a linear program with variables taking real numbers, the integrality gap refers to the ratio of the optimal fractional solution to the optimal integer solution (since we consider maximization problem the optimal fractional solution is no smaller than the optimal integer solution). In the second step of our algorithm, we use randomized rounding to turn the fractional solution back to a feasible integer solution. We call the ratio between the sum of products between overlapping districts’ primal variables and the sum of all variables to be the rounding gap, i.e., ${\sum }_{A,B:A\cap B\ne \mathrm{\varnothing }}{x}_A{x}_B/{\sum }_S{x}_S$. The rounding gap can be used to upper bound the loss of solution quality when we turn the fractional solution to a feasible integer solution using the randomized rounding algorithm.

Necessarily, a large integrality gap implies a large rounding gap for sure. Specifically, let $\tau$ be the rounding gap. The analysis to our rounding algorithm guarantees the existence of an integral solution within a factor of $4(1+\epsilon )\tau$ from the optimal fractional solution, which implies an integrality gap of at most $4\tau$ when setting $\epsilon \to 0$. Thus if the integrality gap is large, we cannot have a small rounding gap. Interestingly, the above discussion, combined with Lemma 8 implies that the integrality gap of the natural LP formulation for the star districting problem is at most $O(\sqrt{n})$.

Next we show that our LP relaxation could have a large integrality gap of $\mathrm{\Omega }(\sqrt{n})$ for a general graph. We use a reduction from $k$-uniform hypergraph matching problem to our $c$-balanced star districting problem. Let $H=(V_H,E_H)$ be the given $k$-uniform hypergraph – a hypergraph such that all its hyperedges have size $k$. We construct a graph $G=(V_H\cup E_H,E_G)$ by creating additional vertices for each hyperedge. These vertices have heavy weights, say $p_2(e):=(c-1)k$ and vertices from $V_H$ have weights $p_1(v):=1$. For each hypergraph $e\in E_H$ (which is a subset of vertices), we connect all vertices $v\in e$ to the corresponding vertex $e$ in $G$. It ensures that there is an one-to-one correspondence between hyperedges of $H$ to $c$-balanced star districts on $G$. Now, the relaxed linear program for $(G,p_1,p_2)$ will be equivalent (with an extra $ck$-factor in the objective function) to a fractional hypergraph matching. Thus, the $(k+1-1/k)$ integrality gap of $k$-uniform hypergraph matching [36, 16] can be transferred to our LP formulation – specifically, the construction in [16] via projective planes leads to an $\mathrm{\Omega }(\sqrt{n})$ integrality gap.

On the other hand, we do observe planar graph instances with a constant $>1$ rounding gap with an at most $1+o(1)$ integrality gap (refer the full version). Again, this does not eliminate the possibility of achieving PTAS, but it suggests a conjecture that we are unlikely to obtain a PTAS for planar graphs using the current analysis.

We note that this dynamic programming approach also works for star districts on tree graph and yields an FPTAS. Similar to the arbitrary districts setting, we consider three cases for each $v$: the absent case where $v$ is not included in any district; the consolidating where $v$ is in a star district that is contained in its descendants; the incomplete case where $v$ is the center of a star district that is incomplete.