TAOCP 7.2.2.2 Exercise 387

Let $G=(V,E)$ and $G'=(V',E')$.

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: 4m58s

Solution

Let $G=(V,E)$ and $G'=(V',E')$. Introduce a Boolean variable

$$ x_{v,v'} $$

for every pair $(v,v')\in V\times V'$. The intended meaning is that $x_{v,v'}=1$ exactly when the vertex $v$ of $G$ is mapped to the vertex $v'$ of $G'$.

A graph embedding requires every vertex of $G$ to be assigned to one distinct vertex of $G'$. The first requirement is expressed by the clauses

$$ \bigvee_{v'\in V'} x_{v,v'} $$

for every $v\in V$. This clause forces each vertex $v$ to have at least one image.

The distinctness of the images is expressed by the clauses

$$ \bar{x}{v,v'}\vee \bar{x}{w,v'} $$

for every $v,w\in V$ with $v\ne w$ and every $v'\in V'$. These clauses prevent two different vertices of $G$ from being mapped to the same vertex of $G'$.

The remaining condition is preservation of edges. If $u-v\in E$ and $u'-v'\notin E'$, then the pair $u,v$ cannot be mapped to the pair $u',v'$. Therefore we include the clause

$$ \bar{x}{u,u'}\vee \bar{x}{v,v'} $$

for every $u-v\in E$ and every $u',v'\in V'$ with $u'-v'\notin E'$.

Let $F$ be the conjunction of all clauses constructed above. We prove that $F$ is satisfiable exactly when $G$ can be embedded in $G'$.

Suppose first that $G$ has an embedding $\phi:V\to V'$. Define a truth assignment by

$$ x_{v,v'}= \begin{cases} 1,&v'=\phi(v),\ 0,&v'\ne\phi(v). \end{cases} $$

For every $v\in V$, the clause $\bigvee_{v'\in V'}x_{v,v'}$ contains the literal $x_{v,\phi(v)}$, so it is satisfied. Since $\phi$ is injective, if $v\ne w$, then $\phi(v)\ne\phi(w)$, and hence every clause

$$ \bar{x}{v,v'}\vee\bar{x}{w,v'} $$

contains at least one true literal. Finally, if $u-v\in E$, then $\phi(u)-\phi(v)\in E'$ because $\phi$ is an embedding. Hence no clause of the form

$$ \bar{x}{u,u'}\vee\bar{x}{v,v'} $$

can have both literals false under this assignment. Therefore all clauses in $F$ are satisfied, and $F$ is satisfiable.

Conversely, suppose that $F$ has a satisfying assignment. For each $v\in V$, the clause

$$ \bigvee_{v'\in V'}x_{v,v'} $$

is satisfied, so there exists at least one $v'\in V'$ with $x_{v,v'}=1$. Define $\phi(v)$ to be such a vertex $v'$.

The clauses

$$ \bar{x}{v,v'}\vee\bar{x}{w,v'} $$

guarantee that no two distinct vertices of $G$ can be assigned the same image. If $v\ne w$ and $\phi(v)=\phi(w)=v'$, then both $x_{v,v'}$ and $x_{w,v'}$ would be true, making the corresponding clause false. Hence $\phi$ is injective.

Now let $u-v\in E$. Assume that $\phi(u)-\phi(v)\notin E'$. The construction then includes the clause

$$ \bar{x}{u,\phi(u)}\vee\bar{x}{v,\phi(v)}. $$

By the definition of $\phi$, both $x_{u,\phi(u)}$ and $x_{v,\phi(v)}$ are true, so both literals in this clause are false. This contradicts the assumption that the assignment satisfies $F$. Therefore

$$ \phi(u)-\phi(v)\in E' $$

whenever $u-v\in E$, and $\phi$ is an embedding of $G$ into $G'$.

The constructed clauses are satisfiable exactly for those pairs of graphs for which an embedding exists. This completes the proof. ∎