Skip to main content

Sparsification of directed graphs via cut balance

Publication ,  Conference
Cen, R; Cheng, Y; Panigrahi, D; Sun, K
Published in: Leibniz International Proceedings in Informatics, LIPIcs
July 1, 2021

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úr 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).

Duke Scholars

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

Publication Date

July 1, 2021

Volume

198

Related Subject Headings

  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cen, R., Cheng, Y., Panigrahi, D., & Sun, K. (2021). Sparsification of directed graphs via cut balance. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 198). https://doi.org/10.4230/LIPIcs.ICALP.2021.45
Cen, R., Y. Cheng, D. Panigrahi, and K. Sun. “Sparsification of directed graphs via cut balance.” In Leibniz International Proceedings in Informatics, LIPIcs, Vol. 198, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.45.
Cen R, Cheng Y, Panigrahi D, Sun K. Sparsification of directed graphs via cut balance. In: Leibniz International Proceedings in Informatics, LIPIcs. 2021.
Cen, R., et al. “Sparsification of directed graphs via cut balance.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 198, 2021. Scopus, doi:10.4230/LIPIcs.ICALP.2021.45.
Cen R, Cheng Y, Panigrahi D, Sun K. Sparsification of directed graphs via cut balance. Leibniz International Proceedings in Informatics, LIPIcs. 2021.

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

Publication Date

July 1, 2021

Volume

198

Related Subject Headings

  • 46 Information and computing sciences