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.

Let $G = (V, E)$ be a bipartite graph with bipartition $V = X \cup Y$, where $X \cap Y = \emptyset$. Assume for contradiction that:

1. The total number of vertices $n = |X| + |Y|$ is odd.
2. $G$ contains a Hamiltonian cycle $C$.

Since $G$ is bipartite, the cycle $C$ must alternate between vertices in $X$ and $Y$. Starting at a vertex in $X$, the cycle proceeds to $Y$, then back to $X$, and so on. To return to the starting vertex in $X$, the cycle must consist of an even number of steps. However, $n$ is odd, making it impossible to alternate perfectly and return to the starting point.

This contradiction implies that $G$ cannot have a Hamiltonian cycle when $n$ is odd.

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.

We can use the following Lemma:

Lemma: Let $G$ be a Hamiltonian graph. If every edge in $G$ is essential, meaning it must appear in every Hamiltonian cycle of $G$, then $G$ itself must be a Hamiltonian cycle.

Proof of Lemma (by Contradiction): Let $C$ be a Hamiltonian cycle in $G$. Assume $G \neq C$, meaning there exists at least one edge $e \in G$ that does not belong to $C$. Thus, $e$ is non-essential. This contradicts the assumption that every edge in $G$ is essential.

Proof: Assume $\text{HAM-CYCLE} \in P$, meaning there exists a polynomial-time algorithm $A$ that decides whether a given graph contains a Hamiltonian cycle.

Let $G = (V, E)$ be a graph with a Hamiltonian cycle. We begin by setting $G^\ast = G$.

For each edge $e \in E$, we perform the following steps:

1. Remove $e$ from $G^\ast$, resulting in a subgraph $G'$.
2. Use algorithm $A$ to check if $G'$ still contains a Hamiltonian cycle:
   • Case 1: $e$ is essential. If removing $e$ from $G^\ast$ causes $G'$ to lose its Hamiltonian cycle, then $e$ must be part of every Hamiltonian cycle in $G^\ast$. In this case, $G^\ast$ remains unchanged.
   • Case 2: $e$ is non-essential. If $G'$ still contains a Hamiltonian cycle, then there exist Hamiltonian cycles in $G^\ast$ that do not include $e$. In this case, we safely remove $e$ from $G^\ast$, so we update $G^\ast = G'$.

The iterations ensure that $G^\ast$ remains a subgraph of $G$ that still contains a Hamiltonian cycle. Every edge that remains in the final graph must be essential for the last $G^\ast$. Thus, by the lemma above, $G^\ast$ must be a Hamiltonian cycle. Since $G^\ast$ is a subgraph of $G$, it is also a Hamiltonian cycle of $G$.

Algorithm $A$ runs in polynomial time, and since there are at most $O(n^2)$ edges in $G$, the total number of calls to $A$ is at most $O(n^2)$. Thus, the running time of the iterations is polynomial.

Finally, listing the vertices of the Hamiltonian cycle in order can be done in polynomial time. This involves starting from an arbitrary vertex in $G^\ast$ and following the Hamiltonian cycle in $G^\ast$. Regardless of whether the graph is stored with an adjacency list or adjacency matrix, this will take polynomial time.

Thus, the problem of listing the vertices of a Hamiltonian cycle in order can be solved in polynomial time.

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!)