CODEWITHSUNDEEP
algorithmgraph-theory
vinc456
vinc456

Reputation: 2890

Paths in undirected graphs

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.

Upvotes: 2

Views: 2717

Answers (2)

Khaur
Khaur

Reputation: 770

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.

Upvotes: 0

Charlie Martin
Charlie Martin

Reputation: 112386

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.

Upvotes: 1

Related Questions