Summary: We study the approximability of the all-or-nothing multicommodity flow problem in directed graphs with symmetric demand pairs (SymANF). The input consists of a directed graph \(G = (V, E)\) and a collection of (unordered) pairs of nodes \({\mathcal{M}} = \{s_1t_1, s_2t_2, \dots, s_kt_k\}\). A subset \({\mathcal{M}}'\) of the pairs is routable if there is a feasible multicommodity flow in \(G\) such that, for each pair \(s_it_i \in{\mathcal{M}}'\), the amount of flow from \(s _{i }\) to \(t _{i }\) is at least one and the amount of flow from \(t _{i }\) to \(s _{i }\) is at least one. The goal is to find a maximum cardinality subset of the given pairs that can be routed. Our main result is a polylogarithmic approximation with constant congestion for SymANF. We obtain this result by extending the well-linked decomposition framework of C. Chekuri et al. [in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC’05. Baltimore, MD, USA, May 22–24, 2005. New York, NY: Association for Computing Machinery (ACM). 183–192 (2005; Zbl 1192.90017)] to the directed graph setting with symmetric demand pairs. We point out the importance of studying routing problems in this setting and the relevance of our result to future work.
For the entire collection see [Zbl 1287.90003].