Sparse subgraph preserving rooted edge connectivity up to $k$

Question

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?

Answer 1

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

The desired sparse graph exists, as we can keep removing edges to reach a minimal graph with the desired connectivity property.