Relationship between the minimum cost rooted k-edge connected subgraph and the unrootd version in undirected graphs

Question

In the undirected rooted k-edge connected subgraph problem, the goal is to find a minimum cost subgraph in which there are k edge-disjoint paths between the root and each vertex in the graph. The generalized version for undirected graphs aims to find a subgraph in which each pair of vertices has k-edge disjoint paths.

Is it possible that given the optimal solution to one problem, we could create an optimal solution for the other one? I have tried to see if it is possible to construct an optimal solution for the generalized version, given the optimal solution to the rooted version. We have k paths from each node to the root, so it is possible to match these subpaths to create k paths between any pairs. However, I haven't been able to prove that such paths would necessarily be disjoint.

Answer 1

Your approach is working. Menger's theorem states that the size of a minimal $s-t$ cut is equal to the number of edge disjoint paths between $s$ and $t$.

The generalized version is equivalent to the rooted version. The following propositions are equivalent:

• The graph is $k$ connected
• The graph have no $s-t$ $k$-cut (definition of $k$-connected)
• Every pair of vertices $s,t$ have $k$ edge disjoint paths (Menger's theorem)
• For a fixed root $r$, the graph have no $r-t$ $k$-cut (definition of $k$-connected, a $k$-cut must have $r$ on one side)
• For a fixed root $r$, every pair of vertices $r,t$ have $k$ edge disjoint paths (Menger's theorem)