0
$\begingroup$

Given a directed acyclic graph the task ith positive edge weight is to find the maximum weighted path between 2 nodes u and v using 2 traversal meaning after the first traversal from u to v find the first path let its weight be v1 and replace the edges along the path with 0 again do the second traversal from u to v in the modified graph and find a path let its value be v2. The task is to maximize the sum of v1 and v2. The solution I thought of is to use the classic Dynamic programming algorithm to find longest weighted path for the first traversal and replace edges by 0 along the path again run same algorithm in the modified graph and the value of value from 1st and second traversal is result. But this approach is not yielding an optima solution can anyone give example where it is failing and a possible solution to the problem?

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

[EDIT]This is now a complete answer

A counter exemple for your solution is:

$v_1 \xrightarrow{2} v_2$ ; $v_1 \xrightarrow{1} v_3$ ; $v_2 \xrightarrow{0} v_3$ ; $v_2 \xrightarrow{1} v_4$ ; $v_3 \xrightarrow{2} v_4$ .

The first maximal path will give you this path $v_1\xrightarrow{2} v_2 \xrightarrow{0} v_3\xrightarrow{2} v_4$ of weight 4. And the second maximal has weight 1 (hence for a total of 5). But you can get a better total by taking $v_1 \xrightarrow{2} v_2 \xrightarrow{1} v_4$ and $v_1 \xrightarrow{1} v_3 \xrightarrow{2} v_4$ for a total of 6.

A solution

Let $G=(V,E,w)$ be a DAG.

Let $m=m_1...m_n$ be a path of maximum in $G$.

We define $G_m=(V',E',w')$ as follow:

  • $V'=\{m_1,...,m_n\}\times V$
  • $E'=\{((m_i,v),(m_i,v'))\mid (v,v')\in E\}\cup \{((m_i,m_j),(m_j,m_k))\mid i<k<j\}$
  • $w'((m_i,v),(m_i,v'))=w(v,v')$ if $(v,v')$ do no belong to the maximal path, $0$ otherwise
  • $w'((m_i,m_j),(m_j,m_k))=-w(m_k...m_j)$

Let $m'$ be the maximal path in $G_m$, the maximal sum you are looking for is equal to $w(m)+w'(m')$!

You can compute it in polynomial time since finding a maximal path is linear in DAGs and the second DAG has a size polynomial in the first.

I let you the joy of proving this solution correct ... The intuition behind it is:

  1. I find the maximal path in $G$
  2. But it may be the case that I made a wrong choice maximizing the first path without caring about the second
  3. So I allow the second path to correct the first by going up the first path (taking negative reward). This is done when there is a change of copies (going from $m_i\times V$ to $m_j\times V$
  4. I can correct only once each edge of the graph (this is the reason of the inequality $i<k<j$).

Please ask if something is not clear or if I made a mistake. I didn't do the full proof. But I hope it is correct.

Edit 2: on an exemple Considere the graph given as a counter example for your solution. The maximal path is : $m=v_1 \to v_2 \to v_3 \to v_4$. thats gives 4.

$G_m$ is has follow : for $k\in\{1,2,3,4\}$ : $(v_k,v_1) \xrightarrow{0} (v_k,v_2)$ ; $(v_k,v_1) \xrightarrow{1} (v_k,v_3)$ ; $(v_k,v_2) \xrightarrow{0} (v_k,v_3)$ ; $(v_k,v_2) \xrightarrow{1} (v_k,v_4)$ ; $(v_k,v_3) \xrightarrow{0} (v_k,v_4)$ ;

$(v_1,v_3)\xrightarrow{-0}(v_3,v_2)$ ; $(v_1,v_4)\xrightarrow{-(0+2)}(v_4,v_2)$ ; $(v_1,v_4)\xrightarrow{-2}(v_4,v_3)$ ; .

The maximal path is $(v_1,v_1)\xrightarrow{1} (v_1,v_3)\xrightarrow{-0}(v_3,v_2)\xrightarrow{1}(v_3,v_4)$ that gives you 2.

Thus the solution is 6.

Notice that here the second maximal path somehow "correct" the first maximal path by taking $(v_1,v_3)\xrightarrow{-0}(v_3,v_2)$.

$\endgroup$
9
  • $\begingroup$ It would be great if you can explain the solution with an example $\endgroup$ Commented Oct 12, 2016 at 17:11
  • $\begingroup$ @PrashantBhanarkar I edited my answer to show the construction on an example. This does not mean the construction is correct but illustrate the idea I had to give this construction. Now that I think about it again may be the inequality on $i,j,k$ should be $i\leq k <j$ rather than $i< k<j$ but I'm not sure. If you do a proof, I'm sure you will work out whether the inequality should be strict or not. $\endgroup$
    – wece
    Commented Oct 14, 2016 at 7:30
  • $\begingroup$ Please tell me if something is not clear enough $\endgroup$
    – wece
    Commented Oct 14, 2016 at 7:31
  • $\begingroup$ @PrashantBhanarkar I found this algorithm en.wikipedia.org/wiki/Edge_disjoint_shortest_pair_algorithm which is basically what I'm trying to do , but it look simpler but I think it is because it does not allow the two paths to take the same edge... But if you understand this algorithm you understand the idea I had to design my answer. $\endgroup$
    – wece
    Commented Oct 14, 2016 at 9:22
  • $\begingroup$ I understand the first part of the algorithm that we need to find the maximum weighted path in a DAG but I am not clear with the second part $\endgroup$ Commented Oct 14, 2016 at 10:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .