I've read that the longest path problem is $NP$-Hard, but what about where it is specified that each node can be visited a maximum of $N$ times? It seems the longest-path problem is a special case of this more general question.

My argument for why the generalized problem should be $NP$-Hard is this:

Supposing $P\not =NP$, then the special case with $N = 1$ cannot be solved in polynomial time. This implies that since the general case should be at least as hard as the special case, it should also be $NP$-Hard. Suppose we had a polynomial algorithm to solve the generalized longest path problem, then we can also solve the special case where $N = 1$ in polynomial time, which is a contradiction.

What I haven't found a way to prove is the claim that for any $N > 1$, this problem is also $NP$-hard. It seems intuitively wrong that the problem with $N = 1$ is $NP$-Hard but for some $N$, say $N = 5$, or $N = \text{(number of nodes in the graph)}$, it's not $NP$-Hard, but I can't find a way to prove this.

EDIT: By length of path I mean including the repeating nodes, so ABAB is length 4, ABABAB is length 6 and so on.

  • $\begingroup$ I'm not knowledgeable in complexity classes, but isn't it a general fact that if an NP-hard problem can be reduced to another problem, then this other problem is at least NP-hard as well? $\endgroup$ – Josh Chen Feb 12 '16 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.