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

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.

• Both problems in their decision version are $\mathcal{NP}$-complete, so there must be a polynomial reduction between them. That does not answer whether there is a natural transformation between them. Mar 30, 2022 at 8:57

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 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)