0
$\begingroup$

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!

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

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – user475680 Jun 1 '14 at 12:19
  • $\begingroup$ Yeps, that's it. $\endgroup$ – Patrick Jun 1 '14 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.