The all-or-nothing multicommodity flow problem

TLDR

The all‑or‑nothing multicommodity flow problem in general graphs, unlike the edge‑disjoint path problem, allows non‑integral flows and has known 2‑approximation for cardinality and 4‑approximation for weighted cases on trees, with the best prior approximation being O(min(n…). The study aims to find a largest subset of commodity pairs that can each carry one unit of flow and to achieve a poly‑logarithmic approximation for this problem in general undirected graphs. The authors model the problem on a capacitated undirected graph with unit‑demand pairs and use Racke’s low‑congestion oblivious routing to design a poly‑logarithmic approximation algorithm. The problem is NP‑hard and APX‑hard even on trees.

Abstract

We consider the all-or-nothing multicommodity flow problem in general graphs. We are given a capacitated undirected graph G=(V,E,u) and set of k pairs s1t1, s2t2, …, sktk. Each pair has a unit demand. The objective is to find a largest subset S of 1,2,…,k such that for every i in S we can send a flow of one unit between si and ti. Note that this differs from the edge-disjoint path problem (EDP) in that we do not insist on integral flows for the pairs. This problem is NP-hard, and APX-hard, even on trees. For trees, a 2--approximation is known for the cardinality case and a 4--approximation for the weighted case. In this paper we build on a recent result of Racke on low congestion oblivious routing in undirected graphs to obtain a poly-logarithmic approximation for the all-or-nothing problem in general undirected graphs. The best previous known approximation for all-or-nothing flow problem was O(min(n