TAOCP 7.2.2.1 Exercise 77
Let G=(V,E),\qquad H=(W,F), with
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: no
Solve time: 3m05s
Solution
Let
$$ G=(V,E),\qquad H=(W,F), $$
with
$$ |V|=|W|=n. $$
We construct an exact cover instance whose solutions correspond to embeddings of $G$ in $H$. The construction uses primary items and secondary items in the sense of Algorithm X. Every primary item must be covered exactly once, while every secondary item may be covered at most once.
For each vertex $v\in V$, introduce a primary item
$$ A_v . $$
For each vertex $w\in W$, introduce a primary item
$$ B_w . $$
The purpose of these items is to force a chosen solution to assign every vertex of $G$ to exactly one vertex of $H$, and to use every vertex of $H$ exactly once.
Now consider a possible assignment
$$ (v,w)\in V\times W . $$
For every such pair we create one option initially containing the two primary items
$$ {A_v,B_w}. $$
It remains to prevent the simultaneous choice of assignments that do not preserve edges.
Suppose
$$ {u,v}\in E $$
but
$$ {x,y}\notin F . $$
Then the two assignments
$$ (u,x),\qquad (v,y) $$
cannot both occur in an embedding. For every unordered pair of incompatible assignments
$$ {(u,x),(v,y)}, $$
introduce a secondary item
$$ C_{(u,x),(v,y)} . $$
Add this secondary item to the two corresponding options. Thus the option for $(u,x)$ contains
$$ C_{(u,x),(v,y)}, $$
and the option for $(v,y)$ contains the same secondary item.
The same construction is made for every pair of assignments that would violate the edge condition. No other secondary items are introduced.
We now show that the exact covers of this instance are precisely the embeddings of $G$ in $H$.
First suppose that an exact cover is given. Because every primary item $A_v$ must be covered exactly once, exactly one option corresponding to a pair
$$ (v,w) $$
is selected for each $v\in V$. Therefore the selected options define a function
$$ \phi:V\rightarrow W . $$
Because every primary item $B_w$ must also be covered exactly once, every vertex of $W$ occurs exactly once as an image. Since
$$ |V|=|W|=n, $$
the function $\phi$ is a bijection.
It remains to verify that $\phi$ preserves edges. Suppose that
$$ {u,v}\in E . $$
Assume, for contradiction, that
$$ {\phi(u),\phi(v)}\notin F . $$
Then the two selected assignments
$$ (u,\phi(u)),\qquad (v,\phi(v)) $$
are an incompatible pair. By construction, both of their options contain the same secondary item
$$ C_{(u,\phi(u)),(v,\phi(v))}. $$
Hence the exact cover would cover this secondary item twice, which is forbidden. Therefore
$$ {\phi(u),\phi(v)}\in F . $$
Thus
$$ {u,v}\in E\implies {\phi(u),\phi(v)}\in F, $$
so $\phi$ is an embedding of $G$ in $H$.
Conversely, suppose that $G$ is embedded in $H$. Let
$$ \phi:V\rightarrow W $$
be such an embedding. Choose the option corresponding to each assignment
$$ (v,\phi(v)) $$
for $v\in V$.
Every primary item $A_v$ is covered once because exactly the option for $v$ is chosen. Every primary item $B_w$ is covered once because $\phi$ is a bijection.
It remains to check the secondary items. A secondary item was created only for an incompatible pair of assignments. If some secondary item
$$ C_{(u,x),(v,y)} $$
were covered twice, then both assignments
$$ (u,x),\qquad (v,y) $$
would have been selected. By construction, these assignments violate the embedding condition. This contradicts the assumption that the selected assignments come from the embedding $\phi$. Therefore every secondary item is covered at most once.
Hence the chosen options form a valid exact cover.
The construction can be generated directly from $G$ and $H$: it requires only considering all possible vertex assignments and all pairs of assignments that violate the edge-preservation condition. Algorithm X applied to this exact cover instance searches through possible collections of assignments. It succeeds exactly when there is a collection giving a bijection $\phi:V\rightarrow W$ that preserves all edges.
Therefore Algorithm X decides whether $G$ is isomorphic to a subgraph of $H$. ∎