2
$\begingroup$

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$

$\endgroup$
  • $\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 Jun 20 '17 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 Jun 20 '17 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$ – Ameer Jewdaki Jun 22 '17 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$ – Nicholas Mancuso Jun 25 '17 at 21:26

Your Answer

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

Browse other questions tagged or ask your own question.