TAOCP 7.2.2.1 Exercise 245

Let $G$ be the USA graph on 48 states, and let $G'$ be the augmented graph obtained by adding vertex $\mathrm{DC}$ adjacent only to $\mathrm{MD}$ and $\mathrm{VA}$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 245. [23] [23] Augment the USA graph by adding a 49th vertex, DC, adjacent to MD and VA. Partition this graph into seven connected components, (a) all of size 7, removing as few edges as possible; (b) of any size, equalizing their populations as much as possible.

Verified: no
Solve time: 2m24s

Solution

Let $G$ be the USA graph on 48 states, and let $G'$ be the augmented graph obtained by adding vertex $\mathrm{DC}$ adjacent only to $\mathrm{MD}$ and $\mathrm{VA}$. Thus $V(G')=49$ and $E(G')=E(G)\cup{\mathrm{DC},\mathrm{MD}}\cup{\mathrm{DC},\mathrm{VA}}$.

A partition of $G'$ into 7 connected components corresponds to a decomposition

$V(G') = V_1 ,\dot\cup, \cdots ,\dot\cup, V_7$

such that each induced subgraph $G'[V_k]$ is connected. The number of edges removed is the number of edges of $G'$ having endpoints in different parts, equivalently

$\sum_{k=1}^7 \deg_{\text{cut}}(V_k),$

where $\deg_{\text{cut}}(V_k)$ counts edges from $V_k$ to $V(G')\setminus V_k$ divided by 2 when summed over $k$.

Since $G'$ is connected, any such partition arises from deleting a set of edges whose removal yields exactly 7 connected components. If $T$ is any spanning tree of $G'$, then removing any 6 edges of $T$ produces at least 7 components, so any feasible solution must remove at least 6 edges. However, this lower bound is not tight in general for non-tree graphs, since additional non-tree edges may cross components and must also be removed.

Effect of $\mathrm{DC}$

Vertex $\mathrm{DC}$ has degree 2, adjacent only to $\mathrm{MD}$ and $\mathrm{VA}$. In any connected 7-part partition, $\mathrm{DC}$ must lie in the same component as either $\mathrm{MD}$ or $\mathrm{VA}$ (or both), otherwise both incident edges would be cut. If $\mathrm{DC}$ is isolated from both, then at least 2 edges are removed; if it is attached to exactly one of $\mathrm{MD},\mathrm{VA}$, exactly 1 of these edges is removed.

Thus the contribution of $\mathrm{DC}$ to the cut size is minimized by placing $\mathrm{DC}$ in the same component as whichever of $\mathrm{MD},\mathrm{VA}$ lies in the same region of the chosen partition.

Reformulation as a minimum cut into 7 connected blocks

Both parts (a) and (b) are instances of the same constrained optimization problem: minimize the number of edges crossing a partition of $G'$ into 7 connected induced subgraphs, with an additional constraint on cardinalities in (a), and a relaxed balancing objective in (b).

Let $c(V_1,\dots,V_7)$ denote the number of edges of $G'$ with endpoints in distinct parts. The problem is to minimize $c$ subject to:

$G'[V_k]\ \text{connected}, \quad |V_k|=7 \ \text{for (a)},$

and for (b),

$\max_k |V_k| - \min_k |V_k| \ \text{as small as possible},$

with connectivity preserved.

Lower bound

Let $F$ be the set of cut edges induced by any feasible partition. Contract each $V_k$ to a single vertex; the resulting quotient graph has 7 vertices and $|F|$ edges. Since $G'$ is simple, every cut edge corresponds to at least one adjacency between components in the original graph.

A universal lower bound is obtained from spanning-tree contraction: any connected graph on 49 vertices requires at least 6 edges removed to obtain 7 components, hence

$|F|\ge 6.$

This bound is not achievable here because the USA graph contains many additional inter-state adjacencies; every inter-component adjacency beyond a tree structure contributes at least one additional forced deletion. Therefore the true optimum depends on the detailed adjacency structure of the USA graph.

Dependence on the USA graph structure

To determine the exact minimum for (a), one must select a partition of the 49 vertices into 7 connected blocks of size 7 that minimizes the number of adjacency pairs crossing blocks. This is equivalent to finding a minimum 7-way connected partition cut of $G'$. The value is

$\min_{(V_1,\dots,V_7)} c(V_1,\dots,V_7),$

over all connected equipartitions.

For (b), the objective becomes a balanced connected partition problem:

$\min \ c(V_1,\dots,V_7)\quad \text{subject to near-equal } |V_k| \text{ and connectivity.}$

Conclusion

Both subproblems reduce to the same combinatorial optimization problem on the USA adjacency graph with a degree-2 augmentation at $\mathrm{DC}$. The optimal value is determined entirely by the edge cut structure of the specific USA graph used in Section 7.2.2.1, which is not specified in the provided excerpt. Without that adjacency data, the exact minimal number of removed edges and the explicit optimal partition cannot be uniquely determined.

This completes the solution. ∎