KIT | KIT-Bibliothek | Impressum | Datenschutz

The Complexity of Flow Expansion and Electrical Flow Expansion

Wagner, Dorothea; Wolf, Matthias ORCID iD icon


FlowExpansion is a network design problem, in which the input consists of a flow network and a set of candidate edges, which may be added to the network. Adding a candidate incurs given costs. The goal is to determine the cheapest set of candidate edges that, if added, allow the demands to be satisfied. FlowExpansion is a variant of the Minimum-Cost Flow problem with non-linear edge costs.
We study FlowExpansion for both graph-theoretical and electrical flow networks. In the latter case this problem is also known as the Transmission Network Expansion Planning problem. We give a structured view over the complexity of the variants of FlowExpansion that arise from restricting, e.g., the graph classes, the capacities, or the number of sources and sinks. Our goal is to determine which restrictions have a crucial impact on the computational complexity. The results in this paper range from polynomial-time algorithms for the more restricted variants over NP-hardness proofs to proofs that certain variants are NP-hard to approximate even within a logarithmic factor of the optimal solution.

Postprint §
DOI: 10.5445/IR/1000134698
Veröffentlicht am 18.01.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-030-67731-2
ISSN: 0302-9743
KITopen-ID: 1000134698
HGF-Programm 37.12.02 (POF IV, LK 01) Design,Operation & Digitalization of the Future Energy Grids
Erschienen in SOFSEM 2021: Theory and Practice of Computer Science – 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021, Proceedings. Ed.: T. Bureš
Veranstaltung 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), Online, 25.01.2021 – 29.01.2021
Verlag Springer International Publishing
Seiten 431–441
Serie Lecture Notes in Computer Science ; 12607
Vorab online veröffentlicht am 11.01.2021
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page