We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$(\varepsilon , \delta )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>ε</mi> <mo>,</mo> <mi>δ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-spectral sparsifier with multiplicative error <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation> and additive error <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> </math></EquationSource> </InlineEquation> that has <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(\varepsilon ^{-2} n \log n \log r \log (1 + \varepsilon W/\delta n))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>ε</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo>log</mo> <mi>r</mi> <mo>log</mo> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>ε</mi> <mi>W</mi> <mo stretchy="false">/</mo> <mi>δ</mi> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> hyperedges with high probability, where <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varepsilon , \delta \in (0,1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>,</mo> <mi>δ</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, n is the number of nodes, r is the rank of the hypergraph, and W is the sum of edge weights. The space complexity of our algorithm is <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$O(n^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, while previous algorithms required space complexity <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\varOmega (m)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Ω</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where m is the number of hyperedges. This provides an exponential improvement in the space complexity since m can be exponential in n.

Online Algorithms for Spectral Hypergraph Sparsification

期刊论文
发表日期：

2025年12月10日

查看全文

Tasuku Soma,
Kam Chuen Tung,
Yuichi Yoshida

摘要

We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an $(\varepsilon , \delta )$ $(ε, δ)$ -spectral sparsifier with multiplicative error $\varepsilon $ $ε$ and additive error $\delta $ $δ$ that has $O(\varepsilon ^{-2} n \log n \log r \log (1 + \varepsilon W/\delta n))$ $O (ε^{- 2} n log n log r log (1 + ε W / δ n))$ hyperedges with high probability, where $\varepsilon , \delta \in (0,1)$ $ε, δ \in (0, 1)$ , n is the number of nodes, r is the rank of the hypergraph, and W is the sum of edge weights. The space complexity of our algorithm is $O(n^2)$ $O (n^{2})$ , while previous algorithms required space complexity $\varOmega (m)$ $Ω (m)$ , where m is the number of hyperedges. This provides an exponential improvement in the space complexity since m can be exponential in n.