Find two paths in a graph that are in distance of at least D(constant)

Question

Instance of the problem: Undirected and unweighted graph G=(V,E). two source nodes a and b, two destination nodes c and d and a constant D(complete positive number).(we can assume that lambda(c,d),lambda(a,b)>D, when lambda(x,y) is the shortest path between x and y in G). we have two peoples standing on the nodes a and b.

Definition:scheduler set- A scheduler set is a set of orders such that in each step only one of the peoples make a move from his node v to one of v neighbors, when the starting position of them is in the nodes a,b and the ending position is in the nodes c,d.A "scheduler set" is missing-disorders if in each step the distance between the two peoples is > D.

I need to find an algorithm that decides whether there is a "missing-disorders scheduler set" or not.

any suggestions?

Answer 1

One simple solution would be to first solve all-pairs shortest paths using n breadth-first searches from every node in O(n * (n + m)).

Then create the graph of valid node pairs (x,y) with lambda(x, y) > D, with edges indicating the possible moves. There is an edge {(v,w), (x,y)} if v = x and there is an edge {w, y} in the original graph or if w = y and there is an edge {v, x} in the original graph. This new graph has O(n^2) nodes and O(nm) edges.

Now you just need to check whether (c, d) is reachable from (a, b) in the new graph. This can be achieved using DFS or BFS.

The total runtime be O(n * (n + m)).