# Sparse subgraph preserving rooted edge connectivity up to $k$

For a graph $G=(V,E)$ with $n$ vertices and $m$ edges, a subgraph of $O(kn)$ edges is an $r$-rooted-$k$-sparsifier if it preserves the local edge connectivity from $r$ to every other vertex up to $k$. Namely, it is a subgraph $G_k$, such that $\lambda(r,x,G_k)\geq \min(\lambda(r,x,G),k)$ for all $x\in V$. Here $\lambda(x,y,G)$ is the maximum number of edge disjoint paths from $x$ to $y$.

For undirected graphs, Nagomochi and Ibaraki shows such graph exist and has an algorithm to find a $r$-rooted-$k$-sparsifier in $O(m)$ time. In fact, it finds a subgraph preserves all local edge and vertex connectivity.

Are there similar results for directed graphs? Or are there a proof that a $r$-rooted-$k$-sparsifier cannot exist for some directed graph?

• For Eulerian digraphs a result of Bang-Jensen, Frank and Jordan gives such a result. epubs.siam.org/doi/abs/10.1137/S0036142993226983, in fact it gives a stronger decomposition result. Similar result is known under slightly less restrictive conditions due to Gabow. For general graphs I don't the answer and am curious as well. My guess would be that the answer is negative. – Chandra Chekuri Jul 18 '14 at 4:08

Let $d^+_G(x)$ be the in-degree of $x$ in graph $G$.
Theorem (LovĂˇsz 1973): For a directed graph $G$ and a specified vertex $r$, there exist a subgraph $G'$ with the property that $d^+_{G'}(x) = \lambda(r,x,G') = \lambda(r,x,G)$.