# 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