Sparsification, where the cut values of an input graph are approximately preserved by a sparse graph (called a cut sparsifier) or a succinct data structure (called a cut sketch), has been an influential tool in graph algorithms. But, this tool is restricted to undirected graphs, because some directed graphsare known to not admit sparsification. Such examples, however, are structurally very dissimilar to undirected graphs in that they exhibit highly unbalanced cuts. This motivates us to ask: can we sparsify a balanced digraph? To make this question concrete, we define balance \beta of a digraph as the maximum ratio of the cut value in the two directions (Ene et al., STOC 2016). We show the following results: For-All Sparsification: If all cut values need to be simultaneously preserved (cf. Bencz\'ur and Karger, STOC 1996) , then we show that the size of the sparsifier (or even cut sketch) must scale linearly with \beta. The upper bound is a simple extension of sparsification of undirected graphs (formally stated recently in Ikeda and Tanigawa (WAOA 2018)), so our main contribution here is to show a matching lower bound. For-Each Sparsification: If each cut value needs to be individually preserved ( Andoni et al., ITCS 2016) , then the situation is more interesting. Here, we give a cut sketch whose size scales with \sqrt{\beta We also show that this result is tight by exhibiting a matching lower bound of \sqrt{\beta .
In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected and directed graphs. We give nearly matching upper and lower bounds for both for-all (cf. Bencz\'ur and Karger, STOC 1996) and for-each ( Andoni et al., ITCS 2016) cut sparsifiers/sketches as a function of cut balance, defined the maximum ratio of the cut value in the two directions of a directed graph (Ene et al., STOC 2016). We also show an interesting application of digraph sparsification via cut balance by using it to give a very short proof of a celebrated maximum flow result of Karger and Levine (STOC 2002) .
R
Sparsification, where the cut values of an input graph are approximately preserved by a sparse graph (called a cut sparsifier) or a succinct data structure (called a cut sketch), has been an influential tool in graph algorithms. But, this tool is restricted to undirected graphs, because some directed graphsare known to not admit sparsification. Such examples, however, are structurally very dissimilar to undirected graphs in that they exhibit highly unbalanced cuts. This motivates us to ask: can we sparsify a balanced digraph? To make this question concrete, we define balance \beta of a digraph as the maximum ratio of the cut value in the two directions (Ene et al., STOC 2016). We show the following results: For-All Sparsification: If all cut values need to be simultaneously preserved
In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected and directed graphs. We give nearly matching upper and lower bounds for both for-all
R
, then we show that the size of the sparsifier (or even cut sketch) must scale linearly with \beta. The upper bound is a simple extension of sparsification of undirected graphs (formally stated recently in Ikeda and Tanigawa (WAOA 2018)), so our main contribution here is to show a matching lower bound. For-Each Sparsification: If each cut value needs to be individually preserved (
and for-each (
R
, then the situation is more interesting. Here, we give a cut sketch whose size scales with \sqrt{\beta
cut sparsifiers/sketches as a function of cut balance, defined the maximum ratio of the cut value in the two directions of a directed graph (Ene et al., STOC 2016).
R
that this result is tight by exhibiting a matching lower bound of \sqrt{\beta
an interesting application of digraph sparsification via cut balance by using it to give a very short proof of a celebrated maximum flow result of Karger and Levine (STOC 2002)