Suppose we have a DAG $G$ with one source node $s$, ie. it has a path to every node, and target node $t$ which every node has a path to it. For a pair of paths from $s$ to $t$ we can define a distance function $d(\cdot,\cdot)$ as: $$d(P_1,P_2) = |(P_1 - P_2) \cup (P_2 - P_1)|$$ We want to find the maximum value of this function computed all possible paths between $s$ and $t$: $$D = \max_{P_1,P_2} \big\{ d(P_1,P_2)\big\}$$

You can think of this measure as a distance between two paths and therefore the problem can be thought of finding the "diameter" of a graph that its vertices are paths on $G$ and its edges' weights are determined by this formula.

Because $G$ is a DAG the number of paths between $s$ and $t$ is finite and therefore the quantity is well defined.

I have tried to find an upper bound for $D$ in a linear time with respect to nodes and edges of the graph. Suppose we take a random path $P_r$. We try to find the path that is maximally different from $P_r$. If we find the most distant path from this path, namely $P_s$ diameter cannot be bigger than $2 d(P_r,P_s)$, that is: $$D \le 2 d(P_r, P_s)$$ This can be done by setting the weight of the edges on $P_r$ to zero and then finding the maximum distance between $s$ and $t$ on the new graph. This can be done in linear time. But I haven't figured a way on how to choose the $P_r$ or how to directly compute $D$

  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – Raphael
    Commented Jun 20, 2017 at 20:02
  • 2
    $\begingroup$ You might want to check out if you can model the problem as one of finding maximal flows. $\endgroup$
    – Raphael
    Commented Jun 20, 2017 at 20:02
  • $\begingroup$ @Raphael I've put down my thoughts that go quite some way in the direction of solving the problem, I believe, if I knew the solution I wouldn't be asking the question in the first place. Which solutions involving max-flow do you know of that are sort of similar? $\endgroup$ Commented Jun 22, 2017 at 14:18
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Maximum_flow_problem lists both the edge- and vertex-disjoint paths problem as a max flow problem. $\endgroup$ Commented Jun 25, 2017 at 21:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.