Showing NP-completeness of longest path problem

[TaPaKaH]

Homework Statement

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

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.

 

[Ray Vickson]

Homework Statement

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

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.

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

 

[Office_Shredder]

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.

 

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

 

[TaPaKaH]

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