Polynomial-Time Reducibility

HC $\leq_{m}^{P} \mathrm{LP}$.

$\mathrm{VC} \equiv_{m}^{P}$ IS.

GIso $\equiv_{m}^{P}$ DGIso.

SAT $\leq_{m}^{P}$ CNF-SAT.

$\mathrm{VC} \leq_{m}^{P} \mathrm{IP}$.

$3\mathrm{DM} \leq_{m}^{P} \mathrm{SAT}$.

$3\mathrm{SAT} \leq_{m}^{P} \mathrm{VC}$.

$3\mathrm{SAT} \leq_{m}^{p} \mathrm{HC}$.

Prove that CNF-Sat $\leq_{m}^{P}$ 3Sat.

In this exercise, we study an alternative proof for Example 7.25. Let us replace conditions (1) and (2) by condition (3): For every $a \in A \cup B \cup C$, there is a triple $w \in W^{\prime }$ such that (i) $a \in w$, and (ii) if $w^{\prime } \in W^{\prime }, w^{\prime } \neq w$ then $a \notin w^{\prime }$. Translate this condition into a Boolean formula $G$ over variables $x_{w}$ and show that $G$ is satisfiable if and only if $W$ has a threedimensional matching $W^{\prime }$.

Construct the following reductions:

Consider the following variations of the problem 3Sat:

3Sat-Exactly-One: Given a 3-CNF $F$, determine whether there is an assignment $t$ on variables in $F$ that assigns value TRUE to exactly one literal in each clause of $F$.

3Sat-Not-All: Given a 3-CNF $F$, determine whether there is an assignment $t$ on variables in $F$ that assigns value TRUE to either one or two literals (but not all three literals) in each clause of $F$.

Show that 3Sat, 3Sat-Exact-One and 3Sat-Not-All are polynomial time equivalent under $\leq_{m}^{P}$.

Consider the following problems: Subgraph Isomorphism (SGIso): Given two graphs $G_{1}= \left(V_{1}, E_{1}\right)$ and $G_{2}=\left(V_{2}, E_{2}\right)$, determine whether there is a one-to-one mapping $f: V_{1} \rightarrow V_{2}$ such that, for all $u, v \in V_{1}$, $\left\{ u, v\right\} \in E_{1}$ implies $\left\{ f(u), f(v)\right\} \in E_{2}$.

Graph Automorphism (GAuto): Given a graph $G= (V, E)$, determine whether there is a one-to-one function $f: V \rightarrow V$ other than the identity function such that, for all $u, v \in V,\left\{ u, v\right\} \in E$ if and only if $\left\{ f(u), f(v)\right\} \in E$.

Prove all the polynomial-time reductions you can find among the three problems GIso, SGIso and GAuto.