Connected Low-Discrepancy Bipartitions via Partial Coloring and Cut & Count

Many partitioning tasks ask for two things that pull against each other. The first is that each part be connected, so that you can walk between any two of its vertices without leaving it. The second is that each part be balanced across several attributes at once. Examples include splitting a network into two self-contained halves with equal load, equal size, and equal counts of several node types. Balancing many attributes is exactly what discrepancy algorithms do well. These algorithms choose a +1/−1 sign for each element so that every attribute sums to nearly zero, and the best ones work by iterative partial coloring: they fix the signs of about half the remaining elements per round while keeping all attribute sums small. Discrepancy algorithms know nothing about connectivity, though. Enforcing connectivity exactly is what Cut & Count does well. Cut & Count is a dynamic program over a tree decomposition, a tree-shaped arrangement of small vertex sets called bags that covers the graph. It counts solutions modulo 2 in a way that cancels disconnected ones, and it avoids recording which bag vertices are joined to which. Its weakness here is that every attribute we want balanced adds a counter dimension to its table, so the table grows like $n^d$ for $d$ attributes on $n$ vertices.

We propose a hybrid in which partial coloring and Cut & Count each do the part they are good at. Partial coloring commits most vertices to a side while keeping the attribute imbalance small. A cheap Cut & Count check, which ignores balance, vetoes any commitment that would make a connected completion impossible. An exact Cut & Count dynamic program with full balance counters then finishes the few vertices left uncolored. The counters only need to range over the uncolored vertices' contribution, so after $t$ rounds the table shrinks from roughly $n^d$ to $(n/2^t)^d$. This brings multi-attribute connected balancing on low-treewidth graphs within reach of exact search. There is a second payoff. The error of Cut & Count is one-sided: it can wrongly say "no completion exists" but never wrongly say "yes". A veto therefore never lets an infeasible commitment through, and the randomness costs only wasted reverts, never a wrong answer.

Problem and Core Claim

The input is a graph $G=(V,E)$ of treewidth $\mathrm{tw}$ and a vector $a_v \in \{-1,0,1\}^d$ at each vertex, one coordinate per attribute. The attributes could be supply or demand, node type, or a constant 1 for size. We seek $V = V_1 \cup V_2$ with $G[V_1]$ and $G[V_2]$ both connected, minimizing

$$\mathrm{disc}(V_1,V_2) = \Big\| \sum_{v\in V_1} a_v - \sum_{v \in V_2} a_v \Big\|_\infty ,$$

the largest imbalance across the $d$ attributes. For $d=2$ (one supply coordinate plus size), this is the doubly balanced connected partitioning problem. Doubly Balanced Connected Graph Partitioning solves that problem in polynomial time, but only on 2- and 3-connected graphs, using convex embeddings and $st$-numberings. Those tools break down on graphs with cut vertices, and the paper leaves low-treewidth graphs and more attribute types open. This work motivates ours: it shows the problem is natural and marks exactly where geometric methods stop.

Our claim has two parts. First, a two-sided Cut & Count solves the problem exactly in about $4^{\mathrm{tw}}$ bag states times the counter range. Second, iterative partial coloring with connectivity vetoes shrinks that counter range enough to make $d$ between 3 and 8 practical. Empirically, the hybrid should reach discrepancy close to the exact optimum where the optimum can be computed. At larger scales, it should beat both connectivity-first heuristics and discrepancy-first methods followed by repair.

Research Program

