Akhoondian Amiri, Saeed ;
Dudycz, Szymon ;
Schmid, Stefan ;
Wiederrecht, Sebastian
CongestionFree Rerouting of Flows on DAGs
Abstract
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 congestionfree manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NPhard 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 multicommodity flow rerouting schedule exists, is NPhard even on DAGs. Our main contribution is a polynomialtime (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.
BibTeX  Entry
@InProceedings{akhoondianamiri_et_al:LIPIcs:2018:9147,
author = {Saeed Akhoondian Amiri and Szymon Dudycz and Stefan Schmid and Sebastian Wiederrecht},
title = {{CongestionFree Rerouting of Flows on DAGs}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {143:1143:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9147},
URN = {urn:nbn:de:0030drops91471},
doi = {10.4230/LIPIcs.ICALP.2018.143},
annote = {Keywords: Unsplittable Flows, Reconfiguration, DAGs, FPT, NPHardness}
}
2018
Keywords: 

Unsplittable Flows, Reconfiguration, DAGs, FPT, NPHardness 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

2018 