Fully Dynamic Spectral Sparsification of Hypergraphs Article Swipe

PDF

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2502.01421

Spectral hypergraph sparsification, a natural generalization of the well-studied spectral sparsification notion on graphs, has been the subject of intensive research in recent years. In this work, we consider spectral hypergraph sparsification in the dynamic setting, where the goal is to maintain a spectral sparsifier of an undirected, weighted hypergraph subject to a sequence of hyperedge insertions and deletions. For any $0 < \varepsilon \leq 1$, we give the first fully dynamic algorithm for maintaining an $ (1 \pm \varepsilon) $-spectral hypergraph sparsifier of size $ n r^3 \operatorname{poly}\left( \log n, \varepsilon ^{-1} \right) $ with amortized update time $ r^4 \operatorname{poly}\left( \log n, \varepsilon ^{-1} \right) $, where $n$ is the number of vertices of the underlying hypergraph and $r$ is an upper-bound on the rank of hyperedges. Our key contribution is to show that the spanner-based sparsification algorithm of Koutis and Xu (2016) admits a dynamic implementation in the hypergraph setting, thereby extending the dynamic spectral sparsification framework for ordinary graphs by Abraham et al. (2016).

Related Topics

Concepts

Mathematics Computer science Combinatorics Algorithm

Metadata

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

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2502.01421

Digital Object Identifier
Title: Fully Dynamic Spectral Sparsification of Hypergraphs

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-02-03

Full publication date if available
Authors: Gramoz Goranci, Ali Momeni

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

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

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

