# Is this an NP-Complete problem? (unweighted & undirected graph)

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?

• 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 – DRF Apr 1 '15 at 12:39
• en.wikipedia.org/wiki/Longest_path_problem – Batman Apr 1 '15 at 12:39

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.

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.