## 5 Imbalance-Inducing Postprocessing
### Dynamic Program to Optimize Cuts  
The partitioning problem becomes more tractable if we fix an ordering \(\pi\) of vertices and insist on each partition consisting of consecutive vertices (perhaps, with wrap-around). Let us for now assume that no wrap-around is permissible; that is, each part corresponds to a contiguous subset of vertices on \(\pi\). In the dynamic programming (DP) framework, instead of solving the given instance, we solve several instances (all based on the input and closely related to one another) and do so in a carefully chosen sequence such that the instances already solved make it easier to quickly solve newer instances, culminating in the solution to the real instance. Let \(A_{i,j,q}\) for \(1\leq i,j\leq n,1\leq q\leq k,j\geq i-1\) denote the smallest cut size achievable for the subgraph induced by vertices \(\pi(i\to j)\) if exactly \(q\) partitions thereof are desired. Once all these entries are computed, \(A_{1,n,k}\) yields the solution to the original problem. As is customary in dynamic programs, we only discuss how to find the \"cost\"--here, the cut size--of the optimal solution; finding the actual solution--here, the partition--can be achieved in a straight-forward manner by adding certain information to the DP table. We fill in the table \(A_{i,j,q}\) in the order of increasing \(q\). For the case of \(q=1\), we clearly have \(A_{i,j,q}=0\) if and only if  
\[w(\pi(i\to j))\leq(1+\alpha)\frac{w(V)}{k},\]  
that is, vertices \(\pi(i\to j)\) can be placed in one part without violating the balanced property. Otherwise, it is defined as infinity. We use a recursive formula to compute \(A_{i,j,q}\) for \(q>1\). The formula depends on \(A_{i^{\prime},j^{\prime},q^{\prime}}\) entries where \(q^{\prime}<q\), hence these entries have all been already computed. Let us introduce some notation before presenting the recurrence. We define \(C(i,j,k)\) as the total length of edges going from \(\pi(i\to j)\) to \(\pi(j+1\to k)\). We now present the recursive formula for computing \(A_{i,j,q}\) as  
\[A_{i,j,q}=\min_{i-1\leq k\leq j}\left[A_{i,k,1}+A_{k+1,j,q-1}+C(i,k,j)\right]. \tag{2}\]  
Notice that the first term in the minimization is only used to signify whether \(\pi(i\to k)\) is a valid part in the intended \(\alpha\)-balanced partition: its value is either zero or infinity. **Lemma 1**. : _Equation (2) is a valid recursion for \(A_{i,j,q}\), which coupled with the initialization step given above yields a sound computation for all entries in the DP table._  
Proof. : The argument proceeds by mathematical induction. The initialization step is clearly sound as it is simply verifying feasibility of single parts. For the inductive part, it suffices to show that the best solution with a part \(\pi(i\to k)\) has a cut size \(A_{i,k,1}+A_{k+1,j,q-1}+C(i,k,j)\). Then, the first term in (2) accounts for the case when we use one empty part (i.e., we partition \(\pi(i\to j)\) using only \(q-1\) parts) and the minimization considers the cases when the first part consists of \(\pi(i\to k)\). To see the cost of the latter is as in (2), notice that any cut edge in the partition of \(\pi(i\to j)\) is either completely inside \(\pi(i\to k)\) (i.e., not contributing to the cut size), inside \(\pi(k+1\to j)\) (which is accounted for in \(A_{k+1,j,q-1}\) or connects \(\pi(i\to k)\) to \(\pi(k+1\to j)\) (in which case is taken into account by \(C(i,k,j)\)). The above procedure can be implemented to run in time \(O(n^{3}k)\) and consume space \(O(n^{2}k)\). Next we show how to improve this further. See Algorithm 4. The key idea is to avoid computing \(A_{i,j,q}\) for all values \(1\leq q\leq k\). Rather we focus on a limited subset of such \(q\)'s of size \(O(\log k)\).