2026-07-24T18:10:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24576 2025-12-16T14:01:03Z ddc:004 open_access

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts Haeupler, Bernhard Long, Yaowei Saranurak, Thatchaphol Wang, Shengzhe Length-Constrained Expander Expander Decomposition Shortcut We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2022; Haeupler et al., 2024]. Along the way, we prove the multi-commodity maxflow-mincut theorems for length-constrained expansion in both directed and undirected vertex-capacitated graphs. Based on our decomposition, we build a length-constrained flow shortcut for undirected vertex-capacitated graphs, which roughly speaking is a set of edges and vertices added to the graph so that every multi-commodity flow demand can be routed with approximately the same vertex-congestion and length, but all flow paths only contain few edges. This generalizes the shortcut for undirected edge-capacitated graphs from [Bernhard Haeupler et al., 2024]. Length-constrained expander decomposition and flow shortcuts have been crucial in the recent algorithms in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2024; Haeupler et al., 2024]. Our work thus serves as a foundation to generalize these concepts to directed and vertex-capacitated graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bernhard Haeupler and Yaowei Long and Thatchaphol Saranurak and Shengzhe Wang 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.107 urn:nbn:de:0030-drops-245765 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.107 eng https://creativecommons.org/licenses/by/4.0/legalcode