Incremental Approximate Maximum Flow via Residual Graph Sparsification Article Swipe

PDF

Gramoz Goranci , Monika Henzinger , Harald Räcke , A. R. Sricharan ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.4230/lipics.icalp.2025.91

We give an algorithm that, with high probability, maintains a (1-ε)-approximate s-t maximum flow in undirected, uncapacitated n-vertex graphs undergoing m edge insertions in Õ(m+ n F^*/ε) total update time, where F^{*} is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs (m = Ω(n²)), and more generally, for graphs where F^* = Õ(m/n). At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [SICOMP '15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [SICOMP '19] from undirected graphs to balanced directed graphs.

Related Topics

Concepts

Residual Graph Flow (mathematics) Maximum flow problem Mathematics Computer science Combinatorics Algorithm Geometry

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2502.09105
PDF: https://arxiv.org/pdf/2502.09105
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4407571812

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4407571812

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.4230/lipics.icalp.2025.91

Digital Object Identifier
Title: Incremental Approximate Maximum Flow via Residual Graph Sparsification

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-01-01

Full publication date if available
Authors: Gramoz Goranci, Monika Henzinger, Harald Räcke, A. R. Sricharan

List of authors in order
Landing page: https://arxiv.org/abs/2502.09105

Publisher landing page
PDF URL: https://arxiv.org/pdf/2502.09105

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2502.09105

