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

Problem Detail: 

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!

Asked By : user475680

Answered By : Patrick

Hopefully not giving too much away: You need to add only two nodes.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26292

3.2K people like this

 Download Related Notes/Documents