TAOCP 7.2.2.1 Exercise 77

The original construction fails because it encodes whole mappings as single options and implicitly enumerates all embeddings.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.1: Dancing Links

Exercise 77. [M21] [M21] Given graphs $G$ and $H$, each with $n$ vertices, use Algorithm X to decide whether or not $G$ is isomorphic to a subgraph of $H$. (In such a case we say that $G$ is embedded in H.)

Verified: yes
Solve time: 2m35s

The original construction fails because it encodes whole mappings as single options and implicitly enumerates all embeddings. A correct reduction must build an exact cover instance whose size is polynomial in $n$ and whose options are local, not global.

A standard way to achieve this is to represent an embedding as a bijection between vertex sets together with local consistency constraints enforced by shared secondary items.

Correct solution

Let $G = (V_G, E_G)$ and $H = (V_H, E_H)$ be graphs with

$$ V_G = {u_1,\dots,u_n}, \quad V_H = {v_1,\dots,v_n}. $$

We decide whether $G$ is isomorphic to a subgraph of $H$, i.e., whether there exists a bijection $f : V_G \to V_H$ such that

$$ (u_i,u_k) \in E_G ;\Rightarrow; (f(u_i), f(u_k)) \in E_H. $$

We construct an instance of Algorithm X (exact cover with primary and secondary items) as follows.

Items

Primary items (bijection constraints)

We enforce that every vertex of $G$ is assigned exactly one vertex of $H$, and every vertex of $H$ is used exactly once.

  • For each $u_i \in V_G$, create a primary item $R_i$.
  • For each $v_j \in V_H$, create a primary item $C_j$.

Thus:

$$ {R_1,\dots,R_n} \cup {C_1,\dots,C_n} $$

are primary items.

Secondary items (edge compatibility constraints)

For each edge $(u_i,u_k) \in E_G$ and each pair $(v_j,v_\ell) \notin E_H$, introduce a secondary item

$$ F_{i,k,j,\ell}. $$

Intuitively, this item represents the forbidden situation “$u_i \mapsto v_j$ and $u_k \mapsto v_\ell$ simultaneously when that would violate adjacency”.

Options

For each possible assignment $u_i \mapsto v_j$, define an option $A_{i,j}$.

Items covered by $A_{i,j}$

Each option includes:

  • Primary items:

$$ R_i, \quad C_j $$

  • Secondary items:

For every edge $(u_i,u_k) \in E_G$ and every vertex $v_\ell \in V_H$ such that $(v_j,v_\ell) \notin E_H$, include

$$ F_{i,k,j,\ell}. $$

Similarly, for every edge $(u_k,u_i) \in E_G$ and every $v_\ell$ with $(v_\ell,v_j) \notin E_H$, include the corresponding item (to handle symmetry if graphs are undirected).

Thus each option records all forbidden pairwise interactions involving the assignment $u_i \mapsto v_j$.

Why this works

1. Exact cover forces a bijection

Because:

  • Each $R_i$ appears only in options $A_{i,j}$, exactly one such option must be chosen for each $i$. So every $u_i$ is assigned exactly one image.
  • Each $C_j$ appears only in options $A_{i,j}$, so exactly one $u_i$ maps to each $v_j$.

Hence the chosen options define a bijection $f : V_G \to V_H$.

2. Edge preservation is enforced

Suppose $f(u_i) = v_j$ and $f(u_k) = v_\ell$, where $(u_i,u_k) \in E_G$.

If $(v_j,v_\ell) \notin E_H$, then the secondary item $F_{i,k,j,\ell}$ is included in both options $A_{i,j}$ and $A_{k,\ell}$.

Since Algorithm X requires each item to be covered exactly once, these two options cannot both be selected.

Therefore no chosen bijection can map an edge of $G$ to a non-edge of $H$.

Conversely, if $(v_j,v_\ell) \in E_H$, no conflicting item is introduced, so the assignment is allowed.

Thus adjacency in $G$ implies adjacency in $H$ under the selected bijection.

3. Correctness equivalence

  • If a subgraph embedding $f$ exists, selecting all $A_{i,f(i)}$ yields a valid exact cover:

  • Primary items are covered exactly once by bijectivity.

  • No forbidden secondary item is doubly covered because $f$ preserves edges.

  • If an exact cover exists, the selected options define a bijection $f$ and the secondary items guarantee that every edge of $G$ maps to an edge of $H$.

Hence solutions of the exact cover instance are in one-to-one correspondence with embeddings of $G$ into $H$.

Complexity

  • Primary items: $2n$.
  • Options: $n^2$.
  • Secondary items: at most $O(n^2 \cdot |E_G|)$, since for each edge in $G$ we add items over non-edges of $H$.

Thus the construction is polynomial in $n$.

Conclusion

We have constructed in polynomial time an exact cover instance such that Algorithm X finds a solution if and only if $G$ is isomorphic to a subgraph of $H$. This yields a valid reduction. ∎