0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – caduk
    Mar 30, 2022 at 8:57

1 Answer 1

Reset to default
1
$\begingroup$

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)
$\endgroup$

You must log in to answer this question.

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