1
$\begingroup$

Suppose we have an undirected weighted graph G with a root node, and the goal is to find minimum cost k-edge disjoint paths from the root node to each vertex. Now, suppose we create a directed version of G called G' by adding two edges (u, v), (v, u) to the G' graph for each undirected edge (u, v) in G, with the same cost as the corresponding undirected edge.

Suppose we solve the minimum rooted k-edge disjoint path problem on G', and we want to find a feasible (not optimal) solution for G using this solution. We consider each edge (u, v) in G to be in the solution if (u, v) or (v, u) is in the solution for G'. I want to see if this strategy can lead to a feasible solution for G. It's obvious that we would indeed have the k paths for each (r, v) pair in the undirected graph, but I can not prove that the paths would be disjoint, or not necessarily disjoint by a counterexample. What do you think? Are there any theorems that can help in this case?

$\endgroup$
4
  • $\begingroup$ Do you mean a min-cost $k$-connected graph? $\endgroup$
    – Mike
    Commented Apr 3, 2022 at 18:08
  • $\begingroup$ @Mike Yes, min-cost k-edge connected subraph. $\endgroup$
    – Winston
    Commented Apr 3, 2022 at 20:26
  • $\begingroup$ @MishaLavrov I think you are right about that. But let's consider the case where G satisfies the minimum number of edges requirement. $\endgroup$
    – Winston
    Commented Apr 3, 2022 at 20:27
  • $\begingroup$ Oh, if what you actually mean is a $k$-edge-connected subgraph, then my comment is completely irrelevant. I thought you wanted $n-1$ edge-disjoint paths that are each $k$ edges long, one from the root to every other vertex. $\endgroup$ Commented Apr 3, 2022 at 21:48

1 Answer 1

2
$\begingroup$

If you have two edge disjoint paths in $G'$ from $s$ to $t$ such that one use the edge $(u,v)$ and the other the edge $(v,u)$ (so one path is $s\rightarrow \text{subpath}_{1,1}\rightarrow u\rightarrow v\rightarrow \text{subpath}_{1,2} \rightarrow t$ and the other is $s\rightarrow \text{subpath}_{2,1}\rightarrow v\rightarrow u\rightarrow \text{subpath}_{2,2} \rightarrow t$, then it is easy to see that we can re-route these paths such that none use $(u,v)$ and $(v,u)$ ($s\rightarrow \text{subpath}_{1,1}\rightarrow u \rightarrow \text{subpath}_{2,2} \rightarrow t$ and $s\rightarrow \text{subpath}_{2,1}\rightarrow v\rightarrow \text{subpath}_{1,2} \rightarrow t$). Do this for each edge used in both ways, and you get a solution in the undirected case.

$\endgroup$
3
  • $\begingroup$ Great, this is actually pretty easy to see! I can't believe how I missed it. Thanks a lot. $\endgroup$
    – Winston
    Commented Apr 5, 2022 at 16:50
  • $\begingroup$ I guess this means that such paths shouldn't even exist cause we are getting rid of some edges in the re-routing process, which makes the solution to even cost less. This contradicts the fact that the solution on the directed graph was optimal. $\endgroup$
    – Winston
    Commented Apr 5, 2022 at 17:26
  • $\begingroup$ @Winston Yes, if we are finding a minimum cost subgraph, then the path in $G$ needs to be edge-disjoint by direct application of this result. $\endgroup$
    – caduk
    Commented Apr 5, 2022 at 21:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .