# From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows

Cláudio Carvalho, Jonas Costa, Raul Lopes, Ana Karolinna Maia, Nicolas

Nisse, Cláudia Linhares Sales

► To cite this version:

Cláudio Carvalho, Jonas Costa, Raul Lopes, Ana Karolinna Maia, Nicolas Nisse, et al. From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows. Discrete Mathematics and Theoretical Computer Science, In press, vol. 25:1 (10), pp.15. 10.46298/dmtcs.9302. hal-03031759v4

HAL Id: hal-03031759

https://hal.science/hal-03031759v4

Submitted on 24 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows

Cláudio Carvalho<fnref n="1" />*

Jonas Costa<fnref n="1" />†

Raul Lopes<fnref n="2" />‡

Ana Karolinna Maia<fnref n="1" />§

Nicolas Nisse<fnref n="3" />¶

Cláudia Linhares Sales<fnref n="1" />‖

revisions 4th Apr. 2022, 9th Nov. 2022; accepted 10th Mar. 2023.

An *s*-branching flow *f* in a network *N* = (*D*, *u*), where *u* is the capacity function, is a flow that reaches every vertex in *V*(*D*) from *s* while loosing exactly one unit of flow in each vertex other than *s*. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity *n* − 1, a network *N* admits *k* arc-disjoint *s*-branching flows if and only if its associated digraph *D* contains *k* arc-disjoint *s*-branchings. Thus, a classical result by Edmonds stating that a digraph contains *k* arc-disjoint *s*-branchings if and only if the in-degree of every set *X* ⊆ *V*(*D*) \ {*s*} is at least *k* also characterizes the existence of *k* arc-disjoint *s*-branching flows in those networks, suggesting that the larger the capacities are, the closer an *s*-branching flow is from simply being an *s*-branching. This observation is further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomial algorithm to find the flows (if they exist) when every arc has capacity *n* − *c*, for every fixed *c* ≥ 1, and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper, we investigate how a property that is a natural extension of the characterization by Edmonds' relates to the existence of *k* arc-disjoint *s*-branching flows in networks. Although this property is always necessary for the existence of the flows, we show that it is not always sufficient and that it is hard to decide if the desired flows exist even if we know beforehand that the network satisfies it. On the positive side, we show that it guarantees the existence of the desired flows in some particular cases depending on the choice of the capacity function or on the structure of the underlying graph of *D*, for example. We remark that, in those positive cases, polynomial time algorithms to find the flows can be extracted from the constructive proofs.

**Keywords:** Digraphs, Branchings, Branching flows, Arc-disjoint flows

<footnote n="1">¹ Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil</footnote>

<footnote n="2">² Université Paris-Dauphine, PSL University, CNRS UMR7243, LAMSADE, Paris, France</footnote>

<footnote n="3">³ Université Côte d'Azur, Inria, CNRS, I3S, Sophia-Antipolis, France</footnote>

<footnote>*FUNCAP Pronem 4543945/2016.</footnote>

<footnote>†FUNCAP Pronem 4543945/2016, CAPES/STIC-AmSud 88881.197438/2018-01 and PhD scholarship granted by CAPES.</footnote>

<footnote>‡French Agence Nationale de la Recherche under contract ASSK ANR-18-CE40-0025-01. Work partially done at UFC(MDCC), with a PhD scholarship by FUNCAP.</footnote>

<footnote>§FUNCAP 186-155.01.00/21 and 4543945/2016 (Pronem).</footnote>

<footnote>¶French Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01.</footnote>

<footnote>‖FUNCAP Pronem 4543945/2016, and CNPq project 304831/2017-4.</footnote>
# 1 Introduction

Let $D = (V, A)$ be a digraph. If $e$ is an arc of $D$ from a vertex $v$ to a vertex $w$, we may refer to $e$ as $vw$. The *in-degree* of a set $X \subseteq V(D)$, denoted by $d_D^-(X)$, is the number of arcs with tail outside of $X$ and head inside of $X$. If $X = \{v\}$, we simply write $d_D^-(v)$ instead of $d_D^-(\{v\})$ (omitting braces). For an integer $n$, we denote by $[n]$ the set $\{1, \dots, n\}$.

A network $\mathcal{N} = (D, u)$ is formed by a digraph $D = (V, A)$ with a capacity function $u: A(D) \to \mathbb{Z}_+$. If all arcs in $D$ have capacity $\lambda$, we simply write $u \equiv \lambda$. A flow in $\mathcal{N}$ is a function $f: A(D) \to \mathbb{Z}_+$ such that $f(vw) \le u(vw), \forall vw \in A(D)$ (note that contrary to the classical definition of flows, there is no need to satisfy the conservation constraints). For a vertex $v \in V(D)$, we define $f^+(v) = \sum_{vw \in A} f(vw)$ and $f^-(v) = \sum_{wv \in A} f(vw)$, that is, $f^+(v)$ and $f^-(v)$ are the amount of flow *leaving* and *entering* $v$, respectively. The *balance vector* of a flow $f$ in a network $\mathcal{N} = (D, u)$ is the function $b_f: V(D) \to \mathbb{Z}$ associating each vertex $v \in V(D)$ to the value $f^+(v) - f^-(v)$. If $b_f(v) = \ell$, we may also say that $v$ has *balance* $\ell$. A vertex $s \in V(D)$ is a *source* of $f$ if $f^+(s) > 0$ and $f^-(s) = 0$. An $(s, t)$-cut on a network $\mathcal{N} = (D, c)$ is a bipartition $(S, \bar{S} = V(D) \setminus S)$ of $V(D)$ such that $s \in S$ and $t \in \bar{S}$. The capacity of an $(s, t)$-cut is the sum of the capacities of arcs with tail in $S$ and head in $\bar{S}$ and it is denoted by $u(S, \bar{S})$. For other concepts on graphs and digraphs, we follow standard terminology as in [3, 6].

Flows are widely studied as they allow, with a certain elegance and simplicity, modeling problems in different areas of study such as transportation, logistics and telecommunications. In the theoretical field, they are used to solve various problems in graphs and digraphs. A long list of results related to flows can be found in [1, 10]. In this work, we deal with one variation of the problem where, roughly speaking, $k$ arc-disjoint flows, having in common the same source and with a prescribed balance vector, have to be found.

Since a flow in a network can be entirely described by its associated balance vector, the goal of a flow problem can be seen as finding a flow $f$ whose balance vector respects a given set of properties. Therefore, the problem that has been considered is: given a digraph $D$ together with a balanced vector $b: V(D) \to \mathbb{Z}$, does there exist a flow $f$ in $D$ such that $b_f = b$? For example, in the decision version of the classical MAXIMUM FLOW problem we are given a network $\mathcal{N} = (D, u)$ together with a positive integer $k$ and a pair of vertices $s, t \in V(D)$, and the goal is to decide if $\mathcal{N}$ admits a flow $f$ with $b_f(s) \ge k$ such that $b_f(v) = 0$ for all $v \in V(D) \setminus \{s, t\}$ and $b_f(s) = -b_f(t)$. Such a flow $f$ is known as an $(s, t)$-flow and, in this case, we say that $f$ has *value* $b_f(s)$. This problem can be solved in polynomial time [11] (see [17, Chapter 10] for a survey on algorithms for MAXIMUM FLOW). Furthermore, by applying a simple reduction to MAXIMUM FLOW (see [3, Lemma 4.2.2]), we can solve in polynomial time any flow problem in which the aim is to find a flow $g$ with $\sum_{v \in V(D)} b_g(v) = 0$.

