<p>Let $d^+_G(x)$ be the in-degree of $x$ in graph $G$.</p>

<p><strong>Theorem (<a href="http://www.sciencedirect.com/science/article/pii/009589567390018X" rel="nofollow">Lovász 1973</a>):</strong> 
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)$.</p>

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

CC BY-SA 3.0
2015-12-23T18:14:57.177Z
2015-12-23T18:14:57.177Z
Chao Xu
<p>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$.</p>

<p>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. </p>

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

CC BY-SA 3.0
2014-07-18T04:08:34.143Z
For Eulerian digraphs a result of Bang-Jensen, Frank and Jordan gives such a result. http://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
<graph-theory>
Sparse subgraph preserving rooted edge connectivity up to $k$
Chao Xu
# Sparse subgraph preserving rooted edge connectivity up to $k$

(Asked by: username_0 on 2014-07-17)

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?

**Tags:** graph-theory
> **Comments:**
> **username_1**: For Eulerian digraphs a result of Bang-Jensen, Frank and Jordan gives such a result. http://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.  

---

## 1 answers

### Answer by username_0 on 2015-12-23. Score: 2 | Accepted answer

Let $d^+\_G(x)$ be the in-degree of $x$ in graph $G$.

**Theorem ([Lovász 1973](http://www.sciencedirect.com/science/article/pii/009589567390018X)):**
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.


---

