On Mergings in Acyclic Directed Graphs

Abstract

Consider an acyclic directed graph $G$ with sources $s_1, s_2, ldots,s_n$ and sinks $r_1, r_2, ldots, r_n$. For $i=1, 2, ldots,n$, let $c_i$ denote the size of the minimum edge cut between $s_i$ and $r_i$, which, by Menger's theorem, implies that there exists a group of $c_i$ edge-disjoint paths from $s_i$ to $r_i$. Although they are edge disjoint within the same group, the above-mentioned edge-disjoint paths from different groups may merge with each other (or, roughly speaking, share a common subpath). In this paper we show that by choosing these paths appropriately, the number of mergings among all these edge-disjoint paths is always bounded by a finite function $mathcal{M}(c_1, c_2, ldots, c_n)$, which is independent of the size of $G$. Moreover, we prove some elementary properties of $mathcal{M}(c_1, c_2, dots, c_n)$, derive exact values of $mathcal{M}(1, c)$ and $mathcal{M}(2, c)$, and establish a scaling law of $mathcal{M}(c_1, c_2)$ when one of the parameters is fixed.