Sparsification of directed graphs via cut balance

Conference Paper

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

Full Text

Duke Authors

Cited Authors

  • Cen, R; Cheng, Y; Panigrahi, D; Sun, K

Published Date

  • July 1, 2021

Published In

Volume / Issue

  • 198 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959771955

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.ICALP.2021.45

Citation Source

  • Scopus