Input: directed graph G with no cycles, nodes s & t, natural number k.

Output: true, if there are at least two vertex disjoint paths from s to t with maximum path length k. Otherwise - return false.

Run time should be polynomial.

My idea was to assign each edge capacity = 1 and find max flow. If max flow >= 2, return true. But max flow searches for shortest augmentation path, which is not always the optimal solution if you need 2 and more paths. I have a feeling that Breadth-first search or Depth-first search can help, but I don't know how to put the things together.

Does anyone have an algorithm for that problem?

CodePudding user response：

There is a Suurballe algorithm for finding two disjoint paths in a graph of minimal length. It works for O (|E| |V|*log|V|).