License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.143
URN: urn:nbn:de:0030-drops-91471
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9147/
Go to the corresponding LIPIcs Volume Portal

Akhoondian Amiri, Saeed ; Dudycz, Szymon ; Schmid, Stefan ; Wiederrecht, Sebastian

Congestion-Free Rerouting of Flows on DAGs

pdf-format:
LIPIcs-ICALP-2018-143.pdf (0.5 MB)

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 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.

BibTeX - Entry

@InProceedings{akhoondianamiri_et_al:LIPIcs:2018:9147,
  author =	{Saeed Akhoondian Amiri and Szymon Dudycz and Stefan Schmid and Sebastian Wiederrecht},
  title =	{{Congestion-Free Rerouting of Flows on DAGs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{143:1--143:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9147},
  URN =		{urn:nbn:de:0030-drops-91471},
  doi =		{10.4230/LIPIcs.ICALP.2018.143},
  annote =	{Keywords: Unsplittable Flows, Reconfiguration, DAGs, FPT, NP-Hardness}
}

Keywords: Unsplittable Flows, Reconfiguration, DAGs, FPT, NP-Hardness
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI