## 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 D_{x} 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 |
---|---|

Article number | 114702 |

Journal | Theoretical Computer Science |

Volume | 1010 |

ISSN | 0304-3975 |

DOIs | |

Publication status | Published - 27. Sept 2024 |

### Bibliographical note

Publisher Copyright:© 2024

## Keywords

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