Constrained Flows in Networks

Avatar
Poster
Voice is AI-generated
Connected to paperThis paper is a preprint and has not been certified by peer review

Constrained Flows in Networks

Authors

Stéphane Bessy, Jørgen Bang-Jensen, Lucas Picasarri-Arrieta

Abstract

The support of a flow $x$ in a network is the subdigraph induced by the arcs $ij$ for which $x_{ij}>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 ${\cal 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 deciding the maximum flow we can send from $s$ to $t$ along 2 paths (called a maximum 2-path-flow) in ${\cal N}$. Baier et al. (2005) gave a polynomial algorithm which finds a 2-path-flow $x$ whose value is at least $\frac{2}{3}$ of the value of a optimum 2-path-flow. This is best possible unless P=NP. They also obtained a $\frac{2}{p}$-approximation for the maximum value of a $p$-path-flow for every $p\geq 2$. In this paper we give an algorithm which gets within a factor $\frac{1}{H(p)}$ of the optimum solution, where $H(p)$ is the $p$'th harmonic number ($H(p) \sim \ln(p)$). This improves the approximation bound due to Baier et al. when $p\geq 5$. We show that in the case where the network is acyclic, we can find 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.

Follow Us on

0 comments

Add comment