5
$\begingroup$

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.