[Math] find the maximum weighted path in a directed acyclic graph using 2 traversal

Question

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?

Answer 1

[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)$.