How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem

Question

I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t:

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

A simple path is a path without any repeated vertice, i.e. every vertice can be visited just one time. The length of the path is given from the edges of which it is composed.

So how can I show that LPATH is an NP-Complete problem using the Hamilton path problem as an NP-Hard problem as reference?

Answer 1

Welcome to the site! Let $G = (V, E)$ be a undirected graph. If $G$ is Hamiltonian, then there exists a simple cycle $C$ in $G$ containing every vertex, i.e. the length of $C$ is $|V|$. Note that if you delete any edge $vw$ from $C$, you end up with a path of length $|V| - 1$ between $v$ and $w$. Conversely, if you find a simple path $P$ of length $|V| - 1$ between two vertices $v, w$ connected by an edge, you can add the edge $vw$ to $P$ to obtain a Hamiltonian cycle (as $P$ cannot contain $vw$ due to being a simple path). Also observe that the choice of $v$ and $w$ is arbitrary as long as they are connected by an edge.

So we can obtain the following reduction: Starting from some graph $G = (V, E)$, pick some edge $vw \in E$ and delete it to obtain a new graph $G' = (V, E \setminus \{vw\})$. Using the observations we made, it follows that $G'$ has a path $P$ between $v$ and $w$ of length $|V| - 1$ if and only if adding $vw$ to $P$ yields a Hamiltonian cycle in the original graph $G$. As $G'$ can be computed from $G$ in polynomial time, we have a polynomial reduction $\mathrm{Hamiltonian Cycle} \leq_\mathsf{P} \mathrm{Long Path}$, thus showing that your problem is $\mathsf{NP}$-hard (because $\mathrm{Hamiltonian Cycle}$ is $\mathsf{NP}$-hard already).

To show that $\mathrm{Long Path}$ is in $\mathsf{NP}$ we note that a path in a graph can be efficiently encoded as a list of its edges and checking that a string actually encodes a path in the graph and then counting the number of edges to determine whether it is long enough can be done in polynomial time.

Hence we find that $\mathrm{Long Path}$ is $\mathsf{NP}$-complete.