TAOCP 7.2.2.2 Exercise 390

Exercise 390. [23] Let $G$ be a graph with vertices $V$, edges $E$, $|E| = m$, $|V| = n$, and $s, t \in V$.

a) Construct $O(kn)$ clauses that are satisfiable if and only if there's a path of length $k$ or less from $s$ to $t$, given $k$.
b) Construct $O(m)$ clauses that are satisfiable if and only if there's at least one path from $s$ to $t$.
c) Construct $O(n^2)$ clauses that are satisfiable if and only if $G$ is connected.
d) Construct $O(kn)$ clauses that are unsatisfiable if and only if there's a path of length $k$ or less from $s$ to $t$, given $k$.

e) Construct $O(m)$ clauses that are unsatisfiable if and only if there's at least one path from $s$ to $t$. f) Construct $O(m)$ clauses that are unsatisfiable if and only if $G$ is connected. (This construction is much better than (c), in a sparse graph.)

Verified: no
Solve time: 4m06s

Solution

The definition of embedding gives a direct way to express several graph problems. If $H$ is embedded in $G$, every vertex of $H$ is assigned to a distinct vertex of $G$, and every edge of $H$ must be mapped to an edge of $G$. Thus the source graph specifies the required pattern of adjacencies, and the target graph specifies where that pattern may occur.

For the $k$-clique problem, let $K_k$ denote the complete graph on $k$ vertices. A graph $G$ contains a $k$-clique precisely when there are $k$ vertices of $G$ such that every pair of them is adjacent. An embedding of $K_k$ in $G$ chooses $k$ distinct vertices of $G$, and because every pair of vertices of $K_k$ is connected by an edge, their images must be pairwise adjacent in $G$. Therefore an embedding of $K_k$ in $G$ is exactly a $k$-clique of $G$. Hence

$$ G\text{ contains a }k\text{-clique}\iff K_k\text{ is embedded in }G. $$

For the $k$-colorability problem, let $n=|V(G)|$. Construct a target graph $H$ consisting of $k$ disjoint independent sets, each containing $n$ vertices, with every vertex in one part adjacent to every vertex in every other part. In other words, $H$ is the complete $k$-partite graph with parts

$$ A_1,A_2,\ldots,A_k, $$

where $|A_i|=n$ for every $i$.

Suppose first that $G$ has a proper $k$-coloring. Assign the vertices of $G$ with color $i$ injectively to vertices of $A_i$. This is possible because each color class contains at most $n$ vertices. If $u-v$ is an edge of $G$, then $u$ and $v$ have different colors, so their images lie in different parts of $H$ and therefore are adjacent. The resulting map is an embedding of $G$ in $H$.

Conversely, suppose that $G$ is embedded in $H$. Give every vertex of $G$ the color corresponding to the part of $H$ containing its image. Two adjacent vertices of $G$ cannot be mapped into the same part of $H$, because vertices inside one part are not adjacent. Hence adjacent vertices receive different colors, so this assignment is a proper $k$-coloring of $G$. Therefore

$$ G\text{ is }k\text{-colorable}\iff G\text{ is embedded in }H. $$

For the Hamiltonian cycle problem, let $n=|V(G)|$ and let $C_n$ be the cycle graph with $n$ vertices. If $C_n$ is embedded in $G$, the embedding maps all $n$ vertices of $C_n$ to distinct vertices of $G$. Since $G$ also has $n$ vertices, the embedding uses every vertex of $G$. The images of the edges of $C_n$ form a cycle passing through all vertices of $G$, so $G$ has a Hamiltonian cycle.

Conversely, suppose that $G$ has a Hamiltonian cycle. Label the vertices of that cycle in cyclic order as

$$ v_1,v_2,\ldots,v_n . $$

Map the vertices of $C_n$ in cyclic order to

$$ v_1,v_2,\ldots,v_n . $$

Every edge of $C_n$ is mapped to an edge of $G$, and the map is injective. Thus $C_n$ is embedded in $G$. Therefore

$$ G\text{ has a Hamiltonian cycle}\iff C_n\text{ is embedded in }G. $$

The three decision problems are therefore special cases of graph embedding: clique detection uses $K_k$ as the source graph, $k$-colorability uses $G$ as the source graph and a complete $k$-partite graph as the target graph, and Hamiltonian cycle detection uses $C_n$ as the source graph. This completes the proof. ∎