2026-08-09T16:34:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17553 2024-03-06T10:59:53Z ddc:004 open_access

Expander Decomposition in Dynamic Streams Filtser, Arnold Kapralov, Michael Makarov, Mikhail Streaming expander decomposition graph sparsifiers In this paper we initiate the study of expander decompositions of a graph G = (V, E) in the streaming model of computation. The goal is to find a partitioning 𝒞 of vertices V such that the subgraphs of G induced by the clusters C ∈ 𝒞 are good expanders, while the number of intercluster edges is small. Expander decompositions are classically constructed by a recursively applying balanced sparse cuts to the input graph. In this paper we give the first implementation of such a recursive sparsest cut process using small space in the dynamic streaming model. Our main algorithmic tool is a new type of cut sparsifier that we refer to as a power cut sparsifier - it preserves cuts in any given vertex induced subgraph (or, any cluster in a fixed partition of V) to within a (δ, ε)-multiplicative/additive error with high probability. The power cut sparsifier uses Õ(n/εδ) space and edges, which we show is asymptotically tight up to polylogarithmic factors in n for constant δ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnold Filtser and Michael Kapralov and Mikhail Makarov 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.50 urn:nbn:de:0030-drops-175534 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.50 eng https://creativecommons.org/licenses/by/4.0/legalcode