2

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.
Dominique Fortin
  • 2,212
  • 15
  • 20
vinc456
  • 2,862
  • 5
  • 23
  • 30

2 Answers2

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.

Community
  • 1
  • 1
Charlie Martin
  • 110,348
  • 25
  • 193
  • 263
  • I'm allowed to assume that if all the problems are either P or NP-complete. So if I can't think of a polytime algorithm then I can assume that the problem is NP-complete. You are correct but I am hoping to avoid a reduction if possible. – vinc456 Dec 12 '08 at 08:01
0

What I've come up with:

  1. Same as you said, use any applicable SPP algorithm.
  2. This is the longest path decision problem, which is NP-Hard even for unweighted graphs.
  3. For unweighted graphs, a linear number of applications would suffice to solve 2, so it is NP-Hard as well.
  4. You can use maximum flow algorithms with unit capacity to find the maximum number of edge-disjoint paths.
Khaur
  • 770
  • 3
  • 10