The possibility of considering the coexistence of flows respecting some properties in a network gives more power of modeling for this already useful tool. In [9], a more general version of the flow problem was investigated. There, the goal was to find a collection of $(s_i, t_i)$-flows that sum to a specific value $r$ and such that the sum of all the flows in each arc respects its capacity. It was shown that this version of the problem is NP-hard since it generalizes many hard problems in the literature, including the notoriously hard DIRECTED DISJOINT PATHS problem.

Two flows $f$ and $g$ in a network $\mathcal{N} = (D, u)$ are arc-disjoint if $f(vw) \cdot g(vw) = 0, \forall vw \in A(D)$. In [2], the problem of finding arc-disjoint flows was introduced and studied. The authors considered many constraints showing that some generalize important problems, known to be hard, and that there are cases where polynomial-time algorithms are possible. Amongst other results, they showed that the following are
NP-complete: the problem of deciding if there are two arc-disjoint flows in a network where all arcs have capacity one, the problem of deciding if there are two arc-disjoint flows with the same balance vectors in a network where all arcs have capacity at most 2, and the problem of deciding if there are two arc-disjoint (s, t)-flows in a network where all arcs have capacity at most two.

We say that a digraph $D$ is an $s$-branching if there is a directed path from $s$ to every other vertex in $D$ and the underlying$^{(i)}$ graph of $D$ is a tree. We also say that $D$ has root $s$. There is an extensive literature concerning the study of branchings (see for example chapter 9 of [3]), given their relevance both from practical and theoretical point of view due to its numerous applications, some of which we enumerate below. A classical result by Edmonds [8] characterizes the digraphs containing $k$ arc-disjoint $s$-branchings and later proofs of the same theorem done in [14, 19] show polynomial-time algorithms to find such branchings if they exist.

