License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.61
URN: urn:nbn:de:0030-drops-164029
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16402/
Go to the corresponding LIPIcs Volume Portal

Forster, Sebastian ; de Vos, Tijn

Faster Cut Sparsification of Weighted Graphs

pdf-format:
LIPIcs-ICALP-2022-61.pdf (0.8 MB)

Abstract

A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of (1±ε). This paper considers computing cut sparsifiers of weighted graphs of size O(nlog (n)/ε²). Our algorithm computes such a sparsifier in time O(m⋅min(α(n)log(m/n),log (n))), both for graphs with polynomially bounded and unbounded integer weights, where α(⋅) is the functional inverse of Ackermann’s function. This improves upon the state of the art by Benczúr and Karger (SICOMP 2015), which takes O(mlog² (n)) time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest packing. MSF packings have previously been used by Abraham at al. (FOCS 2016) in the dynamic setting, and are defined as follows: an M-partial MSF packing of G is a set ℱ = {F₁, … , F_M}, where F_i is a maximum spanning forest in G⧵ ⋃_{j = 1}^{i-1}F_j. Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

BibTeX - Entry

@InProceedings{forster_et_al:LIPIcs.ICALP.2022.61,
  author =	{Forster, Sebastian and de Vos, Tijn},
  title =	{{Faster Cut Sparsification of Weighted Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{61:1--61:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16402},
  URN =		{urn:nbn:de:0030-drops-164029},
  doi =		{10.4230/LIPIcs.ICALP.2022.61},
  annote =	{Keywords: Cut Sparsification, Graph Algorithms}
}

Keywords: Cut Sparsification, Graph Algorithms
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI