34.2 Polynomial-time verification

34.2-1

Consider the language $\text{GRAPH-ISOMORPHISM}$ $= \{\langle G_1, G_2 \rangle: G_1$ and $G_2$ are isomorphic graphs$\}$. Prove that $\text{GRAPH-ISOMORPHISM} \in \text{NP}$ by describing a polynomial-time algorithm to verify the language.

(Omit!)

34.2-2

Prove that if $G$ is an undirected bipartite graph with an odd number of vertices, then $G$ is nonhamiltonian.

(Omit!)

34.2-3

Show that if $\text{HAM-CYCLE} \in P$, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.

(Omit!)

34.2-4

Prove that the class $\text{NP}$ of languages is closed under union, intersection, concatenation, and Kleene star. Discuss the closure of $\text{NP}$ under complement.

(Omit!)

34.2-5

Show that any language in $\text{NP}$ can be decided by an algorithm running in time $2^{O(n^k)}$ for some constant $k$.

(Omit!)

34.2-6

A hamiltonian path in a graph is a simple path that visits every vertex exactly once. Show that the language $\text{HAM-PATH}$ $= \{\langle G, u, v \rangle:$ there is a hamiltonian path from $u$ to $v$ in graph $G\}$ belongs to $\text{NP}$.

(Omit!)

34.2-7

Show that the hamiltonian-path problem from Exercise 34.2-6 can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.

(Omit!)

34.2-8

Let $\phi$ be a boolean formula constructed from the boolean input variables $x_1, x_2, \dots, x_k$, negations ($\neg$), ANDs ($\vee$), ORs ($\wedge$), and parentheses. The formula $\phi$ is a tautology if it evaluates to $1$ for every assignment of $1$ and $0$ to the input variables. Define $\text{TAUTOLOGY}$ as the language of boolean formulas that are tautologies. Show that $\text{TAUTOLOGY} \in \text{co-NP}$.

(Omit!)

34.2-9

Prove that $\text P \subseteq \text{co-NP}$.

(Omit!)

34.2-10

Prove that if $\text{NP} \ne \text{co-NP}$, then $\text P \ne \text{NP}$.

(Omit!)

34.2-11

Let $G$ be a connected, undirected graph with at least $3$ vertices, and let $G^3$ be the graph obtained by connecting all pairs of vertices that are connected by a path in $G$ of length at most $3$. Prove that $G^3$ is hamiltonian. ($\textit{Hint:}$ Construct a spanning tree for $G$, and use an inductive argument.)

(Omit!)