0
$\begingroup$

Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'.

What is the complexity of this problem?

$\endgroup$
2
$\begingroup$

You can solve this problem in time $O(|V|+|E|)$ by using dynamic programming. Thirst you order nodes in topological order. Let $v_i$ be the $i$-th node in topological order. Let $E_i$ be the set of edges ending in $v_i$.

If $|E_i\setminus D'| = 0$ then: $$ d[v_i][0] = 0 $$

otherwise: $$ d[v_i][0] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \not\in D'})\\ $$

If $|E_i| = 0$ then: $$d[v_i][1] = -\infty$$ otherwise: $$d[v_i][1] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \in D'}, d[v_j][1]_{(v_j, v_i) \not\in D'}) $$

It's easy to see that $d[v_i][0]$ is equal to length of longest path ending in $v_i$ without edges from $D'$ and $d[v_i][1]$ is equal to length of longest path ending in $v_i$ with exactly one edge from from $D'$. After that you need to find largest of $d[v_i][1]$. You can also store the id of the node for which we found the maximal value during dynamic programming to recreate the path.

$\endgroup$
  • $\begingroup$ Thank you for your answer. In my case I have weights on the vertices and not on the edges, will the compelxity of the problem remain the same? For the condition |Ei\D'|=0, do you mean that all the edges of Ei are in D' or Ei contains at least one edge from D'? $\endgroup$ – Farah Mind Sep 8 at 9:00

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.