Ok, assume you have an undirected graph of finite size with edges with weight = 1. The graph is sparse. From any given node, there is a path to any other node.
Now, we have two cars somewhere in the graph that are constantly going from one destination to the other. Traversing an edge takes exactly one second. Given any input lists of destinations for both cars, we want to find the quickest routes for both cars. The destinations in the lists should be visited in order by their respective cars.
These are two problems that could individually be solved easily with Dijkstra's algorithm. However, the cars may never collide in the nodes. They may be traversing the same edge at the same time but they may never be in the same node at the same time.
I'm supposed to find the best possible routes for the two cars that result in the lowest overall time using greedy algorithms. What I am doing is to use Dijkstra's algorithm to solve for the two cars individually and then resolve collisions by making the car with the earliest finish time wait.
This is, however, not the most optimal solution. I have been hinted that this problem is NP-hard and I have to either show this or come up with an algorithm that gives the globally optimal solution.
But I'm not sure this problem is actually NP-hard and I get completely lost when trying to prove this. Yes, you have to reduce the problem at hand to a known NP-hard problem but I don't even know where to start!
Can anybody help me out with this?
Here's how you can do it in polynomial time. Say we are given the problem over the graph $G=(V,E)$. We first construct another graph $G' = (V',E')$. The set of nodes $V'$ will simply be $V^2\setminus\{(u,u)|u\in V\}$. The edge relation $E'$ will be such that $E'((u,v),(w,x))$ if and only if $E(u,w)$ and $E(v,x)$ (without loss of generality we assume that all nodes have self loop in $E$, so that waiting can be accounted for in this edge relation). Let $U = \{u_0,u_1,\ldots,u_n\}$ and $W = \{w_0,w_1,\ldots,w_m\}$ be the destination lists for the cars, where $u_0$ and $w_0$ are the starting positions of the cars. We now create a copy of $G'$ for each $u_i,w_j$, which we denote $G_{i,j}$ (and the copy of a node $v \in V'$ is denoted by $(v,i,j)$). We put all graphs $G_{i,j}$ into a single graph $H$ in the following way. Let $i,j$ be arbitrary. Then we add the edges $((u_{i-1},v,i-1,j),(u_{i-1},v,i,j))$, $((v,w_{j-1},i,j-1),(v,w_{j-1},i,j))$ for all $v\in V$, and the edge $((u_{i-1},w_{j-1},i-1,j-1),(u_{i-1},w_{j-1},i,j))$. We give each of these new edges weight zero, so that traversing them costs no time.
Then we just run Djikstra's on $H$ with source $(u_0,w_0,0,0)$ and target $(u_n,w_m,n,m)$. The running time of this will be $O([(|V|^2 + |E^2|)nm]^3)$, which is clearly polynomial. This is actually just a dynamic programming algorithm.