2 Search Results for "Tanigawa, Shin-ichi"

Document

DOI: 10.4230/LIPIcs.STACS.2026.38

Fully Dynamic Spectral Sparsification for Directed Hypergraphs

Authors: Sebastian Forster, Gramoz Goranci, and Ali Momeni

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of directed hypergraphs. Our algorithm achieves a near-optimal size of O(n² / ε ² log ⁷ m) and amortized update time of O(r² log ³ m), where n is the number of vertices, and m and r respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any k hyperedge insertions or deletions can be processed with O(kr² log ³ m) amortized work and O(log ² m) depth. This constitutes the first spectral-based sparsification algorithm in this setting.

Cite as

Sebastian Forster, Gramoz Goranci, and Ali Momeni. Fully Dynamic Spectral Sparsification for Directed Hypergraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.STACS.2026.38,
  author =	{Forster, Sebastian and Goranci, Gramoz and Momeni, Ali},
  title =	{{Fully Dynamic Spectral Sparsification for Directed Hypergraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.38},
  URN =		{urn:nbn:de:0030-drops-255272},
  doi =		{10.4230/LIPIcs.STACS.2026.38},
  annote =	{Keywords: Spectral sparsification, Dynamic algorithms, (Directed) hypergraphs, Data structures}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2023.94

Nearly Tight Spectral Sparsification of Directed Hypergraphs

Authors: Kazusato Oko, Shinsaku Sakaue, and Shin-ichi Tanigawa

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract

Spectral hypergraph sparsification, an attempt to extend well-known spectral graph sparsification to hypergraphs, has been extensively studied over the past few years. For undirected hypergraphs, Kapralov, Krauthgamer, Tardos, and Yoshida (2022) have proved an ε-spectral sparsifier of the optimal O^*(n) size, where n is the number of vertices and O^* suppresses the ε^{-1} and log n factors. For directed hypergraphs, however, the optimal sparsifier size has not been known. Our main contribution is the first algorithm that constructs an O^*(n²)-size ε-spectral sparsifier for a weighted directed hypergraph. Our result is optimal up to the ε^{-1} and log n factors since there is a lower bound of Ω(n²) even for directed graphs. We also show the first non-trivial lower bound of Ω(n²/ε) for general directed hypergraphs. The basic idea of our algorithm is borrowed from the spanner-based sparsification for ordinary graphs by Koutis and Xu (2016). Their iterative sampling approach is indeed useful for designing sparsification algorithms in various circumstances. To demonstrate this, we also present a similar iterative sampling algorithm for undirected hypergraphs that attains one of the best size bounds, enjoys parallel implementation, and can be transformed to be fault-tolerant.

Cite as

Kazusato Oko, Shinsaku Sakaue, and Shin-ichi Tanigawa. Nearly Tight Spectral Sparsification of Directed Hypergraphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 94:1-94:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oko_et_al:LIPIcs.ICALP.2023.94,
  author =	{Oko, Kazusato and Sakaue, Shinsaku and Tanigawa, Shin-ichi},
  title =	{{Nearly Tight Spectral Sparsification of Directed Hypergraphs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{94:1--94:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.94},
  URN =		{urn:nbn:de:0030-drops-181469},
  doi =		{10.4230/LIPIcs.ICALP.2023.94},
  annote =	{Keywords: Spectral sparsification, (Directed) hypergraphs, Iterative sampling}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2026
1 2023

Refine by Author
1 Forster, Sebastian
1 Goranci, Gramoz
1 Momeni, Ali
1 Oko, Kazusato
1 Sakaue, Shinsaku
Show More...

Refine by Series/Journal
2 LIPIcs

Refine by Classification
2 Theory of computation → Sparsification and spanners

Refine by Keyword
2 (Directed) hypergraphs
2 Spectral sparsification
1 Data structures
1 Dynamic algorithms
1 Iterative sampling

2 Search Results for "Tanigawa, Shin-ichi"

Fully Dynamic Spectral Sparsification for Directed Hypergraphs

Abstract

Cite as

Nearly Tight Spectral Sparsification of Directed Hypergraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message