Convex generalized flows

Michael Holzhauser, Sven O. Krumke, Clemens Thielen

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We study an extension of the well-known generalized maximum flow problem in which the outflow of an edge is a strictly increasing convex function of its inflow. In contrast to the traditional generalized maximum flow problem, in which the outflow of an edge depends linearly on its inflow and which is solvable in polynomial time, we show that, for convex outflow functions, the problem becomes strongly NP-hard to solve even on bipartite acyclic graphs and weakly NP-hard on series-parallel graphs. Both results hold even if the outflow functions are convex quadratic. Furthermore, we present (exponential-time) exact algorithms for computing optimal flows on acyclic and series-parallel graphs and optimal preflows on general graphs. We also show that a flow decomposition similar to the one for traditional generalized flows is possible and present a pseudo-polynomial-time algorithm for the case of integral flows on series-parallel graphs.

Original languageEnglish
Pages (from-to)86-99
Number of pages14
JournalDiscrete Applied Mathematics
StatePublished - 20 Aug 2015
Externally publishedYes


  • Computational complexity
  • Flow decomposition
  • Generalized flows
  • Maximum flows
  • Network flow algorithms


Dive into the research topics of 'Convex generalized flows'. Together they form a unique fingerprint.

Cite this