Polynomial-time algorithms for special cases of the maximum confluent flow problem

A flow on a directed network is said to be confluent if the flow uses at most one outgoing arc at each node. Confluent flows arise naturally in destination-based routing. We study the maximum confluent flow problem (MaxConf) with a single commodity but multiple sources and sinks and heterogeneous arc capacities. It was recently shown that MaxConf  is NPNP-hard even on trees. We improve the classification of easy and hard confluent flow problems by providing polynomial-time algorithms for outerplanar graphs with a single sink, as well as trees with a constant number of either sources or sinks. Furthermore, we present an FPTAS for graphs with bounded treewidth.