# Showing NP-completeness of longest path problem

1. Nov 20, 2013

### TaPaKaH

1. The problem statement, all variables and given/known data
Show that the following problem is NP-complete:
Given: A directed graph $G=(V,E)$, source and target nodes $s,t\in V$ and a parameter K.
Goal: Determine whether there exists a simple $s,t$-path in $G$ of length at least $K$.

3. The attempt at a solution
I've already shown that the problem is in NP, but I can't come up with a poly time reduction from a known NP-complete problem. Any ideas welcome.

2. Nov 20, 2013

### Ray Vickson

Google "longest path problem"; several on-line articles have all you need.

3. Nov 20, 2013

### Office_Shredder

Staff Emeritus
TaPaKaH, what are some NP-complete problems you are allowed to reduce to? Ones that are graph related already (ones that are related to doing walks around a graph in particular) would be particularly nice as starting points.

4. Nov 21, 2013

### TaPaKaH

2-partition, 3-partition, TSP (undirected), ILP, SAT, 3-SAT, clique, vertex cover, independent set, Hamiltonian path (undirected) and cycle (directed and undirected) is what I am allowed to use.

5. Nov 21, 2013

### TaPaKaH

I just managed to come up with a reduction from directed Hamiltonial cycle.