2026-07-21T14:16:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24249 2025-11-12T13:39:25Z ddc:004 open_access

Parameterized Streaming Algorithms for Topological Sorting Chen, Ho-Lin Lin, Peng-Ting Tsai, Meng-Tsung Independence Number Chain Cover SCC Decomposition 2-Satisfiability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ho-Lin Chen and Peng-Ting Lin and Meng-Tsung Tsai 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.18 urn:nbn:de:0030-drops-242495 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.18 eng https://creativecommons.org/licenses/by/4.0/legalcode