Integer and Unsplittable Multiflows in Series-Parallel Digraphs

Mohammed Majthoub Almoghrabi, Martin Skutella, Philipp Warode · 2024

Read Integer and Unsplittable Multiflows in Series-Parallel Digraphs by Mohammed Majthoub Almoghrabi, Martin Skutella, Philipp Warode (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-05182.txt.

Introduction

Mohammed Majthoub Almoghrabi, Martin Skutella, and Philipp Warode settled two long-standing flow conjectures for a structured graph class in a 2024 paper. An unsplittable multiflow sends each commodity's whole demand along one path, no splitting allowed, which real routing prefers but theory finds hard. Goemans conjectured twenty-five years ago that plain multiflows can be decomposed into unsplittable ones with little congestion; Morell and Skutella later conjectured something stronger. Nobody had confirmed either for any nontrivial graph class.

For series-parallel digraphs, the authors prove the stronger statement outright. Even when commodities have distinct sources and sinks: any multiflow is a convex blend of unsplittable ones. Deviating on each arc by less than the largest single demand. Strong integrality results reduce multiflow math work on such graphs to a plain single-commodity flow problem.

Catalog record

CREATORMohammed Majthoub Almoghrabi, Martin Skutella, Philipp Warode
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE115 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-05182

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Integer and Unsplittable Multiflows in Series-Parallel Digraphs Thanks: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy — The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). Mohammed Majthoub Almoghrabi, Martin Skutella, Philipp Warode Abstract An unsplittable multiflow routes the demand of each commodity along a single path from its source to its sink node. As our main result, we prove that in series-parallel digraphs, any given multiflow can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. This result confirms a 25-year-old conjecture by Goemans for single-source unsplittable flows, as well as a stronger recent conjecture by Morell and Skutella, for series-parallel digraphs—even for general multiflow instances where commodities have distinct source and sink nodes. Previously, no non-trivial class of digraphs was known for which either conjecture holds. En route to proving this result, we also establish strong integrality results for multiflows on series-parallel digraphs, showing that their computation can be reduced to a simple single-commodity network flow problem. 1 Introduction Network flow theory focuses on the optimal routing of commodities through networks and is fundamental to a wide array of applications in fields such as logistics, telecommunications, and computer networking; see, e.g., [ 1 , 21 ] . In many scenarios, splitting a commodity might degrade the quality of service, increase complexity, or is simply infeasible. For example, in optical networks, dividing data streams across multiple paths requires specialized equipment. Similarly, in freight logistics, splitting loads across multiple routes is often impractical. This motivates unsplittable multiflows. Here, for a given digraph with k source-sink pairs, the given demand d_{i} of every commodity i\in[k]\coloneqq\{1,\dots,k\} must be sent along a single path P_{i} from its source s_{i} to its sink t_{i} . To differentiate unsplittable flows from traditional flows, where the demand of each commodity may be divided and sent along multiple s_{i} – t_{i} paths, we refer to the latter as fractional flows. Unsplittable flow problems represent a compelling extension of disjoint path problems and have received considerable attention in the literature. Even in the apparently straightforward case of a (series-parallel) digraph consisting of one common source and one common sink connected by parallel arcs, determining the existence of a feasible unsplittable multiflow (i.e., one that adheres to given arc capacities) is NP-complete. In fact, several classical problems in combinatorial optimization, such as, e.g., Bin Packing, Partition, or parallel machine scheduling with makespan objective occur as special cases; for more details we refer to Kleinberg’s PhD thesis [ 5 ] . Integer multiflows. When every commodity i\in[k] has unit demand d_{i}\coloneqq 1 , unsplittable multiflows precisely correspond to integer multiflows, which have been extensively studied in the literature. In fact, in unit-capacity networks, feasible integer multiflows model arc-disjoint paths, and therefore cannot be computed efficiently, unless P=NP. For example, Vygen [ 20 ] shows that the arc-disjoint paths problems is NP-complete even in acyclic and planar digraphs; see [ 16 , Chapter 70.13b+c] for further related complexity results. On the other hand, single-commodity network flows (i.e., k=1 ) are well-known to feature strong integrality properties, and there are efficient combinatorial algorithms to compute integer single-commodity flows; see, e.g., [ 1 , 21 ] . In particular, the network flow polytope is integral, that is, any single-commodity flow (x_{e})_{e\in E} on a digraph G=(V,E) with integer excess at every node, is a convex combination of integer flows (y_{e})_{e\in E} that maintain the same excesses, such that \displaystyle\lfloor x_{e}\rfloor\leq y_{e}\leq\lceil x_{e}\rceil\qquad\text{for every arc~$e\in E$.} (1) Arguably, the most important tool for proving the existence of integer multiflows in special graph classes is the Nagamochi–Ibaraki Theorem [ 12 ] (see also [ 16 , Theorem 70.8] ), which relies on the sufficiency of the cut condition . This (necessary) condition requires that the capacity of every cut exceeds the total demand of commodities that must cross it; see ( 4 ) below. The concept of cut-sufficiency is of interest in its own right and is an active research topic; see, e.g., the recent work of Poremba and Shepherd [ 14 ] and references therein. For a fixed digraph, the Nagamochi–Ibaraki Theorem asserts that if, for any integer arc capacities and demands, the cut condition guarantees the existence of a feasible multiflow, it also guarantees the existence of a feasible integer multiflow. For most classes of digraphs in which the existence of a feasible multiflow implies the existence of a feasible integer multiflow, the cut condition is indeed sufficient. However, the multiflow instance in Figure 1 illustrates that the cut condition is generally not sufficient for the class of series-parallel digraphs studied in this paper. s_{1} s_{2} t_{1} t_{2} Figure 1 : An infeasible multiflow instance with two unit-demand commodities on a series-parallel digraph with unit arc capacities satisfying the cut condition Single-source unsplittable flows. Even though our results hold for general multiflow instances in series-parallel digraphs, where each commodity is routed from a distinct source to a distinct sink, our main result is primarily inspired by prior research on single-source unsplittable flows, which we review next. For a comprehensive overview of results on general unsplittable multiflows, we refer to Kolliopoulos’ survey [ 6 ] . Single-source unsplittable flows, where all commodities share a common source node s , have first been studied by Kleinberg [ 5 ] . Dinitz, Garg, and Goemans [ 3 ] prove that a given fractional flow (x_{e})_{e\in E} can always be turned into an unsplittable flow (y_{e})_{e\in E} (given by s – t_{i} paths P_{i} with y_{e}\coloneqq\sum_{i:e\in P_{i}}d_{i} ) such that \displaystyle y_{e}\leq x_{e}+d_{\max}\qquad\text{for every arc~$e\in E$,} (2) where d_{\max}\coloneqq\max_{i\in[k]}d_{i} . A famous conjecture of Goemans says that flow (x_{e})_{e\in E} can even be expressed as a convex combination of unsplittable flows (y_{e})_{e\in E} that satisfy ( 2 ). 1 1 1 Goemans’ original conjecture asserts that, for any arc costs, an unsplittable flow can be found that satisfies ( 2 ) and whose cost does not exceed that of (x_{e})_{e\in E} . This is equivalent to the stated existence of a convex combination; see, e.g., [ 10 ] . Skutella [ 17 ] , based on a flow augmentation method also used by Kolliopoulos and Stein [ 7 ] , proves that Goemans’ Conjecture is valid when the demands of the commodities are multiples of one another. For acyclic digraphs, Morell and Skutella [ 11 ] show that any fractional flow (x_{e})_{e\in E} can be turned into an unsplittable flow (y_{e})_{e\in E} that satisfies the lower bound \displaystyle y_{e}\geq x_{e}-d_{\max}\qquad\text{for every arc~$e\in E$.} (3) This result can also be achieved by augmenting flow in the reverse direction along the designated cycles of Dinitz, Garg, and Goemans [ 3 ] . Furthermore, they conjecture the existence of an unsplittable flow that satisfies both the upper bounds ( 2 ) and the lower bounds ( 3 ). Only recently, for the special case of acyclic and planar digraphs, this conjecture has been proved by Traub, Vargas Koch, and Zenklusen [ 18 ] . Morell and Skutella also propose the following strengthening to Goemans’ conjecture. Conjecture 1 (Morell and Skutella [ 11 ]

Read the complete text