# Finding optimal minimum rooted k-edge disjoint connected paths to build a feasible solution for the undirected version

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?

• Do you mean a min-cost $k$-connected graph?
– Mike
Commented Apr 3, 2022 at 18:08
• @Mike Yes, min-cost k-edge connected subraph. Commented Apr 3, 2022 at 20:26
• @MishaLavrov I think you are right about that. But let's consider the case where G satisfies the minimum number of edges requirement. Commented Apr 3, 2022 at 20:27
• 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. Commented Apr 3, 2022 at 21:48

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.
• @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. Commented Apr 5, 2022 at 21:54