2
$\begingroup$

G is an unweighted, undirected graph. Then, I cannot prove that [deciding whether G has a path of length greater than k] is NP-Complete.

How can I show whether the algorithm is NP-complete or not?

$\endgroup$
  • 1
    $\begingroup$ The easiest way to prove a problem is NP complete is usually to show that you can use it to solve a different NP-complete problem with only polynomial many questions and polynomialy many extra steps. Really that only shows the problem is NP-hard but this problem is obviously in NP so if it's NP-hard it's NP-complete $\endgroup$ – DRF Apr 1 '15 at 12:39
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Longest_path_problem $\endgroup$ – Batman Apr 1 '15 at 12:39
2
$\begingroup$

Let $G$ be your graph, and let it have $n$ vertices.

The Hamiltonian path problem is NP-complete. $G$ has a Hamiltionian path if and only if its longest path has length $n - 1$. Thus, the decision problem you described must be NP-complete.

$\endgroup$
2
$\begingroup$

This problem can be shown to NP-hard by reducing the longest path problem to it. It's not hard to do so maybe you want to give it a try first before I give you the reduction.

$\endgroup$

Your Answer

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

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