Direct OA link when available
Concepts: Residual, Graph, Flow (mathematics), Maximum flow problem, Mathematics, Computer science, Combinatorics, Algorithm, Geometry

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4407571812
doi	https://doi.org/10.4230/lipics.icalp.2025.91
ids.doi	https://doi.org/10.48550/arxiv.2502.09105
ids.openalex	https://openalex.org/W4407571812
fwci	0.0
type	preprint
title	Incremental Approximate Maximum Flow via Residual Graph Sparsification
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11273
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9815999865531921
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Advanced Graph Neural Networks
topics[1].id	https://openalex.org/T12072
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9743000268936157
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	Machine Learning and Algorithms
topics[2].id	https://openalex.org/T11612
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9715999960899353
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1702
topics[2].subfield.display_name	Artificial Intelligence
topics[2].display_name	Stochastic Gradient Optimization Techniques
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C155512373
concepts[0].level	2
concepts[0].score	0.7095137238502502
concepts[0].wikidata	https://www.wikidata.org/wiki/Q287450
concepts[0].display_name	Residual
concepts[1].id	https://openalex.org/C132525143
concepts[1].level	2
concepts[1].score	0.5691107511520386
concepts[1].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[1].display_name	Graph
concepts[2].id	https://openalex.org/C38349280
concepts[2].level	2
concepts[2].score	0.4855477511882782
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1434290
concepts[2].display_name	Flow (mathematics)
concepts[3].id	https://openalex.org/C157469704
concepts[3].level	2
concepts[3].score	0.45312973856925964
concepts[3].wikidata	https://www.wikidata.org/wiki/Q2585642
concepts[3].display_name	Maximum flow problem
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.4458518624305725
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C41008148
concepts[5].level	0
concepts[5].score	0.3862031102180481
concepts[5].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[5].display_name	Computer science
concepts[6].id	https://openalex.org/C114614502
concepts[6].level	1
concepts[6].score	0.3624013662338257
concepts[6].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[6].display_name	Combinatorics
concepts[7].id	https://openalex.org/C11413529
concepts[7].level	1
concepts[7].score	0.28560638427734375
concepts[7].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[7].display_name	Algorithm
concepts[8].id	https://openalex.org/C2524010
concepts[8].level	1
concepts[8].score	0.1848078966140747
concepts[8].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[8].display_name	Geometry
keywords[0].id	https://openalex.org/keywords/residual
keywords[0].score	0.7095137238502502
keywords[0].display_name	Residual
keywords[1].id	https://openalex.org/keywords/graph
keywords[1].score	0.5691107511520386
keywords[1].display_name	Graph
keywords[2].id	https://openalex.org/keywords/flow
keywords[2].score	0.4855477511882782
keywords[2].display_name	Flow (mathematics)
keywords[3].id	https://openalex.org/keywords/maximum-flow-problem
keywords[3].score	0.45312973856925964
keywords[3].display_name	Maximum flow problem
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.4458518624305725
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/computer-science
keywords[5].score	0.3862031102180481
keywords[5].display_name	Computer science
keywords[6].id	https://openalex.org/keywords/combinatorics
keywords[6].score	0.3624013662338257
keywords[6].display_name	Combinatorics
keywords[7].id	https://openalex.org/keywords/algorithm
keywords[7].score	0.28560638427734375
keywords[7].display_name	Algorithm
keywords[8].id	https://openalex.org/keywords/geometry
keywords[8].score	0.1848078966140747
keywords[8].display_name	Geometry
language	en
locations[0].id	pmh:oai:arXiv.org:2502.09105
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2502.09105
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2502.09105
locations[1].id	doi:10.48550/arxiv.2502.09105
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2502.09105
locations[2].id	doi:10.4230/lipics.icalp.2025.91
locations[2].is_oa	True
locations[2].source.id	https://openalex.org/S7407052059
locations[2].source.type	repository
locations[2].source.is_oa	False
locations[2].source.issn_l
locations[2].source.is_core	False
locations[2].source.is_in_doaj	False
locations[2].source.display_name	Dagstuhl Research Online Publication Server
locations[2].source.host_organization
locations[2].source.host_organization_name
locations[2].license	cc-by
locations[2].pdf_url
locations[2].version
locations[2].raw_type
locations[2].license_id	https://openalex.org/licenses/cc-by
locations[2].is_accepted	False
locations[2].is_published
locations[2].raw_source_name
locations[2].landing_page_url	https://doi.org/10.4230/lipics.icalp.2025.91
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5078315645
authorships[0].author.orcid	https://orcid.org/0000-0002-9603-2255
authorships[0].author.display_name	Gramoz Goranci
authorships[0].author_position	first
authorships[0].raw_author_name	Goranci, Gramoz
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5003641345
authorships[1].author.orcid	https://orcid.org/0000-0002-5008-6530
authorships[1].author.display_name	Monika Henzinger
authorships[1].author_position	middle
authorships[1].raw_author_name	Henzinger, Monika
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5016682913
authorships[2].author.orcid	https://orcid.org/0000-0001-8797-717X
authorships[2].author.display_name	Harald Räcke
authorships[2].author_position	middle
authorships[2].raw_author_name	Räcke, Harald
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5066738665
authorships[3].author.orcid
authorships[3].author.display_name	A. R. Sricharan
authorships[3].author_position	last
authorships[3].raw_author_name	Sricharan, A. R.
authorships[3].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2502.09105
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-02-15T00:00:00
display_name	Incremental Approximate Maximum Flow via Residual Graph Sparsification
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11273
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9815999865531921
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Advanced Graph Neural Networks
related_works	https://openalex.org/W4300237897, https://openalex.org/W2003930232, https://openalex.org/W2263167076, https://openalex.org/W4311255633, https://openalex.org/W2368007657, https://openalex.org/W2391191500, https://openalex.org/W4297894118, https://openalex.org/W2365398175, https://openalex.org/W1979748118, https://openalex.org/W2641655
cited_by_count	0
locations_count	3
best_oa_location.id	pmh:oai:arXiv.org:2502.09105
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2502.09105
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2502.09105
primary_location.id	pmh:oai:arXiv.org:2502.09105
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2502.09105
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2502.09105
publication_date	2025-01-01
publication_year	2025
referenced_works_count	0
abstract_inverted_index.=	55, 64
abstract_inverted_index.a	9
abstract_inverted_index.m	20
abstract_inverted_index.n	25
abstract_inverted_index.(m	54
abstract_inverted_index.At	66
abstract_inverted_index.We	0
abstract_inverted_index.an	2
abstract_inverted_index.et	124
abstract_inverted_index.in	14, 23, 92, 111
abstract_inverted_index.is	32, 41, 73
abstract_inverted_index.of	69, 79, 122
abstract_inverted_index.on	36
abstract_inverted_index.to	45, 103, 131
abstract_inverted_index.(i)	100
abstract_inverted_index.F^*	63
abstract_inverted_index.Our	96
abstract_inverted_index.al.	125
abstract_inverted_index.and	57, 81, 115
abstract_inverted_index.are	99
abstract_inverted_index.cut	119
abstract_inverted_index.for	51, 60, 87, 107
abstract_inverted_index.how	102
abstract_inverted_index.our	70
abstract_inverted_index.s-t	11
abstract_inverted_index.the	33, 37, 42, 67, 74, 93, 112, 118
abstract_inverted_index.'19]	127
abstract_inverted_index.(ii)	116
abstract_inverted_index.Fung	123
abstract_inverted_index.This	40
abstract_inverted_index.edge	21
abstract_inverted_index.flow	13, 35
abstract_inverted_index.from	128
abstract_inverted_index.give	1
abstract_inverted_index.high	6
abstract_inverted_index.main	97
abstract_inverted_index.more	58
abstract_inverted_index.such	105
abstract_inverted_index.time	50
abstract_inverted_index.with	5
abstract_inverted_index.'15],	84
abstract_inverted_index.F^{*}	31
abstract_inverted_index.dense	52
abstract_inverted_index.exact	89
abstract_inverted_index.final	38
abstract_inverted_index.first	43
abstract_inverted_index.flows	91, 110
abstract_inverted_index.graph	76
abstract_inverted_index.heart	68
abstract_inverted_index.that,	4
abstract_inverted_index.time,	29
abstract_inverted_index.total	27
abstract_inverted_index.where	30, 62
abstract_inverted_index.Karger	80
abstract_inverted_index.Levine	82
abstract_inverted_index.Õ(m+	24
abstract_inverted_index.graph.	39
abstract_inverted_index.graphs	18, 53, 61, 130
abstract_inverted_index.static	94
abstract_inverted_index.update	28, 49
abstract_inverted_index.F^*/ε)	26
abstract_inverted_index.[SICOMP	83, 126
abstract_inverted_index.achieve	46
abstract_inverted_index.graphs.	134
abstract_inverted_index.maximum	12, 34, 90, 109
abstract_inverted_index.setting	114
abstract_inverted_index.showing	101
abstract_inverted_index.balanced	132
abstract_inverted_index.designed	86
abstract_inverted_index.directed	133
abstract_inverted_index.maintain	104
abstract_inverted_index.n-vertex	17
abstract_inverted_index.residual	75
abstract_inverted_index.setting.	95
abstract_inverted_index.Õ(m/n).	65
abstract_inverted_index.algorithm	3, 44, 72
abstract_inverted_index.amortized	48
abstract_inverted_index.computing	88
abstract_inverted_index.framework	121
abstract_inverted_index.maintains	8
abstract_inverted_index.technique	78
abstract_inverted_index.Ω(n²)),	56
abstract_inverted_index.generally,	59
abstract_inverted_index.insertions	22
abstract_inverted_index.originally	85
abstract_inverted_index.undergoing	19
abstract_inverted_index.undirected	129
abstract_inverted_index.approximate	108
abstract_inverted_index.incremental	71, 113
abstract_inverted_index.sparsifiers	106
abstract_inverted_index.undirected,	15
abstract_inverted_index.generalizing	117
abstract_inverted_index.probability,	7
abstract_inverted_index.contributions	98
abstract_inverted_index.uncapacitated	16
abstract_inverted_index.sparsification	77, 120
abstract_inverted_index.polylogarithmic	47
abstract_inverted_index.(1-ε)-approximate	10
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile.value	0.01620873
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True