TAOCP 7.2.2.2 Exercise 387

Let $G$ have vertices $v_1,\ldots,v_m$, and let $G'$ have vertices $w_1,\ldots,w_n$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 387. [21] Graph $G$ is said to be embedded in graph $G'$ if every vertex $v$ of $G$ corresponds to a distinct vertex $v'$ of $G'$, where $u' - v'$ in $G'$ whenever $u - v$ in $G$. Explain how to construct clauses that are satisfiable if and only if $G$ can be embedded in $G'$.

Verified: no
Solve time: 5m06s

Solution

Let $G$ have vertices $v_1,\ldots,v_m$, and let $G'$ have vertices $w_1,\ldots,w_n$. We introduce a Boolean variable

$$ x_{ij} $$

for every pair $(i,j)$, where $x_{ij}=1$ means that vertex $v_i$ of $G$ is embedded at vertex $w_j$ of $G'$.

The embedding condition has two parts. First, every vertex of $G$ must be mapped to some vertex of $G'$. For each $i$, we therefore include the clause

$$ x_{i1}x_{i2}\cdots x_{in}. $$

Second, a vertex of $G'$ cannot receive two different vertices of $G$. For every $i\ne i'$ and every $j$, we include the binary clause

$$ \bar{x}{ij}\bar{x}{i'j}. $$

These clauses enforce that the mapping from $V(G)$ into $V(G')$ is injective.

It remains to enforce preservation of edges. Suppose that $v_i-v_{i'}$ is an edge of $G$. If $w_j-w_{j'}$ is not an edge of $G'$, then $v_i$ and $v_{i'}$ cannot be mapped simultaneously to $w_j$ and $w_{j'}$. Hence for every edge $v_i-v_{i'}$ of $G$ and every nonedge $w_j-w_{j'}$ of $G'$ we add the clause

$$ \bar{x}{ij}\bar{x}{i'j'}. $$

The complete formula is therefore

$$ F= \bigwedge_{i=1}^{m} (x_{i1}\vee\cdots\vee x_{in}) \wedge \bigwedge_{\substack{i<i'\1\le j\le n}} (\bar{x}{ij}\vee\bar{x}{i'j}) \wedge \bigwedge_{\substack{v_i-v_{i'}\in E(G)\w_j-w_{j'}\notin E(G')}} (\bar{x}{ij}\vee\bar{x}{i'j'}). $$

Assume first that $G$ can be embedded in $G'$. Let the embedding map $v_i$ to $w_{f(i)}$. Set

$$ x_{i,f(i)}=1 $$

and set every other $x_{ij}$ to $0$. The first group of clauses is satisfied because every $v_i$ has an image. The second group is satisfied because the embedding assigns distinct vertices of $G'$ to distinct vertices of $G$. For the third group, if $v_i-v_{i'}$ is an edge of $G$, then the embedding requires $w_{f(i)}-w_{f(i')}$ to be an edge of $G'$. Hence no forbidden pair of true variables occurs, and every clause in the third group is satisfied. Therefore $F$ is satisfiable.

Conversely, suppose that $F$ has a satisfying assignment. For each vertex $v_i$, the first group of clauses guarantees that at least one variable $x_{ij}$ is true. The second group guarantees that no two different vertices $v_i$ and $v_{i'}$ can use the same vertex $w_j$, so choosing a true $x_{ij}$ for each $i$ defines an injective map

$$ f(v_i)=w_j. $$

Consider an edge $v_i-v_{i'}$ of $G$. If $w_{f(i)}-w_{f(i')}$ were not an edge of $G'$, then the corresponding clause from the third group would be

$$ \bar{x}{i,f(i)}\bar{x}{i',f(i')}. $$

Both literals would be false, because both variables were chosen to be true. This contradicts the satisfiability of $F$. Therefore every edge of $G$ is mapped to an edge of $G'$, and $f$ is an embedding of $G$ in $G'$.

Hence the constructed CNF formula is satisfiable exactly when $G$ can be embedded in $G'$. ∎