Reduction to Hamiltonian cycle

Question

Given that the Hamiltonian cycle problem is NP-complete, I want to prove that the following problem is NP-complete:

Given an undirected graph $G(V,E)$ and vertices $s,t\in V$, does there exist a path from $s$ to $t$ with at least $k$ edges such that all vertices in the path are distinct?

I thought of assigning a weight of $1$ to every edge and on similar grounds, but I am not able to compensate for the "at least $k$" edges part.

It would be appreciated if somebody could help me with the approach.

Answer 1

Problem is in NP

You can easily verify an answer to your problem: if a path is given, and it is goes from $s$ to $t$ and has $k$ edges with distinct vertices, then it is correct.

Reduction from Hamiltonian Cycle Problem

You can pick any vertex as $s$, and then for each neighbor, $(s,t_i)\in E$, attempt your algorithm, with $k=\left|V\right|-1$ after cutting that edge. If the algorithm succeeds for any attempt with $(s,t_i)$, then you have found a Hamiltonian cycle. This means Hamiltonian path reduces to your given problem.

Given that it is in NP, and the Hamiltonian Cycle Problem can be reduced to it, it is NP-complete.

EDIT I suppose an even simpler reduction is just to set $s = t$, and for any vertex in $V$, with $k=\left|V\right|-1$.

Though I am unsure of how one would solve this problem given $s,t,k,V,E$ in the general case. Nor do I know how to reduce this problem to the Hamiltonian cycle problem. A roundabout way would be to reduce this problem to 3-SAT, and then reduce the result back down to Hamiltonian cycle. However, as I pointed out above, you can easily see it is NP-complete, due a reduction from Hamiltonian cycle to this problem, in conjunction with the fact that the problem is in NP (you can verify the answer easily).

k-Stroll / k-Tour

A similar problem is named the k-Stroll problem in Approximation Algorithms for the Directed k-Tour and k-Stroll Problems:

The input to the k-Stroll problem is a directed $n$-vertex graph with nonnegative edge lengths, an integer $k$, and two special vertices $s$ and $t$. The goal is to find a minimum-length $s$-$t$ walk, containing at least $k$ distinct vertices.

Also related is the k-Tour problem, which is the case where $s=t$.

Answer 2

Note, all you need to do to show something is NP-Hard is to show that an NP-Hard problem is its subproblem.

For instance, in your case, you could show that since finding a Hamilton Path is NP-Hard, then your problem is NP-Hard since a Hamilton Path is the specific case of your problem where k = |V|-1.