Minimum amount of time for two enemies to reach their destinations?

Question

Given an undirected, unweighted, and connected graph $G = (V, E)$, what is the minimum amount of time it takes for party $X$ to go from $s_x$ to $t_x$ and party $Y$ to go from $s_y$ to $t_y$? At each unit of time, $X$ and $Y$ can either move to a vertex adjacent to their current position or not move at all. $X$ and $Y$ are enemies with each other and if they go less than a distance of $k$ to each other they will go to war. The distance of $X$ and $Y$ is defined as the number of edges between them on the shortest path. What is an efficient algorithm to find the two optimal paths such that $X$ and $Y$ do not go to war and they both reach their destinations in the minimum amount of time? Note that the two paths can share edges as long as $X$ and $Y$ do not go less than k units of each other during their traversal. In the example below with $k$ = 1 the optimal path for $X$ is in blue and y is in red. This allows for both $X$ and $Y$ to reach their destination in two units of time Notice, if $X$ instead took the black path, this would be suboptimal as $Y$ would have to rest for one unit of time as $X$ moved out of the way. (This would take 3 units of time.)

So far I've started by computing the shortest paths between all pairs of vertices in $V$ by doing a BFS at each vertex. This will take $O(EV)$ Then, I suggest the following greedy algorithm:

At each time tick, $X$ and $Y$ should move to the vertex that is closest to their destination. If that vertex is less than k edges from the other party, choose the next closest vertex and so on. If no such vertex exists, then the current party will rest until the other party moves at least k units away from any of the adjacent vertices. Give priority to $X$ or $Y$ based on who has fewer options.

However, I don't think the greedy solution will work. Some other ideas include A* or a max flow reduction.

Answer 1

Generate the graph $G'$ of all legal configurations. A legal configuration is an ordered pair of vertices $\langle u, v \rangle$ in $V^2$ such that $d_G(u,v) \ge k$, where $d_G(u,v)$ denotes the distance between $u$ and $v$ in $G$.

There is an edge from $\langle u_1, v_1 \rangle$ to $\langle u_2, v_2 \rangle$ in $G'$ if and only if $d_G(u_1, u_2) \le 1$ and $d_G(v_1, v_2) \le 1$.

The amount of time you are looking for is now equal to $d_{G'}(\langle s_x, s_y \rangle, \langle t_x, t_y \rangle)$.