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!

A Karp reduction from $\mathrm{Hamiltonian Cycle}$ could work as follows: Given a graph $G = (V, E)$, we construct $\mathrm{Long Path}$-instance $(G', v, v', |V|)$ where $G'$ is obtained by adding a copy $v'$ of some arbitrarily chosen vertex $v \in V$ (including its edges). Note that this instance can be constructed from $G$ in polynomial time.

To see that this is a correct reduction mapping, we see that a Hamiltonian cycle $C$ in $G$ induces a path between $v$ and $v'$ of length $|V|$ and vice versa.

Thus, 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.