Direct OA link when available
Concepts: Mathematics, Computer science, Combinatorics, Algorithm

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/W4407170381
doi	https://doi.org/10.48550/arxiv.2502.01421
ids.doi	https://doi.org/10.48550/arxiv.2502.01421
ids.openalex	https://openalex.org/W4407170381
fwci
type	preprint
title	Fully Dynamic Spectral Sparsification of Hypergraphs
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10792
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9524999856948853
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Matrix Theory and Algorithms
topics[1].id	https://openalex.org/T10500
topics[1].field.id	https://openalex.org/fields/22
topics[1].field.display_name	Engineering
topics[1].score	0.9050999879837036
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2206
topics[1].subfield.display_name	Computational Mechanics
topics[1].display_name	Sparse and Compressive Sensing Techniques
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C33923547
concepts[0].level	0
concepts[0].score	0.40452536940574646
concepts[0].wikidata	https://www.wikidata.org/wiki/Q395
concepts[0].display_name	Mathematics
concepts[1].id	https://openalex.org/C41008148
concepts[1].level	0
concepts[1].score	0.39922526478767395
concepts[1].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[1].display_name	Computer science
concepts[2].id	https://openalex.org/C114614502
concepts[2].level	1
concepts[2].score	0.3552449941635132
concepts[2].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[2].display_name	Combinatorics
concepts[3].id	https://openalex.org/C11413529
concepts[3].level	1
concepts[3].score	0.351471483707428
concepts[3].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[3].display_name	Algorithm
keywords[0].id	https://openalex.org/keywords/mathematics
keywords[0].score	0.40452536940574646
keywords[0].display_name	Mathematics
keywords[1].id	https://openalex.org/keywords/computer-science
keywords[1].score	0.39922526478767395
keywords[1].display_name	Computer science
keywords[2].id	https://openalex.org/keywords/combinatorics
keywords[2].score	0.3552449941635132
keywords[2].display_name	Combinatorics
keywords[3].id	https://openalex.org/keywords/algorithm
keywords[3].score	0.351471483707428
keywords[3].display_name	Algorithm
language	en
locations[0].id	pmh:oai:arXiv.org:2502.01421
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.01421
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.01421
locations[1].id	doi:10.48550/arxiv.2502.01421
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.01421
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/A5079275314
authorships[1].author.orcid	https://orcid.org/0000-0001-9707-8290
authorships[1].author.display_name	Ali Momeni
authorships[1].author_position	last
authorships[1].raw_author_name	Momeni, Ali
authorships[1].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.01421
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Fully Dynamic Spectral Sparsification of Hypergraphs
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10792
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9524999856948853
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Matrix Theory and Algorithms
related_works	https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2051487156, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2502.01421
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.01421
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.01421
primary_location.id	pmh:oai:arXiv.org:2502.01421
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.01421
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.01421
publication_date	2025-02-03
publication_year	2025
referenced_works_count	0
abstract_inverted_index.$	76, 85, 94, 99
abstract_inverted_index.a	3, 42, 52, 146
abstract_inverted_index.n	86
abstract_inverted_index.$,	107
abstract_inverted_index.$0	61
abstract_inverted_index.(1	77
abstract_inverted_index.In	24
abstract_inverted_index.Xu	143
abstract_inverted_index.an	46, 75, 122
abstract_inverted_index.by	163
abstract_inverted_index.et	165
abstract_inverted_index.in	21, 32, 149
abstract_inverted_index.is	39, 110, 121, 132
abstract_inverted_index.n,	90, 103
abstract_inverted_index.of	6, 18, 45, 54, 83, 113, 115, 127, 140
abstract_inverted_index.on	12, 124
abstract_inverted_index.to	40, 51, 133
abstract_inverted_index.we	27, 66
abstract_inverted_index.$n$	109
abstract_inverted_index.$r$	120
abstract_inverted_index.1$,	65
abstract_inverted_index.For	59
abstract_inverted_index.Our	129
abstract_inverted_index.\pm	78
abstract_inverted_index.al.	166
abstract_inverted_index.and	57, 119, 142
abstract_inverted_index.any	60
abstract_inverted_index.for	73, 160
abstract_inverted_index.has	14
abstract_inverted_index.key	130
abstract_inverted_index.r^3	87
abstract_inverted_index.r^4	100
abstract_inverted_index.the	7, 16, 33, 37, 68, 111, 116, 125, 136, 150, 155
abstract_inverted_index.<	62
abstract_inverted_index.\leq	64
abstract_inverted_index.\log	89, 102
abstract_inverted_index.been	15
abstract_inverted_index.give	67
abstract_inverted_index.goal	38
abstract_inverted_index.rank	126
abstract_inverted_index.show	134
abstract_inverted_index.size	84
abstract_inverted_index.that	135
abstract_inverted_index.this	25
abstract_inverted_index.time	98
abstract_inverted_index.with	95
abstract_inverted_index.^{-1}	92, 105
abstract_inverted_index.first	69
abstract_inverted_index.fully	70
abstract_inverted_index.where	36, 108
abstract_inverted_index.work,	26
abstract_inverted_index.(2016)	144
abstract_inverted_index.Koutis	141
abstract_inverted_index.admits	145
abstract_inverted_index.graphs	162
abstract_inverted_index.notion	11
abstract_inverted_index.number	112
abstract_inverted_index.recent	22
abstract_inverted_index.update	97
abstract_inverted_index.years.	23
abstract_inverted_index.(2016).	167
abstract_inverted_index.Abraham	164
abstract_inverted_index.\right)	93, 106
abstract_inverted_index.dynamic	34, 71, 147, 156
abstract_inverted_index.graphs,	13
abstract_inverted_index.natural	4
abstract_inverted_index.subject	17, 50
abstract_inverted_index.thereby	153
abstract_inverted_index.Spectral	0
abstract_inverted_index.consider	28
abstract_inverted_index.maintain	41
abstract_inverted_index.ordinary	161
abstract_inverted_index.research	20
abstract_inverted_index.sequence	53
abstract_inverted_index.setting,	35, 152
abstract_inverted_index.spectral	9, 29, 43, 157
abstract_inverted_index.vertices	114
abstract_inverted_index.weighted	48
abstract_inverted_index.algorithm	72, 139
abstract_inverted_index.amortized	96
abstract_inverted_index.extending	154
abstract_inverted_index.framework	159
abstract_inverted_index.hyperedge	55
abstract_inverted_index.intensive	19
abstract_inverted_index.$-spectral	80
abstract_inverted_index.deletions.	58
abstract_inverted_index.hypergraph	1, 30, 49, 81, 118, 151
abstract_inverted_index.insertions	56
abstract_inverted_index.sparsifier	44, 82
abstract_inverted_index.underlying	117
abstract_inverted_index.\varepsilon	63, 91, 104
abstract_inverted_index.hyperedges.	128
abstract_inverted_index.maintaining	74
abstract_inverted_index.undirected,	47
abstract_inverted_index.upper-bound	123
abstract_inverted_index.\varepsilon)	79
abstract_inverted_index.contribution	131
abstract_inverted_index.well-studied	8
abstract_inverted_index.spanner-based	137
abstract_inverted_index.generalization	5
abstract_inverted_index.implementation	148
abstract_inverted_index.sparsification	10, 31, 138, 158
abstract_inverted_index.sparsification,	2
abstract_inverted_index.\operatorname{poly}\left(	88, 101
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile