×

Constrained flows in networks. (English) Zbl 07898963

Summary: The support of a flow \(x\) in a network is the subdigraph induced by the arcs uv for which \(x(u v) > 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 \(\mathcal{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 \(\mathcal{N} \). Baier et al. (2005) gave a polynomial time algorithm which finds a \(p\)-path-flow \(x\) whose value is at least \(\frac{2}{3}\) of the value of a optimum \(p\)-path-flow when \(p \in \{2, 3 \} \), and at least \(\frac{1}{2}\) when \(p \geq 4\). When \(p = 2\), they show that this is best possible unless P=NP. We show for each \(p \geq 2\) that the value of a maximum \(p\)-path-flow cannot be approximated by any ratio larger than \(\frac{9}{11} \), 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 \(\frac{1}{H ( p )}\) of the optimum solution, where \(H(p)\) is the \(p\)’th harmonic number (\(H(p) \sim \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.

MSC:

68Qxx Theory of computing

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows, 1993, Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] Baier, G.; Köhler, E.; Skutella, M., The k-splittable flow problem, Algorithmica, 42, 231-248, 2005 · Zbl 1086.90007
[3] Bang-Jensen, J.; Bessy, S., (Arc-)disjoint flows in networks, Theor. Comput. Sci., 526, 28-40, 2014 · Zbl 1290.90080
[4] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications, 2009, Springer-Verlag: Springer-Verlag London · Zbl 1170.05002
[5] Bang-Jensen, J.; Havet, F.; Yeo, A., The complexity of finding arc-disjoint branching flows, Discrete Appl. Math., 209, 16-26, 2016 · Zbl 1339.05371
[6] Bang-Jensen, J.; Yeo, A., Arc-disjoint spanning sub(di)graphs in digraphs, Theor. Comput. Sci., 438, 48-54, 2012 · Zbl 1247.68096
[7] Bang-Jensen, J.; Yeo, A., Balanced branchings in digraphs, Theor. Comput. Sci., 595, 107-119, 2015 · Zbl 1328.68082
[8] Berman, P.; Karpinski, M.; Scott, A., Approximation hardness of short symmetric instances of MAX-3SAT, Electron. Colloq. Comput. Complex., TR03, 2003
[9] Bessy, S.; Hörsch, F.; Maia, A. K.; Rautenbach, D.; Sau, I., FPT algorithms for packing k-safe spanning rooted sub(di)graphs, Discrete Appl. Math., 346, 80-94, 2024 · Zbl 1532.05133
[10] Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms, 2015, Springer · Zbl 1334.90001
[11] Disser, Yann; Matuschke, Jannik, The complexity of computing a robust flow, Oper. Res. Lett., 48, 1, 18-23, 2020 · Zbl 1525.90091
[12] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM J. Comput., 5, 4, 691-703, 1976 · Zbl 0358.90021
[13] Fortune, S.; Hopcroft, J. E.; Wyllie, J., The directed subgraph homeomorphism problem, Theor. Comput. Sci., 10, 111-121, 1980 · Zbl 0419.05028
[14] Fürer, M.; Raghavachari, B., Approximating the minimum degree spanning tree to within one from the optimal degree, (Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1992), 317-324 · Zbl 0829.68097
[15] Skutella, M., Approximating the single source unsplittable min-cost flow problem, Math. Program., 91, 3, 493-514, 2002 · Zbl 1030.90109
[16] Slivkins, A., Parameterized tractability of edge-disjoint paths on directed acyclic graphs, SIAM J. Discrete Math., 24, 1, 146-157, 2010 · Zbl 1207.68169
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.