Convex generalized flows

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

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2015-08, Vol.190-191, p.86-99
Main Authors: Holzhauser, Michael, Krumke, Sven O., Thielen, Clemens
Format: Article
Language:English
Subjects:
Computational complexity
Flow decomposition
Generalized flows
Maximum flows
Network flow algorithms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2015.03.021