2026-09-08T02:22:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26411 2026-09-05T19:42:35Z ddc:004 open_access

Expander Decomposition with Almost Optimal Overhead Bansal, Nikhil Jambulapati, Arun Saranurak, Thatchaphol Graph algorithms expander decomposition flow expansion sparse cuts We present the first polynomial-time algorithm for computing a near-optimal flow-expander decomposition. Given a graph G and a parameter ϕ, our algorithm removes at most a ϕlog^{1+o(1)}n fraction of edges so that every remaining connected component is a ϕ-flow-expander (a stronger guarantee than being a ϕ-cut-expander). This achieves overhead log^{1+o(1)}n, nearly matching the Ω(log n) graph-theoretic lower bound that already holds for cut-expander decompositions, up to a log^{o(1)}n factor. Prior polynomial-time algorithms required removing O(ϕlog^{1.5}n) and O(ϕlog²n) fractions of edges to guarantee ϕ-cut-expander and ϕ-flow-expander components, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Bansal and Arun Jambulapati and Thatchaphol Saranurak 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.22 urn:nbn:de:0030-drops-264113 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.22 eng https://creativecommons.org/licenses/by/4.0/legalcode