Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.45
URN: urn:nbn:de:0030-drops-141143
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14114/
Cen, Ruoxu ; Cheng, Yu ; Panigrahi, Debmalya ; Sun, Kevin
Sparsification of Directed Graphs via Cut Balance
| pdf-format: |
|
Abstract
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).
BibTeX - Entry
@InProceedings{cen_et_al:LIPIcs.ICALP.2021.45,
author = {Cen, Ruoxu and Cheng, Yu and Panigrahi, Debmalya and Sun, Kevin},
title = {{Sparsification of Directed Graphs via Cut Balance}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {45:1--45:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14114},
URN = {urn:nbn:de:0030-drops-141143},
doi = {10.4230/LIPIcs.ICALP.2021.45},
annote = {Keywords: Graph sparsification, directed graphs, cut sketches, space complexity}
}
| Keywords: | Graph sparsification, directed graphs, cut sketches, space complexity | |
| Seminar: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 02.07.2021 |
