5
$\begingroup$

First, here are the definitions I am working with: Given an undirected graph $G = (V,E)$ and vertices $s, t \in V$ we wish to either find the number of vertex disjoint paths from $s$ to $t$ or to find the number of edge disjoint paths from $s$ to $t$.

I am trying to show the instance of one problem can be transformed to an equivalent instance of the other. I was able to show one direction: in particular, given an instance of the edge disjoint path problem, I can convert it to an equivalent instance of the vertex disjoint path problem by using the line graph $L(G)$. The only thing that I am not sure about is what to make of $s$ and $t$ as they are no longer defined in $L(G)$.

However, for the other direction, I have no idea how to transform an instance of the vertex disjoint problem to an equivalent instance of the edge disjoint problem.

The reduction need not be one-to-one (i.e if there are $k$ paths in the vertex-disjoint case, there could be $k'$ paths in the edge disjoint case... as long as we can show how to go from $k'$ to $k$.

$\endgroup$
  • $\begingroup$ By "path" if you mean a sequence of non-repeating vertices and by "disjoint" you mean having no common elements at all, I believe the converse is not difficult to prove. If two paths are vertex disjoint then they are most certainly edge disjoint since an edge is identified by its incident vertices and as long as they are unequal, so are the corresponding edges. If $v_1, v_2,..., v_r$ and $u_1, u_2, ..., u_p$ are two paths, if $v_i$ is unequal to $u_j$ for every $i, j$ then obviously the two paths are edge disjoint too since $v_p v_q$ is unequal to $u_l u_m$ for any characters $p, q, l, m$ $\endgroup$ – Ishfaaq Jan 18 '14 at 0:11
  • $\begingroup$ That's not what I meant... What I am trying to do is that: Given an instance of the vertex-disjoint problem, show how to transform it so that it can be fed to an "edge-disjoint solver" and that the number of such paths match up. In the other direction, that's what the line graph solves. $\endgroup$ – user340082710 Jan 18 '14 at 0:54
  • 1
    $\begingroup$ I know that a vertex disjoint set of paths implies edge disjoint, but I am trying to show that if I have an edge-disjoint solver, that I can solve a vertex-disjoint problem instance by somehow transforming the graph appropriately. $\endgroup$ – user340082710 Jan 18 '14 at 1:45
  • $\begingroup$ Sorry for not replying earlier. I learnt Graph Theory from a purely theoretic perspective and not from a computer science perspective. This seems to be out of my league. $\endgroup$ – Ishfaaq Jan 19 '14 at 4:07

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.