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_1in 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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/26292 3.2K people like this
