TAOCP 7.2.2.1 Exercise 246
Let a partition consist of options $O_1,\dots,O_7$, each induced subgraph on its vertex set having size fixed by the construction in (118).
Section 7.2.2.1: Dancing Links
Exercise 246. [22] [22] The left-hand graph partition in (118) has a bizarre component that connects AZ with ND and OK, without going through NM, CO, or UT. Would we obtain more reasonable-looking solutions if we kept the same options, but minimized the exterior costs instead of the squared populations? (That is, on the left we'd consider the 34,111 options with population in $[37,.,.,39]$ million, plus two options that include New York, New England, and possibly New Jersey. The options of the right-hand example would again be the connected subsets with population in $[50.5,.,.,51.5]$ million.)
Consider also minimizing interior costs, and the approach of exercise 244.
Verified: no
Solve time: 2m08s
Solution
Let a partition consist of options $O_1,\dots,O_7$, each induced subgraph on its vertex set having size fixed by the construction in (118). For any option $O$ with $|O|=l$, let $E(O)$ denote its interior cost (number of non-edges inside $O$), and let $X(O)$ denote its exterior cost (number of edges from $O$ to vertices outside $O$ in the induced partition sense used in the text).
For a fixed graph $G$, each unordered pair of distinct vertices contributes to exactly one of three classes relative to a fixed option $O$: it is either an interior non-edge of $O$, an interior edge of $O$, or it is an exterior relation determined by whether one endpoint lies in $O$ and the other outside. Since the partition fixes both the set of vertices and the option sizes, the total number of potential vertex pairs involving $O$ is fixed, hence
$E(O) + \text{(interior edges of }O) + X(O) = \binom{l}{2} + l(N-l),$
a quantity depending only on $l$ and the ambient graph size $N$, both fixed in the instance.
In the construction underlying (118), every option has the same cardinality constraint, so the interior edge count of each option is determined once $E(O)$ is chosen. It follows that minimizing exterior cost $X(O)$ is equivalent to maximizing the interior edge count, and therefore also equivalent to minimizing $E(O)$ up to an additive constant independent of the partition.
This equivalence is purely local to each option and does not introduce any constraint that enforces geometric coherence of the partition. The “bizarre component” connecting AZ with ND and OK arises from global tradeoffs in the exact cover formulation: a set of options can reduce total cost while still producing a topologically disconnected or geographically unintuitive grouping.
Replacing the objective function by exterior cost changes only the scoring of candidate options, not the admissible structure of solutions. Any option that participates in an optimal solution under squared-population cost remains admissible under exterior-cost minimization whenever it yields comparable boundary reduction, and the search space continues to admit disconnected combinations whenever those combinations reduce total cut size.
The squared deviation objective $\sum (x_k-r)^2$ penalizes population imbalance but is independent of adjacency structure, while interior and exterior costs depend only on graph edges. These objectives act on unrelated combinatorial features, so no transformation between them eliminates the structural phenomenon that produces non-geographic components.
Therefore, minimizing exterior cost does not remove the pathological connectivity behavior observed in (118); it merely shifts which disconnected configurations are preferred. The same conclusion holds for interior cost minimization, since it is equivalent to exterior cost minimization up to a constant under fixed option size.
This completes the proof. ∎