MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Congestion Free Rerouting of Flows (practice talk for ICALP)

Saeed Amiri
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 3 July 2018
13:00
30 Minutes
E1 4
024
Saarbrücken

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.

Contact

Saeed Amiri
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

reconfiguration, algorithm, FPT, flow, rerouting
If you like to have a quick look, you can find the early version of the paper here: https://arxiv.org/abs/1611.09296

Saeed Amiri, 06/04/2018 10:35 -- Created document.