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.ESA.2021.21
URN: urn:nbn:de:0030-drops-146029
Go to the corresponding LIPIcs Volume Portal

Bläsius, Thomas ; Friedrich, Tobias ; Weyand, Christopher

Efficiently Computing Maximum Flows in Scale-Free Networks

LIPIcs-ESA-2021-21.pdf (0.7 MB)


We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on the fact that often only a small fraction of such a network is relevant for the flow. At its core, our algorithm augments Dinitz’s algorithm with a balanced bidirectional search. Our experiments on a scale-free random network model indicate sublinear run time. On scale-free real-world networks, we outperform the commonly used highest-label Push-Relabel implementation by up to two orders of magnitude. Compared to Dinitz’s original algorithm, our modifications reduce the search space, e.g., by a factor of 275 on an autonomous systems graph.
Beyond these good run times, our algorithm has an additional advantage compared to Push-Relabel. The latter computes a preflow, which makes the extraction of a minimum cut potentially more difficult. This is relevant, for example, for the computation of Gomory-Hu trees. On a social network with 70000 nodes, our algorithm computes the Gomory-Hu tree in 3 seconds compared to 12 minutes when using Push-Relabel.

BibTeX - Entry

  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Weyand, Christopher},
  title =	{{Efficiently Computing Maximum Flows in Scale-Free Networks}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-146029},
  doi =		{10.4230/LIPIcs.ESA.2021.21},
  annote =	{Keywords: graphs, flow, network, scale-free}

Keywords: graphs, flow, network, scale-free
Collection: 29th Annual European Symposium on Algorithms (ESA 2021)
Issue Date: 2021
Date of publication: 31.08.2021
Supplementary Material: Software (code and data): archived at:

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