**Theorem 1** (Edmonds' branching theorem [8]). A digraph $D = (V, A)$ has $k$ arc-disjoint $s$-branchings if and only if $d_D^-(X) \ge k$ for all $X \subseteq V(D) \setminus \{s\}$ with $X \ne \emptyset$.

A stronger version of this result, allowing each branching to have its own set of roots, can be seen in [17, Chapter 53]. There are many applications for Edmonds' Theorem on arc-disjoint branchings: it can be used, for example, to prove Menger's Theorem [16], to characterize arc-connectivity [18], and to characterize branching cover [12]. The problem of finding disjoint branchings was recently studied in the setting of temporal graphs in [20]. In this paper, we consider branchings in terms of flow.

An $s$-branching flow in a network $\mathcal{N} = (D, u)$ is a flow $f$ such that $b_f(s) = n-1$ and $b_f(v) = -1$ for every $v \in V(D) \setminus \{s\}$. In other words, $f$ reaches all vertices of $D$ and each vertex other than $s$ retains one unit of flow. Here, we study the problem that, given a digraph $D$ and a source $s$ and an integer $k$, aims at deciding whether there exist $k$ arc-disjoint $s$-branching flows.

**Related work:** Finding one $s$-branching flow in a given network is easy: since $\sum_{v \in V(D)} b_f(v) = 0$, we can reduce this problem to the problem of finding one $(s, t)$-flow, as discussed above. We can also find $k$ arc-disjoint $s$-branching flows in polynomial time when $u \equiv n-1$. In [2] it was shown that, in this case, $\mathcal{N}$ admits an $s$-branching flow if and only if $D$ contains an $s$-branching. Thus, applying Theorem 1, the authors provided a characterization of networks admitting $k$ arc-disjoint $s$-branching flows, which are exactly the networks constructed on digraphs containing $k$ arc-disjoint $s$-branchings. They also provided a polynomial time algorithm that finds such flows if they exist. We now discuss how the tractability of this problem, in general, depends on the choice of the capacity function.

In [2], the authors showed that the problem of deciding if a network has $k$ arc-disjoint $s$-branching flows is NP-complete if every arc has capacity at most two, and in [4] this result was extended to networks with capacity at most $\ell$, for every fixed $\ell \ge 2$. For most choices of larger capacities, the problem remains hard. In [4] it was shown that, unless the *Exponential Time Hypothesis* [13] fails, there is no polynomial time algorithm for the problem of finding $k$ arc-disjoint $s$-branching flows in a network $\mathcal{N} = (D, u)$ with $u \equiv \lambda$ for any choice of $\lambda$ such that $n/2 \le \lambda \le n - (\log n)^{1+\epsilon}$, $\epsilon > 0$, even if $D$ is acyclic. In [7] the authors adapted this last proof to show that the same holds if $(\log n)^{1+\epsilon} \le \lambda \le n/2$. The last two results have an intersection point, which is when $u \equiv n/2$. The two constructions result in the same network in this case, and it is worth noticing that it gives a polynomial time reduction. So, for $u \equiv n/2$, the problem is NP-hard. On the positive side, in [4] it was also shown that the problem is solvable in polynomial time when $\lambda = n-c$, for fixed $k$ and $c \ge 1$. More precisely, the authors showed that the problem is XP for

<footnote>(i) The underlying graph of a digraph $D$ is the undirected graph obtained by ignoring the orientation of the arcs of $D$.</footnote>
fixed $k$ and $c$ when the goal is to find $k$ arc-disjoint $s$-branching flows. This was later improved to an FPT algorithm with the same parameter in [5].

In short, the results presented in the previous paragraph roughly say that the problem of deciding if a given network with $u \equiv n - c$ contains $k$ arc-disjoint $s$-branching flows admits a polynomial time algorithm for every fixed $c \ge 1$, and is unlikely to admit such an algorithm for most other choices of $u$ under reasonable complexity hypothesis. Thus, any general characterization of networks admitting such flows must also be hard to verify. In the following, we extend to $s$-branching flows the property characterizing networks containing $k$ arc-disjoint $s$-branchings, which was originally proposed in [7].

For a vertex $s \in V(D)$ and two non-negative integers $k, \lambda$, we say that $D$ is $(k, \lambda, s)$-sufficient if, for every $X \subseteq V(D) \setminus \{s\}$ with $X \ne \emptyset$, we have

$$d_D^-(X) \ge k \left\lfloor \frac{|X|}{\lambda} \right\rfloor. \qquad (1)$$

If $\mathcal{N} = (D, u)$ with $u \equiv \lambda$ is a network constructed on such a digraph, we may also say that $\mathcal{N}$ is $(k, \lambda, s)$-sufficient.

It is not hard to visualize the relationship between this property and the one in the statement of Theorem 1: if $\lambda = n - 1$, then every arc of $D$ has enough capacity to send as many units of flow as needed to reach any set $X \subseteq V(D)$. Thus, capacities are not an issue and Inequality 1 states that $d_D^-(X) \ge k$, as in Theorem 1, since $|X| \le n - 1$. For other choices of $\lambda$, note that every $s$-branching flow on $\mathcal{N}$ must reach a set of vertices $X$ with at least $|X|$ units of flow to cover it. Thus each $s$-branching flow in $\mathcal{N}$ uses at least $\lceil |X|/\lambda \rceil$ arcs to cover $X$. More formally, the following was proved.

**Proposition 1.** [7] Let $\mathcal{N} = (D, u)$ be a network with $u \equiv \lambda$ and $s \in V(D)$. If $\mathcal{N}$ admits $k$ arc-disjoint $s$-branching flows, then $D$ is $(k, \lambda, s)$-sufficient.

**Our contributions:** In Section 2, we show how to construct a family of a $(k, \lambda, s)$-sufficient networks not containing $k$ arc-disjoint $s$-branching flows. On the positive side, we show that some positive cases of sufficiency do occur depending on the structure of $D$ and on the choice of $k$ and $\lambda$.

In Section 3, we show that $(k, \lambda, s)$-sufficiency guarantees the existence of $k$ arc-disjoint $s$-branching flows in a network $\mathcal{N} = (D, u)$ when $D$ is an $s$-branching where parallel arcs are allowed, and when $D$ is a collection of internally disjoint multi-paths starting at $s$ and all ending on the same vertex $t \in V(D)$. In other words, the flows are guaranteed to exist when the underlying simple graph of $D$ is a tree or a spindle, and thus the considered property characterizes the existence of the flows in those classes of networks. Additionally, we show that we also have this guarantee in general digraphs when $k = 1$, when $\lambda = 1$, and when $\lambda = |V(D)| - 2$. Finally, we show that, for a network $\mathcal{N} = (D, u)$ with $u \equiv \lambda$ and an integer $p$ satisfying $p\lambda \ge n - 1$, if $d_D^-(X) \ge pk$ for all non-empty $X \subseteq V(D) \setminus \{s\}$, then $\mathcal{N}$ admits $k$ arc-disjoint $s$-branching flows.

In Section 4, we show that the analyzed property is not enough to improve the tractability of the problem of finding the desired flows. Namely, we show that it is NP-complete to decide if a network $\mathcal{N}$ admits $k$ arc-disjoint $s$-branching flows even if its underlying simple graph is constructed by appending a path to the end of a spindle and we know beforehand that $\mathcal{N}$ is $(k, \lambda, s)$-sufficient. Since this property can be easily verified in this class and it is always necessary for the existence of the flows, it is no surprise that it is not enough to guarantee the existence of the $k$ arc-disjoint $s$-branching flows.
In Section 5 we close the paper with some open questions. We remark that polynomial time algorithms
to find the flows can be extracted from the provided constructive proofs of the aforementioned results.

**2 Networks on (k, λ, s)-sufficient digraphs not containing the flows**

In Figure 1 we give an example of a (2, *n* − 3, *s*)-sufficient network that does not contain 2 arc-disjoint
*s*-branching flows, and we show that it can be generalised to (2, *n* − *c*, *s*)-sufficient networks, for every
fixed *c* ≥ 3 (Theorem 2). Thus the best that we can expect is that every (2, *n* − 2, *s*)-sufficient network
contains the desired *s*-branching flows. In Section 3 we show that this is indeed true for general networks
(c.f. Theorem 9).

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** Example of a network on a (2, *n* − 3, *s*)-sufficient digraph that does not contain 2 arc-disjoint *s*-branching flows. Here every arc has capacity *n* − 3.</figcaption></figure>

**Theorem 2.** For every $c \ge 3$, there exists a $(2, n-c, s)$-sufficient network $\mathcal{N}$ which does not admit 2 arc-disjoint $s$-branching flows.

**Proof:** Let $\mathcal{N}$ be a network as in Figure 1, considering that $B$ has exactly $c$ vertices and $|A| = n-c-1$, with each of the last $c$ vertices of $A$ connected to a different vertex of $B$. First, we show that $\mathcal{N}$ is $(2, n-c, s)$-sufficient. For any set $X \subseteq V(D) \setminus \{s\}$, let $a = |X \cap A|$ and $b = |X \cap B|$. Thus, $|X| = a + b$.

If $|X| \le n-c$, then we must show that $d^{-}(X) \ge 2 \left\lfloor \frac{|X|}{n-c} \right\rfloor = 2$. If $a > 0$, one can see that there are two arcs entering $X \cap A$, then $d^{-}(X) \ge 2+b \ge 2$. Otherwise, we have that $b > 0$ and $d^{-}(X) = 2b \ge 2$.

If $|X| > n-c$, then we must show that $d^{-}(X) \ge 2 \left\lfloor \frac{|X|}{n-c} \right\rfloor = 4$. Note that in this case $a > 0$ and $b \ge 2$. So, we have $d^{-}(X) \ge 2+b \ge 4$.

Now we show that $\mathcal{N}$ does not admit 2 arc-disjoint $s$-branching flows. Observe that each flow can use
at most one arc from $A$ to $B$, by the size of $A$ and the capacity of the arcs (specially the arcs leaving $s$ to
$A$). So, there is a vertex $v$ in $B$ that must be reached by each flow through an arc coming from $s$, but there
is only one arc from $s$ to $v$. $\square$

Next, we show how to construct a family of $(k, \lambda, s)$-sufficient networks that do not contain $k$ arc-disjoint $s$-branching flows.

**Theorem 3.** For all $\lambda \ge 2$ and for all even $k \ge 2$, there exists a $(k, \lambda, s)$-sufficient network $\mathcal{N} = (D, u)$, with $u \equiv \lambda$, that does not admit $k$ arc-disjoint $s$-branching flows.
**Proof:** Given an even $k \ge 2$ and $\lambda \ge 2$, start the construction of $\mathcal{N}$ by adding the vertices $s, a, b, c$ and $d$ then add an arc from $s$ to every other vertex along with the arcs $ab, ac, bd$, and $cd$. Subdivide the arc $bd$ ($cd$) $\lambda-2$ times and let $B(C)$ be the union of $\{b\}$ ($\{c\}$) and the set of vertices obtained by the subdivisions of $bd$ ($cd$) (note that if $\lambda = 2$ nothing changes at this step, which means that $B = \{b\}$ and $C = \{c\}$), and then double the arcs between vertices of $B(C)$. Let $P$ be a path with $\lambda$ vertices and denote by $e$ and $f$, respectively, the first and last vertex of $P$. Triple the first $\lambda-2$ arcs of $P$ and double the last one (the one that enters $f$). After that, add $P$ to $D$ along with the arcs $de, fa$ and two parallel arcs $se$. To complete the construction, replace each arc by $k/2$ copies of itself and set $u \equiv \lambda$. See Figure 2.

<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Counter-example for $k = 2$ and $\lambda \ge 2$</figcaption></figure>

Here, we say that a set $X \subseteq V(D)$ is satisfied if $d_D^-(X) \ge k[|X|/\lambda]$.

To prove that $D$ is $(k, \lambda, s)$-sufficient, we consider the case where $k=2$ because for a larger $k$ we multiply the in-degree of each subset of $V(D)-s$ by $k/2$. Observe that, except for $s$, every vertex has in-degree at least 2 in $D$ and that for every $X \subseteq V(D)-s$ each vertex from $\{a, b, c, d\}$ which belongs to $X$ sums at least one unit to its in-degree and the vertex $e$ sums to two. Consider a set $X \subseteq V(D)-s$. If $D[X]$ has a cycle, then $d_D^-(X) \ge 5$, once $X$ necessarily contains $a, d, P$ and either $B$ or $C$ (or both), but its also true that $|X| \ge 2\lambda + 1$, which means that should be at least one extra arc entering in $X$ for it to be satisfied. To verify the existence of this extra arc assume without loss of generality that $B \subset X$ (the case where $C \subset X$ is symmetric) and take the longest $(z, d)$-path in $D[X]$ such that $z \in C$. If no such path exists, there is at least one arc going from $C$ to $d$ which was not counted before and if the path exists, then either $z=c$ or the two arcs $yz$ enters $X$, where $y$ is the in-neighbor of $z$ which, by the choice of $z$, cannot be in $X$.

Now consider that $D[X]$ is acyclic. Note that each source in $D[X]$ contributes with at least two units in the in-degree of $X$. Since each weak component of $D[X]$ has at least one source, then every $X$ with $|X| \le \lambda$ is satisfied. Similarly, the same also holds when $\lambda < |X| \le 2\lambda$ if $D[X]$ has more than one weak component or only one component with many sources. Otherwise $D[X]$ has only one weak component $W$ with a single source $w$, and we have 5 cases:

* $w \in B$. Observe that in this case $\{d, e\} \subset X$, once that $|X| \ge \lambda+1$ and $|B| = \lambda-1$, which means that $d_D^-(X) \ge 5$.

* $w \in C$. It's analogous to the previous one.
* $w = a$. In this case, there are at least two vertices from $\{b, c, d\}$ in $X$. That is, $d^-(X) \ge 4$.

* $w = d$. If $d$ is the source, then $e \in X$, and thus $d_D^-(X) \ge 5$.

* $w \in V(P)$. Except for $f$, every vertex of $P$ has in-degree three and since $X$ must contain $a$, then $d_D^-(X) \ge 4$. When $w = f$, besides $a$, $X$ must also contain at least one vertex from $\{b, c\}$ which guarantees $d_D^-(X) \ge 4$.

When $2\lambda + 1 \le |X| \le 3\lambda$, the in-degree of $X$ must be at least 6. We start with the case that $D[X]$ has just one weak component. If $w$ is a source in $D[X]$, again we have 5 subcases:

* $w \in B$. In this case, since $|B \cup \{d\}| = \lambda$, either there is a vertex in $C$ which is also a source in $D[X]$ or $a \in X$. In both situations, $d, e \in X$ because $|B \cup C| < 2\lambda$. Thus, $d_D^-(X) \ge 6$.

* $w \in C$. It's analogous to the previous one.

* $w = a$. Once $|\{a, d\} \cup B \cup C| = 2\lambda$, if $a$ is a source, there is a path in $D[X]$ that starts in $a$, goes through $B$ or $C$, $d$ and ends in some vertex of $P$.

* $w = d$. When $d$ is a source, for sure $\{a, b, c, d, e\} \subset X$.

* $w \in V(P)$. Here, in order to avoid cycles, we know that if $w = f$, necessarily $a, b, c$ and $d$ are also included in $X$ and if $w \ne f$, at least $a, b$ and $c$ are included in $X$ but, in this case, $w$ already contributes with 3 for the in-degree of $X$. Thus $d_D^-(X) \ge 6$.

If $D[X]$ has more than 2 weak components, we already know that $d_D^-(X) \ge 6$. If $D[X]$ has two weak components $Y, Z$, one of them, say $Y$, has at least $\lambda + 1$ vertices and hence, as in the previous cases, $d_D^-(Y) \ge 4$. Thus, $d^-(X) \ge 6$.

Notice that if there are $k$ arc-disjoint $s$-branching flows $x_1, x_2, \dots, x_k$ in $\mathcal{N}$, as $d_D^-(B) = d_D^-(C) = k$, each one of these $k$ arcs has to be used by a different flow, and carry at least $\lambda - 1$ units of flow, that is, one unit for each vertex of $B$ and $C$. Now observe that $k/2$ of the arcs which enter in $B$ come from $a$ and the same for the ones that enter $C$, and then $a$ must receive $\lambda$ units of flow on each of its $k$ incoming arcs in order to send the proper amount of flow to $B$ and $C$. Assume without loss of generality that the $k/2$ copies of $sa$ are going to be used by $x_1, x_2, \dots, x_{k/2}$ and the $k/2$ copies of $fa$ are left for $x_{k/2+1}, x_{k/2+2}, \dots, x_k$. Since the in-degree of $f$ is also equal to $k$, $f$ can receive at most $\lambda$ units of flow of each $x_1, x_2, \dots, x_k$ and hence it can send at most $\lambda - 1$ units of any of these flows to $a$. Therefore, $\mathcal{N}$ does not admit $k$ arc-disjoint $s$-branching flows. $\square$

### 3 Networks on $(k, \lambda, s)$-sufficient digraphs containing the flows

In this section, we show some positive results regarding $(k, \lambda, s)$-sufficiency. We remark that the constructive proofs of those results can be naturally adapted to polynomial-time algorithms to find the desired flows in those networks.

We say that a digraph $D = (V, A)$ is a *multi-branching* if $D$ is an out-branching when we ignore its parallel arcs and, for $\ell \ge 1$, we denote by $D_\ell$ the class of *multi-spindles*. That is, the class of digraphs formed by a source vertex $s$, a sink vertex $t$, $\ell$ pairwise internally vertex-disjoint multi-paths $P_1, \dots, P_\ell$ from $s$ to $t$, each with $p_i \ge 1$ internal vertices, $1 \le i \le \ell$, respectively. See Figures 3(a) and 3(b) for an example of a multi-branching and an example of a multi-spindle, respectively.
<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Examples of multi-branching (a) and multi-spindle (b)</figcaption></figure>

**Theorem 4.** Let $D$ be a $(k, \lambda, s)$-sufficient multi-branching. Then the network $\mathcal{N} = (D, u)$, with $u \equiv \lambda$, admits $k$ arc-disjoint $s$-branching flows.

The following result is useful for proving Theorem 4.

**Lemma 1.** Let $D$ be a $(k, \lambda, s)$-sufficient digraph and let $W$ be a nonempty subset of $V(D) \setminus \{s\}$ such that $N_D^+(V(D) \setminus W) = \{w\}$, $w \in W$. Then $D[W]$ is $(k, \lambda, w)$-sufficient.

**Proof:** Since $w$ is the unique vertex of $W$ which has in-neighbours in $V(D) \setminus W$, then we have $d_{\bar{D}[W]}(v) = d_{\bar{D}}(v)$ for every $v \in W \setminus \{w\}$. Thus, for every $X \subseteq W \setminus \{w\}$ we have $d_{\bar{D}[W]}(X) = d_{\bar{D}}(X)$. $\square$

**Proof of Theorem 4:** We are going to use induction on the height $h$ of the multi-branching $D$ with root $s$ to construct $k$ arc-disjoint $s$-branching flows $f_1, f_2, \dots, f_k$ in $\mathcal{N}$.

The base case is $h = 1$. In this case $D$ is a star and, since it is $(k, \lambda, s)$-sufficient, there are at least $k$ arcs from $s$ to every other vertex and we can use one arc for each flow $f_j$, for $j \in [k]$.

Induction step: Suppose that the statement holds for multi-branchings of height $h < q$. Assume that $D$ has height $q$ and let $r_1, r_2, \dots, r_p$ be the out-neighbours of $s$ in $D$.

Let $B_{r_i}$ be the subgraph of $B_s$ that is a multi-branching with root $r_i$, for each $i \in [p]$. Observe that, by Lemma 1, $B_{r_i}$ is $(k, \lambda, r_i)$-sufficient and has height $h_i \le q-1$, thus, by induction hypothesis, $B_{r_i}$ has $k$ arc-disjoint $r_i$-branching flows $f_1^i, f_2^i, \dots, f_k^i$. We know that $d^-(r_i) \ge k \lfloor \frac{|B_{r_i}|}{\lambda} \rfloor$ and then we can use $\lfloor \frac{|B_{r_i}|}{\lambda} \rfloor$ of these arcs to send the proper amount of flow from $s$ to $r_i$ on each $x_j$ to complete the $k$ $s$-branching flows. $\square$

Since a multi-path is also a multi-branching, Theorem 4 generalizes the result of [7] for multi-paths.

**Theorem 5.** If $D$ is a $(k, \lambda, s)$-sufficient digraph in $D_\ell$, then the network $\mathcal{N} = (D, u)$ with $u \equiv \lambda$ admits $k$ arc-disjoint $s$-branching flows.

**Proof:** Let $D$ be a digraph in $D_\ell$ that is $(k, \lambda, s)$-sufficient. By definition, $D$ is composed by the multi-paths $P_1, P_2, \dots, P_\ell$ and $V(P_i) \cap V(P_j) = \{s, t\}$ for every $1 \le i < j \le \ell$. We denote the $p_i$ internal vertices of $P_i$ by $v_{p_i}^i, v_{p_{i-1}}^i, \dots, v_2^i, v_1^i$ in this order, for every $i \in [\ell]$. For every $j \in [p_i]$, we define $r_j^i \ge 0$ so that $d_{\bar{D}}(v_j^i) = k\lfloor j/\lambda \rfloor + r_j^i$. Remark that $d_{\bar{D}}(v_j^i) \ge k\lceil j/\lambda \rceil$, otherwise the set
$\{v_j^i, v_{j-1}^i, \dots, v_1^i\}$ would contradict the fact that $D$ is $(k, \lambda, s)$-sufficient, since the only arcs entering in it are those arriving at $v_j^i$. Considering only the vertices with an index multiple of $\lambda$, that is, the vertices $v_{j\lambda}$ for every $1 \le j \le \lfloor p_i/\lambda \rfloor$, let

$$r(P_i) = \begin{cases} k, & \text{if } p_i < \lambda, \\ \min\{r_{j\lambda}^i | 1 \le j \le \lfloor p_i/\lambda \rfloor\}, & \text{otherwise.} \end{cases}$$

For all $i \in [\ell]$, we define $e_i$ as the number of arcs from $v_1^i$ to $t$ and $m_i = \min\{r(P_i), e_i\}$. Let $k' = \sum_{i=1}^{\ell} m_i$.

Assume without loss of generality that $P_1, P_2, \dots, P_q$ are the paths on which $r(P_i) \le e_i$, for $i \in [\ell]$. Then $k' = \sum_{i=1}^q r(P_i) + \sum_{i=q+1}^\ell e_i$. Now, for every $i \in [q]$, we choose a $j_i \in [\lfloor p_i/\lambda \rfloor]$ which satisfies $d_D^-(v_{j_i\lambda}^i) = kj_i + r(P_i)$ and we define $X_i = \{v_{j_i\lambda}^i, v_{(j_i\lambda)-1}^i, \dots, v_1^i\}$. Consider the set $X = \bigcup_{i=1}^q X_i \cup \{t\}$. We have that

$$d_D^-(X) = \sum_{i=1}^q d_D^-(X_i) + \sum_{i=q+1}^{\ell} e_i = k \sum_{i=1}^q j_i + \sum_{i=1}^q r(P_i) + \sum_{i=q+1}^{\ell} e_i = k \sum_{i=1}^q j_i + k'. \quad (2)$$

Since $D$ is $(k, \lambda, s)$-sufficient and $|X_i| = j_i\lambda$

$$d_D^-(X) \ge k \left\lfloor \frac{|X|}{\lambda} \right\rfloor = k \left\lfloor \frac{1}{\lambda} + \frac{\lambda \sum_{i=1}^q j_i}{\lambda} \right\rfloor = k \sum_{i=1}^q j_i + k. \quad (3)$$

Combining (2) and (3) we conclude that $k' \ge k$. To finally construct the $k$ arc disjoint branching flows, we need the following claim.

**Claim 1.** There are $k$ arc-disjoint flows $x_1^i, \dots, x_k^i$ on the network $N_i = (P_i, u)$, with $u \equiv \lambda$, such that $x_1^i, \dots, x_{m_i}^i$ are branching flows in $N_i$ and $x_{m_i+1}, \dots, x_k^i$ are branching flows in $N_i - t$.

*Proof.* We show how to construct the flows $x_1^i, x_2^i, \dots, x_k^i$. For every $j \in [p_i]$, the vertex $v_j^i$ must receive $j+1$ units of flow on the first $m_i$ flows and $j$ units on remaining $k-m_i$ flows. Since $d_D^-(v_j^i) = d_{P_i}^-(v_j^i) \ge k\lfloor j/\lambda \rfloor$, we can use a distinct group of $\lfloor j/\lambda \rfloor$ arcs to send $j$ units of flow on each one of the $k$ flows and we only have to argue how to send the extra unit for the flows $x_1^i, \dots, x_{m_i}^i$. If $j$ is a multiple of $\lambda$, then there are at least another $r(P_i)$ extra arcs entering $v_j^i$ and since $m_i \le r(P_i)$ they can be used to send the extra units (note that, if $r(P_i) = 0$ then $m_i = 0$ and no extra unit is needed). Otherwise, $j$ is not multiple of $\lambda$ and when we send $j$ units of flow through $\lfloor j/\lambda \rfloor$ arcs, there is an arc that will not be used in the maximum capacity and so we can use it to send the extra unit. Applying this method iteratively from $v_{p_i}^i$ to $v_1^i$, we arrive at $v_1^i$ with 2 units of flow on the flows $x_1^i, \dots, x_{m_i}^i$ and we can send the extra unit of each flow to $t$ because $m_i \le e_i$. $\diamond$

For each $i \in [\ell]$, we compute the flows $x_1^i, x_2^i, \dots, x_k^i$ as in the Claim 1. Observe that $k'$ is the number of flows that reach $t$. If $k' = k$, then we can rename these $k$ flows in such a way that each $x_j = \bigcup_{i=1}^\ell x_j^i$ is an $s$-branching flow on $N$. Finally, if $k' > k$, we take a flow that reaches $t$ and we modify it so that it doesn't reach $t$ anymore, and we repeat this process until there are only $k$ flows that reach $t$. $\square$

It is worth to notice that the above proofs for multi-branchings and multi-spindles together with Proposition 1, besides giving a complete characterization of the digraphs in these classes having $k$ arc-disjoint
branching flows, they lead to polynomial-time algorithms to find such flows, once testing the $(k, \lambda, s)$- sufficiency for multi-branchings and multi-spindles can be done in polynomial time. The algorithms work for every value of $\lambda$, even those for which the problem of finding $k$ arc-disjoint branching flows is known to be hard in general.

We now consider the cases of $k$ or $\lambda$ with value 1 and for that we need the three following results.

**Theorem 6 (Max-flow min-cut).** In any network $\mathcal{N} = (D, u)$ with source $s$ and sink $t$, the value of a maximum flow is equal to the capacity of a minimum cut.

**Theorem 7.** [2] Let $k$ be an integer and $\mathcal{N} = (D, u)$ be a network with $u \equiv 1$ and a prescribed balance vector $b$ such that $b \not\equiv 0$. There exist $k$ arc-disjoint flows in $\mathcal{N}$, all with balance vector $b$, if and only if $\mathcal{N}$ has a flow $f$ with balance vector $b_f \equiv kb$. Hence, one can decide the existence of these flows in polynomial time.

**Lemma 2 (Adapted from [3]).** Given a network $\mathcal{N} = (D, u)$ and a prescribed balance vector $b$. Let $M = \sum_{v:b(v)>0} b(v)$ and let $\mathcal{N}' = (D', u')$ be a network defined as follows:

$$ \bullet V(D') = V(D) \cup \{s', t'\}; $$

$$ \bullet A(D') = A(D) \cup \{s'u : u \in V(D), b(u) > 0\} \cup \{vt' : v \in V(D), b(v) < 0\}; $$

$$ \bullet u'(a) = u(a), \forall a \in A(D), u'(s'u) = b(u) \text{ if } b(u) > 0 \text{ and } u'(vt') = -b(v) \text{ if } b(v) < 0. $$

Then, $\mathcal{N}$ admits a flow $f$ with balance $b$ if and only if $\mathcal{N}'$ admits a $(s', t')$-flow $f'$ with value $M$.

**Theorem 8.** Let $D$ be a $(k, \lambda, s)$-sufficient digraph. Then, if $\lambda = 1$ or $k = 1$, the network $\mathcal{N} = (D, u)$ with $u \equiv \lambda$ admits $k$ arc-disjoint $s$-branching flows.

**Proof:** We start by showing a result that is common to both cases. Let $b_f$ be the following balance vector: $b_f(s) = k(n-1)$ and $b_f(v) = -k$, for all $v \in V(D) - s$, where $n = |V(D)|$. Let $\mathcal{N}'$ be the network obtained from $\mathcal{N}$ and $b_f$, as described in Lemma 2, and $(S, \bar{S})$ be a minimum $(s', t')$-cut in $\mathcal{N}'$. We show that $u(S, \bar{S}) = k(n-1)$ which, by the Theorem 6, implies that there is a $(s', t')$-flow with value $k(n-1)$ in $\mathcal{N}'$. Remark that, by construction of $\mathcal{N}'$, $u'(s's) = k(n-1)$, $u'(vt') = k$ for every $v \in D \setminus s$ and $u'(a) = \lambda$ for every $a \in A(D)$. It is easy to see that $u(S, \bar{S}) \le k(n-1)$ because $u(s', V(D') - s') = k(n-1)$. Then, we might assume that $s \in S$ and we define $X = \bar{S} \setminus \{t'\}$. It follows that

$$ u(S, \bar{S}) = u(S, X) + u(S, \{t'\}) = \lambda d_{\bar{D}}(X) + k(n - |X| - 1). \quad (4) $$

Case $\lambda = 1$. Since $D$ is $(k, 1, s)$-sufficient, $d_{\bar{D}}(X) \ge k|X|$ and resuming (4), we have $u(S, \bar{S}) \ge k|X| + k(n - |X| - 1) = k(n-1)$. Thus, $u(S, \bar{S}) = k(n-1)$ and, by the Lemma 2, $\mathcal{N}$ admits a flow with balance $b_f$. The result follows from Theorem 7 which states that $\mathcal{N}$ admits $k$ arc-disjoint $s$-branching flows if and only if it admits a single flow $f$ with balance $b_f$.

Case $k = 1$. Here, $D$ is $(1, \lambda, s)$-sufficient, which means that $d_{\bar{D}}(X) \ge (|X|/\lambda)$, and so $\lambda d_{\bar{D}}(X) \ge |X|$. Replacing this in (4), we obtain $u(S, \bar{S}) \ge |X| + n - |X| - 1 = n - 1$. Thus, $u(S, \bar{S}) = k(n-1)$. Similarly to the previous case, we conclude, by the Lemma 2, that $\mathcal{N}$ admits a flow $f$ with balance $b_f$. As $k = 1$, we have that $f$ is a branching flow and the result follows. $\square$

We also show that networks on $(2, n-2, s)$-sufficient digraphs contain 2 arc-disjoint $s$-branching flows. This is a slightly improvement on the result by [2] when $k = 2$, which states that Edmonds'
characterization of digraphs containing 2 arc-disjoint s-branchings also characterizes the existence of 2 arc-disjoint s-branching flows.

**Theorem 9.** Let $\mathcal{N} = (D, u)$ be a $(2, n - 2, s)$-sufficient network with $u \equiv n - 2$. Then $\mathcal{N}$ admits 2 arc-disjoint s-branching flows.

**Proof:** Since $\mathcal{N} = (D, u)$ is a $(2, n - 2, s)$-sufficient network, then for every $X \subset V(D) \setminus \{s\}$ we have $d_D^-(X) \ge 2$, and for $X = V(D) \setminus \{s\}$ we have $d_D^-(X) \ge 4$. By Edmonds' Theorem, $D$ has two arc-disjoint s-branchings. Let us call these s-branchings $B^b$ and $B^g$ and let us colour blue the arcs used by $B^b$, green the arcs used by $B^g$, and black the arcs of $D$ not used by any of those branchings (observe that every vertex in $V(D) \setminus \{s\}$ is the head of exactly one blue and exactly one green arc). The idea is to construct the desired s-branching flows using the arcs of $B^b$ and $B^g$. This will be possible unless we are forced to send $n - 1$ units of flow through an arc, which can only happen from an arc that leaves $s$. In this particular case, we show how to modify the branchings to avoid the problem.

Let $r_1^b, \dots, r_\ell^b$ be the out-neighbours of $s$ in $B^b$ and let $B_1^b, \dots, B_\ell^b$ be the maximal sub-branchings of $B^b \setminus \{s\}$ with roots $r_1^b, \dots, r_\ell^b$, respectively. If $\ell > 1$, then we can construct a branching flow $f_b$ from $B^b$ by sending $|B_i^b|$ units of flow through $sr_i^b$, for $1 \le i \le \ell$, which is possible because $u \equiv n - 2$. The same applies to $B^g$ and we will exchange $b$ to $g$ in the above notation when it concerns $B^g$ in the rest of the proof.

If $s$ has only one out-neighbour $r^b$ in $B^b$, but there is a black arc $sv$, we can construct $f_b$ from $B^b \cup sv$. We have to consider two cases: if $v \ne r^b$, let $uv \in A(B^b)$ and let $B_v^b$ be the maximal connected subgraph of $B^b \setminus \{u\}$ with root $v$. Then we send $|B_v^b|$ units of flow through $sv$ and $|B^b \setminus \{s\}| - |B_v^b|$ through $sr^b$. Otherwise, $v = r^b$ and we have two copies of the arc $sv$. So we can send 1 unit of flow through one and $n - 2$ through the other. In both cases, for the remaining blue arcs, we just need to adjust the proper amount of flow. The same applies to $B^g$.

Thus we can assume w.l.o.g. that every out-neighbour of $s$ in $D$ is either blue or green and, from such arcs, exactly one is blue ($sr^b$) and the remaining are green. Notice that, since $d_D^-(V(D) \setminus \{s\}) \ge 4$, there must be at least three green arcs from $s$ to $D \setminus \{s\}$.

Since $B^g$ is a s-branching, $r^b$ appears in only one $B_i^g$, and let us consider a $r_j^g$ for which $B_j^g \ne B_i^g$. Except for $sr_j^g$, there are no green arcs entering or leaving $B_j^g$. Then, let $E$ be the set of blue arcs entering $V(B_j^g)$ together with all blue arcs between vertices in $V(B_j^g)$. We now recolour blue the arcs in $A(B_j^g) \cup sr_j^g$ and yellow the arcs in $E$. After this recolouring, a vertex $w \ne s$ is the head of exactly one blue arc and one yellow arc if it is in $V(B_j^g)$, otherwise it is still the head of exactly one blue and one green arc. This means that the vertices of $V(D)$ along with the blue arcs will form a s-branching $B^{b'}$. In particular, there are two blue arcs leaving $s$ in $B^{b'}$ and we can construct the branching flow $f_{b'}$ as before.

We now recolour the arcs of $E$ green. Again, we have the guarantee that every vertex in $B_j^g$ has exactly one green arc arriving at it (the former yellow arcs), and, since the green arcs outside $A(B_j^g) \cup sr_j^g$ remain unaltered, the new set of all green arcs also form a s-branching $B^{g'}$. Once more, we have at least two arcs leaving $s$ in $B^{g'}$, and we can construct $f_{g'}$ as before. $\square$

We remark that, by a result of [4], deciding if a network with $u \equiv n - 2$ admits arc-disjoint flows can be done in polynomial time. Since Theorem 9 completes the proof that a network is $(2, n - 2, s)$-sufficient if and only if it admits 2 arc-disjoint s-branching flows (together with Proposition 1), we get that it can be decided in polynomial time whether a digraph is $(2, n - 2, s)$-sufficient.
We end this section showing that, for particular choices of $d_D^-(X)$ and $\lambda$, a simple stronger condition than the one presented in the statement of Proposition 1 guarantees the existence of $k$ arc-disjoint $s$-branching flows in a given network.

**Theorem 10.** Let $\mathcal{N} = (D, u)$ be a network with $u \equiv \lambda$ and $\lambda \ge 2$, and $p$ be an integer such that $p\lambda \ge n - 1$. If $d_D^-(X) \ge pk$ for all $X \subseteq V(D) \setminus \{s\}$ with $X \ne \emptyset$, then $\mathcal{N}$ admits $k$ arc-disjoint $s$-branching flows.

**Proof:** By Theorem 1, there are $pk$ arc-disjoint $s$-branchings $B_1, \dots, B_{pk}$ in $D$. For $i \in [k]$, let $D_i$ be the digraph with $V(D_i) = V(D)$, with $A(D_i) = A(B_{(i-1)p+1}) \cup \dots \cup A(B_{ip})$, and $\mathcal{N}_i = (D_i, u)$.

Now, for every non-empty $X \subseteq V(D) \setminus \{s\}$, we conclude that $d_{D_i}^-(X) \ge p$ since each $B_i$ with $i \in [pk]$ must reach $X$ at least once. Moreover, by our choice of $p$, we have that every $\mathcal{N}_i$ is $(1, \lambda, s)$-sufficient. Thus, by Theorem 8, we have that each $\mathcal{N}_i$ admits an $s$-branching flow $x_i$. Finally, as every arc of $D$ appears in at most one digraph $D_i$, we conclude that the $s$-branching flows $x_1, \dots, x_k$ are pairwise arc-disjoint. The result follows since each of these flows can be promptly used to construct an $s$-branching flow in $\mathcal{N}$, by copying arcs and flow functions used by each flow $x_j$ with $j \in [k]$. $\square$

# 4 Hardness of finding the flows in $(k, \lambda, s)$-sufficient networks

We showed in Sections 2 and 3 that there are networks $\mathcal{N} = (D, u)$, with $D$ being $(k, \lambda, s)$-sufficient, which have $k$ arc-disjoint $s$-branching flows and others that do not have such flows. We believe it is not always computationally easy to check the $(k, \lambda, s)$-sufficiency of a digraph, but, even if we know that $D$ has such property, it is hard to decide if the desired flows exist, even if the network is constructed on a digraph formed by appending a path to the sink vertex of a multi-spindle.

**Theorem 11.** Given two integers $k$ and $\lambda$ it is NP-complete to decide whether a $(k, \lambda, s)$-sufficient network $\mathcal{N} = (D, u)$ with $u \equiv \lambda$ admits $k$ arc-disjoint $s$-branching flows.

**Proof:** We are going to reduce the 3-PARTITION problem to our problem. Given a set of natural numbers $S = \{a_1, a_2, \dots, a_{3k}\}$ and a positive integer $\lambda$ such that $\lambda/4 < a_i < \lambda/2$, for each $a_i \in S$, and such that $\sum_{i=1}^{3k} a_i = k\lambda$, the 3-PARTITION problem consists in deciding the following: can $S$ be partitioned in $k$ subsets $S_1, S_2, \dots, S_k$ so that $\sum_{a_j \in S_i} a_j = \lambda$, $1 \le i \le k$? Observe that each $S_i$ should be composed by exactly 3 elements of $S$.

From $S$, we construct a network $\mathcal{N} = (D, u)$ such that $D$ is a $(k, \lambda, s)$-sufficient network that admits $k$ arc-disjoint branching flows $x_1, x_2, \dots, x_k$ if and only if $S$ is a yes instance of the 3-PARTITION problem.

We begin the construction by adding a vertex $s$, a multi-path $P_0 = (v_1^0, v_2^0, \dots, v_\lambda^0)$ and, for every $i \in [3k]$, multi-paths $P_i = (v_1^i, v_2^i, \dots, v_{\lambda-a_i}^i)$, each one with $k$ parallel arcs between consecutive vertices. Also, for every $i \in [3k]$, we add one arc $v_{\lambda-a_i}^i v_1^0$ and $k$ parallel arcs $sv_i^i$. See Figure 4. Finally, we set $u \equiv \lambda$ to conclude the construction.

First, let us check that $D$ is $(k, \lambda, s)$-sufficient. By contradiction, assume that there exists a set $X \subseteq V(D) - s$ such that $d_D^-(X) < k \lceil |X|/\lambda \rceil$. Note that $X \ne V(D) - s$ since $|V - s| = (2k + 1)\lambda$ and $d_D^-(V - s) = k(3k)$. Recall that the in-degree of every vertex of $P_i$ is $k$ and thus the in-degree of $X$ is at least $k$. Therefore $X$ cannot be entirely contained in a unique $P_i$, $i \in [3k]$, once, in this case, $|X| \le \lambda$ and then $\lceil |X|/\lambda \rceil = 1$. Similarly, $X$ cannot be entirely contained in $P_0$, since there are $3k$ arcs arriving in $v_1^0$. Now, let $I = \{i: 1 \le i \le 3k, V(P_i) \cap X \ne \emptyset\}$. Observe that $d_D^-(X) \ge k|I|$. We are going now to consider the following cases:
<figure><img src="image_5.png" /><figcaption>**Fig. 4:** The network $\mathcal{N} = (D, c)$ constructed from an instance of the 3-PARTITION problem</figcaption></figure>

(i) $V(P_0) \cap X = \emptyset$. Then $|X| \le \lambda|I|$ and $\lceil|X|/\lambda\rceil \le |I|$, so $d_D^-(X) \ge k|I| \ge k \lceil|X|/\lambda\rceil$, a contradiction to the choice of $X$.

(ii) $X \cap V(P_0) \ne \emptyset$. Then $|X| \le \lambda|I| + \lambda = \lambda(|I| + 1)$. Take the smallest $j$ such that $v_j^0 \in X$. We analyze two possibilities:

(ii.1) $j > 1$. Then there are $k$ arcs $v_{j-1}^0 v_j^0$ that enter $X$, that is, $d^-(X) \ge k|I| + k = k(|I| + 1) \ge k \lceil|X|/\lambda\rceil$ since $|I|$ is a positive integer and $|X| \le \lambda(|I| + 1)$, a contradiction.

(ii.2) $j = 1$. Therefore $v_1^0 \in X$ and $d^-(X) \ge k|I|$. Again, we consider some cases:

(ii.2.1) If there are at least $k$ different values of $i$ for which $v_{\lambda-a_i}^i \notin X$, then such vertices contribute with $k$ to the in-degree of $X$, and again we have $d^-(X) \ge k|I| + k$.

(ii.2.2) If there is only $1 \le l < k$ different values of $i$ for which $v_{\lambda-a_i}^i \notin X$, then, in order to complete the argument, we need to estimate more precisely the size of $X$. Recall that $\lambda/4 < a_i < \lambda/2$. So, $|X| \le \lambda|I| - \frac{\lambda|I|}{4} + \lambda = \lambda(\frac{3|I|}{4} + 1)$. Observe that the amount of arcs entering $X$ is $k|I| + l = \frac{3k|I|}{4} + \frac{k|I|}{4} + l$. Since, in this case, $|I| > 2k$, we have that $\frac{k|I|}{4} \ge \frac{k^2}{2} > k$ if $k > 2$, which we can consider true by the definition of the 3-PARTITION problem ($k < 3$ would be directly a negative instance). Then, $d^-(X) \ge \frac{3k|I|}{4} + k = k(\lambda(\frac{3|I|}{4} + 1)/\lambda)$, a contradiction.

(ii.2.3) If all the last vertices are in $X$, then $d^-(X) \ge d^-(V-s)$, and we have another contradiction, since $|X| < |V(D) - s|$.

As we got a contradiction on each case, it follows that $D$ is $(k, \lambda, s)$-sufficient.

Now we assume that there exists $k$ subsets $S_1, S_2, \dots, S_k$ so that $\sum_{a_j \in S_i} a_j = \lambda, 1 \le i \le k$. In order to construct the arc-disjoint $s$-branching flows $x_1, x_2, \dots, x_k$ in $\mathcal{N}$, we establish that each of the $k$ copies of a multiple arc belongs to a different flow.

For every $1 \le i \le k$, we construct $x_i$ in the following way: If $a_j \notin S_i$, the arc $sv_1^j$ of $x_i$ will carry $\lambda - a_j$ units of flow. If $a_j \in S_i$, the arc $sv_1^j$ of $x_i$ will carry $\lambda$ units of flow. Since $\sum_{a_j \in S_i} a_j = \lambda$, the three arcs $v_{\lambda-a_j}^j$ for $a_j \in S_i$ will send the amount of flow needed to complete the branching flow in $P_0$.

Finally, we assume that there exist $k$ arc-disjoint $s$-branching flows $x_1, x_2, \dots, x_k$ in $\mathcal{N}$. We first claim that $x_r(v_{\lambda-a_i}^i v_1^0) \le a_i$, for all $r \in [k], i \in [q]$. Since $x_1, x_2, \dots, x_k$ are arc-disjoint, there is only one
flow $x_t$ which is positive in $v_{\lambda-a_i}^i$. If $x_t(v_{\lambda-a_i}^i v_1^0) > a_i$, then, as $|V(P_i)| = \lambda - a_i$, $v_1^i$ must receive more than $\lambda$ units of flow in $x_t$, that is, $x_t$ uses at least two copies of the arc $sv_1^i$. This is a contradiction because there are only $k$ copies of $sv_1^i$ and each flow must use exactly one copy. Thus, the claim follows. Each $x_r$ must reach $v_1^0$ with $\lambda$ units of flow. Since $\lambda/4 < a_i < \lambda/2$, each $x_r$ should use three arcs of the type $v_{\lambda-a_j}^j v_1^0$, and the correspondent $a_j$ forms a $S_r$. Then $S_1, S_2, \dots, S_k$ is an *yes* instance of the 3-PARTITION problem. □

Observe that, by the proof of Theorem 11, the networks constructed from negative instances of the 3-PARTITION problem are also examples that $(k, \lambda, s)$-sufficiency does not guarantee the existence of $k$ arc-disjoint $s$-branching flows.

# 5 Concluding remarks

In this work, we studied the characterization of networks admitting $k$ arc-disjoint $s$-branching flows. We showed that, in some cases (Theorems 4 and 5), an “Edmonds like” condition, which we call $(k, \lambda, s)$-sufficiency, is enough to guarantee the existence of the $k$ arc-disjoint $s$-branching flows but, in other cases, a stronger statement is needed (Section 2). This proves that $(k, \lambda, s)$-sufficiency in general is not enough to guarantee the existence of the desired $s$-branching flows in networks, although the cases for which it does are still interesting because, among other reasons, they have been resulting in polynomial-time algorithms to find the flows. Some of the positive results we prove consider restrictions on the structure of the digraphs on which the networks are built: we show that the analyzed property guarantees the existence of the flows on multi-spindles and on multi-branchings. In other words, we prove that the flows always exist in $(k, \lambda, s)$-sufficient networks built on digraphs whose underlying simple graphs are trees or spindles.

Another direction of this research would be to work on the characterization through a stronger condition, as cited before. Some interesting complexity questions are still open, such as a possible dichotomy in DAG’s between the easy and hard cases. In other words, it would be very interesting to know if there a class of digraphs $\mathcal{H}$, all of which are DAGs, such that every $(k, \lambda, s)$-sufficient network constructed on a digraph $D \in \mathcal{H}$ contains $k$ arc-disjoint $s$-branching flows, but that the same is not true for every $D \notin \mathcal{H}$.

# References

[1] R. Ahuja. *Network flows : theory, algorithms, and applications*. Prentice Hall, Englewood Cliffs, N.J, 1993.

[2] J. Bang-Jensen and S. Bessy. (Arc-)disjoint flows in networks. *Theoretical Computer Science*, 526:28–40, 2014. doi:https://doi.org/10.1016/j.tcs.2014.01.011.

[3] J. Bang-Jensen and G. Z. Gutin. *Digraphs: theory, algorithms and applications*. Springer Science & Business Media, Second edition, 2008.

[4] J. Bang-Jensen, F. Havet, and A. Yeo. The complexity of finding arc-disjoint branching flows. *Discrete Applied Mathematics*, 209:16–26, 2016. doi:https://doi.org/10.1016/j.dam.2015.10.012.

[5] S. Bessy, F. Hörsch, A.K. Maia, D. Rautenbach, and I. Sau. FPT algorithms for packing $k$-safe spanning rooted sub(d)graphs, 2021. arXiv:2105.01582.
[6] J. A. Bondy and U. S. R. Murty. *Graph theory*, volume 244 of *Graduate Texts in Mathematics*. Springer, New York, 2008. URL: http://dx.doi.org/10.1007/978-1-84628-970-5, doi:10.1007/978-1-84628-970-5.

[7] J. Costa, C. Linhares Sales, R. Lopes, and A.K. Maia. Um estudo de redes com fluxos ramificados arco-disjuntos. *Matemática Contemporânea*, 46:230–238, 2019.

[8] J. Edmonds. Edge-disjoint branchings. *Combinatorial Algorithms*, 1973.

[9] S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems. *SIAM Journal on Computing*, 5(4):691–703, 1976. doi:10.1137/0205048.

[10] D. R. Ford and D. R. Fulkerson. *Flows in Networks*. Princeton University Press, Princeton, NJ, USA, 1962.

[11] L. R. Ford and D. R. Fulkerson. Maximal flow through a network. *Canadian Journal of Mathematics*, 8:399–404, 1956. doi:10.4153/CJM-1956-045-5.

[12] A. Frank. Covering branchings. *Acta Scientiarium Mathematicarum (Szeged)*, 41:77–81, 1979.

[13] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? *Journal of Computer and System Sciences*, 63(4):512–530, 2001. doi:https://doi.org/10.1006/jcss.2001.1774.

[14] L. Lovász. On two minimax theorems in graph. *Journal of Combinatorial Theory, Series B*, 21(2):96–103, 1976. URL: http://www.sciencedirect.com/science/article/pii/0095895676900496, doi:https://doi.org/10.1016/0095-8956(76)90049-6.

[15] C. McDiarmid. Integral decomposition in polyhedra. *Math. Program.*, 25(2):183–198, 1983. doi:10.1007/BF02591770.

[16] K. Menger. Zur allgemeinen kurventheorie. *Fundamenta Mathematicae*, 10(1):96–115, 1927. URL: http://eudml.org/doc/211191.

[17] A. Schrijver. *Combinatorial optimization: polyhedra and efficiency*, volume 24. Springer Science & Business Media, 2003.

[18] Y. Shiloach. Edge-disjoint branching in directed multigraphs. *Inf. Process. Lett.*, 8(1):24–27, 1979. doi:10.1016/0020-0190(79)90086-3.

[19] R. Tarjan. A good algorithm for edge-disjoint branching. *Information Processing Letters*, 3(2):51–53, 1974. doi:10.1016/0020-0190(74)90024-6.

[20] A. Marino V. Campos, R. Lopes and A. Silva. Edge-disjoint branchings in temporal graphs. In *Proc. of the 31st International Workshop on Combinatorial Algorithms (IWOCA)*, volume 12126 of LNCS, pages 112–115, 2020. doi:10.1007/978-3-030-48966-3\_9.

[21] J. Valdes, R. E. Tarjan, and E. L. Lawler. The recognition of series parallel digraphs. In *Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing*, STOC '79, pages 1–12, New York, NY, USA, 1979. ACM. URL: http://doi.acm.org/10.1145/800135.804393, doi:10.1145/800135.804393.