Paths in undirected graphs

Question

We are given an undirected graph G = (V, E) and two vertices s, t ∈ V . We consider simple paths between s and t. A path is simple if every vertex is visited at most once.

Are the following in P or NP-complete?

Does an efficient algorithm polynomial time exist for the following?

"n" represents the number of vertices in the graph "V"

1. Is there a simple path from s to t of length at most n/100?
2. Is there a simple path from s to t of length at least n/100?
3. Is there a simple path from s to t of length exactly n/100?
4. Are there two edge-disjoint paths from s to t? (Two paths are said to be edge- disjoint if they do not share an edge.)

My thoughts (please correct me if I'm wrong) Your input is appreciated.

1. I think I can run Dijkstra's Algorithm to find the shortest path between S and T in polynomial time. So question 1 is in P.
2. I think it is necessary to enumerate all the simple paths from s to t. I don't know what the running time of this would be, but I think it would be worse than polynomial.
3. Similar to 2 above. No polynomial algorithm.
4. I'm not sure. I don't know of any efficient (poly-time algorithm) to find multiple paths between two nodes but that doesn't mean that they don't exist.

Answer 1

You're on the right track. I wrote another piece on NP-complete to which I'm going to refer you for some of the details, but recall that basically you need to do two things to prove something NP-complete:

1. Show the problem is in NP
2. Show a polynomial time reduction to a problem already known to be NP-complete.

Doing 1 is pretty easy (if something walking the graph "knew" all the right decision of the next edge to take, would it find an answer in polynomial time?); I'd think seriously about the "decision TSP" problem I describe in the other note.