2026-08-10T23:42:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9147 2024-03-06T10:43:28Z ddc:004 open_access

Congestion-Free Rerouting of Flows on DAGs Akhoondian Amiri, Saeed Dudycz, Szymon Schmid, Stefan Wiederrecht, Sebastian Unsplittable Flows Reconfiguration DAGs FPT NP-Hardness Changing a given configuration in a graph into another one is known as a reconfiguration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute k unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for k=2 flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general k, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Saeed Akhoondian Amiri and Szymon Dudycz and Stefan Schmid and Sebastian Wiederrecht 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.143 urn:nbn:de:0030-drops-91471 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.143 eng https://creativecommons.org/licenses/by/3.0/legalcode