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?

  • 2
    $\begingroup$ 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. $\endgroup$ – 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)$.

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.