# Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph

I have a homework question which I would appreciate some help with:

Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v_1, v_2$ we will define $D(v_1, v_2)$ to be the maximum length between $v_1$ and $v_2$ in the graph.

For every two disjoint sub-sets of vertices $V_1, V_2 \subset V$ we will define "The detour length" between them to be: $w(V_1, V_2) = max\{D(v_1, v_2) \mid v_1\in V_1, v_2 \in V_2\}$

Describe an algorithm which runs at $O(|V|\cdot |E|)$ complexity, that receives as an input $V_1, V_2 \subset V$ and calculates $w(V_1, V_2)$

(Hint: You can add vertices and edges to the graph)

OK so I realize that this is a problem which is connected to finding the longest path in a DAG. I know that I can negate all the weights inside $G$ and run Bellman-Ford to find the longest path, (It will work without issues because this is a DAG). Because Bellman-Ford runs in the wanted complexity, I think this can be solved by doing some modification to B-F, but I can't seem to figure out what I can do to solve it.

Every solution I come up with will run in a higher complexity than needed - I thought about running B-F on every vertex on $V_1$ and then calculating the max, but this isn't efficient, and also doesn't really use the hint. I also though about creating a second graph by connecting the two sub-sets but that also will run at a higher complexity because I need to run over every vertex.

Any help is appreciated, Thx!

• For a nice fun bonus challenge: figure out how to solve this problem in $O(|V| + |E|)$ time. It can be done! – D.W. Jun 2 '14 at 6:26

• Ah, OK...I think I have some direction. I can add one node, say $s$ and connect it to all vertices in $v_1$ and add another node $t$ and connect it to all vertices in $v_2$ (all with edges of weight 0)...then it becomes a problem of finding the longest path between s and t (which I can use Bellman-Ford to do) – user475680 Jun 1 '14 at 12:19