The first component is a two-sided counting lemma. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time supplies the method. For one subgraph $H$ with $c(H)$ components and a fixed marker vertex, $H$ has exactly $2^{c(H)-1}$ consistent cuts (splits of $H$'s vertices into left and right with no edge of $H$ crossing). This count is odd exactly when $H$ is connected.

We give each vertex one of four labels: left or right within $V_1$, or left or right within $V_2$. Each side gets its own marker. Because $V_1$ and $V_2$ partition $V$, the number of consistent label pairs factors as $2^{c(V_1)-1}\cdot 2^{c(V_2)-1}$. This product is odd iff both sides are connected, and there are no cross terms. The research file notes that simultaneous connectivity of both sides has not been formulated in this literature. The lemma itself is easy; its role is to make the pipeline exact.

To stop valid solutions from cancelling in pairs, we use the Isolation Lemma: random weights make the minimum-weight solution unique with good probability. We apply it with the Cut & Count weight dimension, as in the original paper and as reused for acyclic matchings in P-Matchings Parameterized by Treewidth. The balance vector is tracked as additional table coordinates.

The second component is connectivity-vetoed partial coloring, which supplies the discrepancy side. We run a random-walk partial coloring in the style of Fast Discrepancy Minimization with Hereditary Guarantees on the $d\times n$ attribute matrix. Larsen's algorithm first projects away heavy directions (ProjectToSmallRows) and then walks inside the cube until half the coordinates reach ±1.

Before each round's commitments become final, we run the balance-free two-sided Cut & Count. That check has only $4^{\mathrm{tw}}$ states times the weight range, and it asks whether a connected completion still exists. If the answer is no, we revert half of the batch and retry, a binary search over the batch. Because errors are one-sided, a "yes" is always correct, so every committed state is feasible. After $T$ rounds, or once the uncolored set $U$ drops below a budget $n_{\mathrm{res}}$, a final exact two-sided Cut & Count runs with committed vertices as hard constraints. Its counters range over $[-|U|,|U|]^d$. That residual solve is exact over all connected completions of the committed part.

The theory we aim for is modest and honest. Without vetoes, Larsen's analysis bounds the committed imbalance by $O(\lg n\cdot \lg^{3/2} m \cdot \mathrm{herdisc})$. Reverts break that guarantee. We will state and try to prove a bound in terms of the number of reverted vertices, and we will measure empirically how often vetoes fire.

The main open analytical question is whether committing only vertices far from the current cut boundary makes vetoes provably rare. Such vertices are, for example, those whose committed neighbors already lie on the same side. The dynamic edge-coloring work of Nibbling at Long Cycles and the nibble literature it builds on constrain this design. That work handles only local constraints by discarding conflicting tentative choices, and the file finds no nibble variant that guarantees global connectivity. Our veto is precisely a global check inserted between nibble rounds, and it pays a treewidth-exponential cost that local nibbling avoids.

Baselines

The ground-truth reference is the full exact two-sided Cut & Count with counters over the whole range $[-n,n]^d$. It uses the same implementation, the same tree decompositions, and the same random weights as the hybrid. It is the strongest possible competitor in solution quality because it is optimal. It will be run on every instance where it fits in a fixed memory budget, typically $d\le 3$ and moderate $n$. There, the hybrid "beats" it if it matches its discrepancy within one unit on at least 90% of instances at an order of magnitude less time or memory. No reported result was found on Lacuna for exact connected balanced bipartition on bounded treewidth, so these numbers will be produced by us.

The deterministic alternative is standard partition-tracking dynamic programming. It records which bag vertices are connected, at a cost of Bell-number many states, about $2^{\Theta(\mathrm{tw}\log\mathrm{tw})}$ per Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. It will be run with identical counters. This comparison isolates the value of Cut & Count and settles whether its randomization is worth it at practical treewidths.

The naive reference point is connectivity-first sampling. We draw a uniformly random spanning tree, cut the edge whose removal gives the smallest imbalance, and repeat for the same wall-clock time as the hybrid, keeping the best result. This mirrors Larsen's comparison against "multiple random samples run for the same duration". We add a local-search variant that moves boundary vertices while preserving connectivity, with an identical time budget.

The strongest discrepancy-first competitor is Larsen's partial coloring run to completion with connectivity ignored, followed by the same exact residual repair used in the hybrid. Larsen reports on $4000\times4000$ uniform, corner, and halfspace matrices that this algorithm yields discrepancies "roughly 10 times smaller than a single random sample and 4 times smaller than multiple random samples run for the same duration" (Fast Discrepancy Minimization with Hereditary Guarantees). Its unconstrained discrepancy also serves as a lower reference: the gap between it and any connected solution measures the price of connectivity.

For $d=2$ on 2- and 3-connected instances, the method of Doubly Balanced Connected Graph Partitioning is included. Its guarantees are $c_p=0, c_s=1$ in 3-connected graphs and $c_p=1, c_s=3$ in 2-connected graphs; the paper gives no empirical numbers. The hybrid should match it where it applies.

The key ablation replaces the discrepancy walk with random commitment of the same fraction of vertices per round. Vetoes and the residual solve stay identical. If this ablation matches the hybrid, the partial-coloring ingredient contributes nothing, and the whole contribution reduces to "commit randomly, then solve exactly".

Why not just…?

Why not just run the exact Cut & Count with full balance counters? For $d\le 2$ this is probably the right answer, and we will say so if the data agree. The table grows like $(2n+1)^d$ per state, however, so at $d=4$ and a few thousand vertices it cannot be stored. The exact baseline runs on every instance where it fits. The crossover point in $d$ and $n$ is itself one of our reported results.

Why not just balance with a discrepancy algorithm and then repair connectivity? This is the most serious threat. On graphs where both sides of good low-discrepancy colorings are nearly connected, repair may be cheap. On sparse or tree-like graphs, it may require recoloring many vertices, and each recoloring moves the imbalance. The discrepancy-first baseline uses our own exact residual repair, so the only difference from the hybrid is when connectivity is enforced. If it matches the hybrid, we will conclude that interleaved vetoes are unnecessary.

Why not just sample random connected partitions or run local search? Larsen's measurements show that same-time random sampling loses to partial coloring by a factor of about 4 on unconstrained balance. It is plausible, but untested, that the gap widens as $d$ grows, because random splits balance each attribute only to about $\sqrt{n}$. Our time-matched sampling and local-search baselines, tracked across $d$, test this directly.

Proposed Experiments

The file contains no connected-partitioning benchmark with reported numbers, so we build one from its resources. Graphs come from the PACE treewidth instances, for which no reported number was found on Lacuna in this setting. We add synthetic low-treewidth families: grids of width 4 to 12, series-parallel graphs, and random partial $k$-trees with many cut vertices. The cut vertices are the regime where the embedding methods fail.

Attribute vectors come from three sources. We draw uniform ±1 entries, as in Larsen's uniform matrices. We also derive attributes from his corner and halfspace constructions by placing vertices at random points in the unit square. These families have known hereditary discrepancy of $O(\log^{2.5} n)$ and $O(n^{1/4})$ respectively, which gives a sense of the achievable scale.

We sweep $d \in \{1,\dots,8\}$, $n$ up to $10^4$, and treewidth up to about 10. For each setting we report achieved discrepancy, gap to the exact optimum where it is computable, gap to the unconstrained discrepancy of Larsen's walk, wall-clock time, peak memory, and veto and revert rates.

Three checks decide the proposal. First, on instances where the exact baseline runs, the hybrid must stay within one unit of optimum on most instances while using at least ten times less memory. Otherwise the pruning costs too much quality. Second, the random-commitment ablation must be measurably worse than the discrepancy walk, especially as $d$ grows. Otherwise partial coloring is not doing the work. Third, the discrepancy-first-then-repair baseline must lose on tree-like graphs with cut vertices. Otherwise interleaving the connectivity check is unnecessary. If revert rates stay low on those graphs, that also supports the conjecture that commitments away from the boundary rarely need vetoing, which is the analysis we would then try to prove.