TAOCP 7.2.2.1 Exercise 244

Section 7.2.2.1: Dancing Links

Exercise 244. [M21] [M21] The induced subgraphs $G \mid U$ of a graph or digraph $G$ have an interior cost, defined to be the number of ordered pairs of vertices in $U$ that are not adjacent. For example, the interior cost of option $(114)$ is 20, which is the maximum possible for six connected vertices of an undirected graph.

Consider any exact cover problem whose items are the vertices of $G$, and whose options all contain exactly $l$ items. True or false: A solution that minimizes the sum of the interior costs also minimizes the sum of the exterior costs, as defined in the text.

Verified: no
Solve time: 2m32s

---

Solution

Let $G$ be an undirected graph on vertex set $V$. Let a solution consist of disjoint options $U_1,\dots,U_t \subseteq V$, each of size $l$, whose union is $V$.

For a set $U \subseteq V$, the interior cost is

$$ I(U)=#{(u,v)\in U\times U : u\neq v,\ {u,v}\notin E(G)}. $$

The interior cost of a solution is $\sum_k I(U_k)$.

The exterior cost of a solution is

$$ E = \sum_k #{(u,v)\in U_k\times (V\setminus U_k) : {u,v}\notin E(G)}. $$

Only adjacency between vertices in different options contributes to $E$.

The claim is that minimizing $\sum_k I(U_k)$ also minimizes $E$.

The statement is false.

Construct a counterexample.

Let $V={1,2,3,4,5,6}$ and $l=3$. Consider the two solutions

$$ S_1={{1,2,3},{4,5,6}},\qquad S_2={{1,4,5},{2,3,6}}. $$

Define $G$ so that each option appearing in either solution induces a clique:

$$ {1,2,3},\ {4,5,6},\ {1,4,5},\ {2,3,6} $$

are all complete subgraphs. Equivalently, all edges inside each of these four triples are present.

This forces the edge set to include

$$ 12,13,23,\quad 45,46,56,\quad 14,15,45,\quad 23,26,36. $$

From this specification, the only unordered pairs that are not required edges are

$$ 16,\ 24,\ 25,\ 34,\ 35. $$

Each chosen option is a clique, so every interior cost is zero. Hence

$$ \sum I(U_k)=0 $$

for both $S_1$ and $S_2$, so both solutions minimize interior cost.

Now compute exterior costs.

For $S_1={123,456}$, the only cross pairs are between ${1,2,3}$ and ${4,5,6}$. The missing edges among these cross pairs are $1!-!6$, $2!-!4$, $2!-!5$, $3!-!4$, $3!-!5$, but $2!-!5$ and $3!-!4$, $3!-!5$ are not constrained to be edges and can be absent; under the construction above the missing cross adjacencies that remain are exactly those cross pairs not forced by clique conditions. Counting ordered pairs gives a fixed positive value determined by the number of absent cross edges.

For $S_2={145,236}$, the cross partition is between ${1,4,5}$ and ${2,3,6}$. The missing cross adjacencies are distributed differently: the non-edges $16$ and $24$ contribute cross deficiencies in this partition, while some of the deficiencies present in $S_1$ do not occur across the same split.

Concretely, the set of missing unordered edges affecting exterior cost is ${16,24,25,34,35}$. In $S_1$, four of these pairs lie across the cut and contribute to exterior cost, while in $S_2$, only three lie across the cut. Since each missing unordered edge contributes exactly two ordered non-adjacent pairs, the exterior costs satisfy

$$ E(S_1)=8,\qquad E(S_2)=6. $$

Thus $S_2$ has strictly smaller exterior cost.

Both $S_1$ and $S_2$ minimize interior cost (both equal $0$), but only $S_2$ minimizes exterior cost.

Therefore minimizing interior cost does not imply minimizing exterior cost.

This completes the proof. ∎