DROPS

Document

DOI: 10.4230/LIPIcs.WADS.2025.18

Parameterized Streaming Algorithms for Topological Sorting

Authors: Ho-Lin Chen, Peng-Ting Lin, and Meng-Tsung Tsai

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

Computing a topological ordering for an n-node directed acyclic graph (DAG) G is computationally challenging in streaming models. Chakrabarti et al. {[}SODA 2020{]} showed that in the insertion-only streaming model, every single-pass algorithm requires Ω(n²) space, and every k-pass algorithm requires n^{1+Ω(1/k)} space for any constant k ≥ 1. We study the parameterized complexity of streaming algorithms for topological sorting, considering two parameters: the independence number α and the maximum displacement δ. Our results include an O(1/ε)-pass O(α n^{1+ε})-space streaming algorithm and an O(n^{1/2})-pass O(n+δ²)-space streaming algorithm. For dense random DAGs, both α and δ are small, allowing us to improve the state-of-the-art for topological sorting in random DAGs. As applications, we show that strongly connected components (SCC) decomposition and 2-satisfiability (2-SAT) can be solved in O(1/ε) passes using O(α n^{1+ε}) space and O(α_I n^{1+ε}) space, respectively, where α_I denotes the independence number of the implication graph induced by the input 2-SAT instance.

Cite as

Ho-Lin Chen, Peng-Ting Lin, and Meng-Tsung Tsai. Parameterized Streaming Algorithms for Topological Sorting. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.WADS.2025.18,
  author =	{Chen, Ho-Lin and Lin, Peng-Ting and Tsai, Meng-Tsung},
  title =	{{Parameterized Streaming Algorithms for Topological Sorting}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.18},
  URN =		{urn:nbn:de:0030-drops-242495},
  doi =		{10.4230/LIPIcs.WADS.2025.18},
  annote =	{Keywords: Independence Number, Chain Cover, SCC Decomposition, 2-Satisfiability}
}

Search Results

Documents authored by Lin, Peng-Ting

Parameterized Streaming Algorithms for Topological Sorting

Abstract

Cite as

Thanks for your feedback!

Could not send message