# Constrained flows in networks

J. Bang-Jensen, S. Bessy, L. Picasarri-Arrieta*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

## Abstract

The support of a flow x in a network is the subdigraph induced by the arcs uv for which x(uv)>0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network N=(D,s,t,c) has a maximum flow x such that the maximum out-degree of the support Dx of x is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of computing the maximum flow we can send from s to t along p paths (called a maximum p-path-flow) in N. Baier et al. (2005) gave a polynomial time algorithm which finds a p-path-flow x whose value is at least [Formula presented] of the value of a optimum p-path-flow when p∈{2,3}, and at least [Formula presented] when p≥4. When p=2, they show that this is best possible unless P=NP. We show for each p≥2 that the value of a maximum p-path-flow cannot be approximated by any ratio larger than [Formula presented], unless P=NP. We also consider a variant of the problem where the p paths must be disjoint. For this problem, we give an algorithm which gets within a factor [Formula presented] of the optimum solution, where H(p) is the p'th harmonic number (H(p)∼ln⁡(p)). We show that in the case where the network is acyclic, we can find such a maximum p-path-flow in polynomial time for every p. We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible.

Original language English 114702 Theoretical Computer Science 1010 0304-3975 https://doi.org/10.1016/j.tcs.2024.114702 Published - 27. Sept 2024

## Keywords

• (Arc-)disjoint paths with prescribed end vertices
• Acyclic digraph
• Approximation algorithm
• Flows
• NP-complete problem
• Parameterised complexity
• Polynomial time algorithm

## Fingerprint

Dive into the research topics of 'Constrained flows in networks'. Together they form a unique fingerprint.