---
OA_place: other
OA_type: green
_id: '18925'
abstract:
- lang: eng
  text: Given the increasingly stringent requirements on the performance and efficiency
    of communication networks, over the last years, great efforts have been made to
    render networks more flexible and programmable. In particular, modern networks
    support a flexible rerouting of flows, e.g., depending on the dynamically changing
    traffic or network conditions. However, the underlying algorithmic problems are
    still not well-understood today.In this paper, we revisit the k-Network Flow Update
    problem that asks for a schedule to reroute k unsplittable flows from their current
    paths to the given new paths, in a congestion-free manner in a capacitated network.
    We show that the problem is already NP-hard for three acyclic flows on simple
    directed graphs. Our main contribution is an efficient algorithm for sparse networks;
    specifically the algorithm is fixed parameter tractable in the number of flows
    and the treewidth of a graph that is the union of all flows. Our results also
    settle the open complexity question in the literature.
acknowledgement: Research was supported by the Austrian Science Fund (FWF), project
  I 5025-N (DELTA), 2020-2024. Esra Ceylan’s research was supported by FFG, FEMtech
  Praktika für Studentinnen. Jakub Svoboda and Krishnendu Chatterjee were supported
  by the European Research Council (ERC) CoG 863818 (ForM-SMArt).
article_processing_charge: No
author:
- first_name: Esra
  full_name: Ceylan, Esra
  id: cb1ca1d8-dcc0-11ef-baa5-9f1b3ef75933
  last_name: Ceylan
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
citation:
  ama: 'Ceylan E, Chatterjee K, Schmid S, Svoboda J. Congestion-free rerouting of
    network flows: Hardness and an FPT algorithm. In: <i>NOMS 2024-2024 IEEE Network
    Operations and Management Symposium</i>. IEEE; 2024. doi:<a href="https://doi.org/10.1109/noms59830.2024.10575579">10.1109/noms59830.2024.10575579</a>'
  apa: 'Ceylan, E., Chatterjee, K., Schmid, S., &#38; Svoboda, J. (2024). Congestion-free
    rerouting of network flows: Hardness and an FPT algorithm. In <i>NOMS 2024-2024
    IEEE Network Operations and Management Symposium</i>. Seoul, Republic of Korea:
    IEEE. <a href="https://doi.org/10.1109/noms59830.2024.10575579">https://doi.org/10.1109/noms59830.2024.10575579</a>'
  chicago: 'Ceylan, Esra, Krishnendu Chatterjee, Stefan Schmid, and Jakub Svoboda.
    “Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm.” In
    <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. IEEE,
    2024. <a href="https://doi.org/10.1109/noms59830.2024.10575579">https://doi.org/10.1109/noms59830.2024.10575579</a>.'
  ieee: 'E. Ceylan, K. Chatterjee, S. Schmid, and J. Svoboda, “Congestion-free rerouting
    of network flows: Hardness and an FPT algorithm,” in <i>NOMS 2024-2024 IEEE Network
    Operations and Management Symposium</i>, Seoul, Republic of Korea, 2024.'
  ista: 'Ceylan E, Chatterjee K, Schmid S, Svoboda J. 2024. Congestion-free rerouting
    of network flows: Hardness and an FPT algorithm. NOMS 2024-2024 IEEE Network Operations
    and Management Symposium. NOMS: Network Operations and Management Symposiu .'
  mla: 'Ceylan, Esra, et al. “Congestion-Free Rerouting of Network Flows: Hardness
    and an FPT Algorithm.” <i>NOMS 2024-2024 IEEE Network Operations and Management
    Symposium</i>, IEEE, 2024, doi:<a href="https://doi.org/10.1109/noms59830.2024.10575579">10.1109/noms59830.2024.10575579</a>.'
  short: E. Ceylan, K. Chatterjee, S. Schmid, J. Svoboda, in:, NOMS 2024-2024 IEEE
    Network Operations and Management Symposium, IEEE, 2024.
conference:
  end_date: 2024-05-10
  location: Seoul, Republic of Korea
  name: 'NOMS: Network Operations and Management Symposiu '
  start_date: 2024-05-06
corr_author: '1'
date_created: 2025-01-27T15:06:45Z
date_published: 2024-05-01T00:00:00Z
date_updated: 2025-11-05T07:34:27Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/noms59830.2024.10575579
ec_funded: 1
external_id:
  isi:
  - '001270140300143'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://schmiste.github.io/noms24.pdf
month: '05'
oa: 1
oa_version: Submitted Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: bd622a5c-d553-11ed-ba76-bae280ba8aff
  grant_number: '894907'
  name: Graphical Games
publication: NOMS 2024-2024 IEEE Network Operations and Management Symposium
publication_identifier:
  eissn:
  - 2374-9709
  isbn:
  - '9798350327946'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Congestion-free rerouting of network flows: Hardness and an FPT algorithm'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...