# New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages

Victor Campos, Jonas Costa, Raul Lopes, Ignasi Sau

► To cite this version:

Victor Campos, Jonas Costa, Raul Lopes, Ignasi Sau. New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages. ESA 2023 - 31st Annual European Symposium on Algorithms, Sep 2023, Amsterdam, Netherlands. pp.30:1-30:18, 10.4230/LIPIcs.ESA.2023.30 . hal-04215020

HAL Id: hal-04215020

https://hal.science/hal-04215020v1

Submitted on 22 Sep 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 CC BY 4.0 - Attribution - International License
# New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages

Victor Campos [ID]

ParGO group, Universidade Federal do Ceará, Fortaleza, Brazil

Jonas Costa [x]

ParGO group, Universidade Federal do Ceará, Fortaleza, Brazil

Raul Lopes [ID]

DIENS, École normale supérieure de Paris, CNRS, France
Université Paris-Dauphine, PSL University, CNRS UMR7243, Paris, France

Ignasi Sau [ID]

LIRMM, Université de Montpellier, CNRS, Montpellier, France

## Abstract

We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of congestion two (or any other constant) from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger's Theorem on appropriately defined auxiliary digraphs, and an alternative simpler one using matroids, however with worse polynomial running time.

As an application, we manage to simplify and improve several results of Edwards et al. [ESA 2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large, which is the hard case). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular topology.

We hope that our min-max relations will find further applications as, in our opinion, they are simple, robust, and versatile to be easily applicable to different types of routing problems in digraphs.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability; Mathematics of computing → Graph algorithms

**Keywords and phrases** directed graphs, min-max relation, half-integral linkage, directed disjoint paths, bramble, parameterized complexity, matroids

**Digital Object Identifier** 10.4230/LIPIcs.ESA.2023.30

**Related Version** Full Version: https://arxiv.org/abs/2306.16134

**Funding** *Victor Campos*: FUNCAP/PRONEM PNE-0112-00061.01.00/16, and CAPES/Cofecub 88887.712023/2022-00.

*Jonas Costa*: FUNCAP/PRONEM PNE-0112-00061.01.00/16, FUNCAP PS1-0186-00155.01.00/2, and PhD scholarship granted by CAPES.

*Raul Lopes*: group Casino/ENS Chair on Algorithmics and Machine Learning, and French National Research Agency under JCJC program (ASSK: ANR-18-CE40-0025-01).

*Ignasi Sau*: ELIT (ANR-20-CE48-0008-01).

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

© Victor Campos, Jonas Costa, Raul Lopes, and Ignasi Sau; licensed under Creative Commons License CC-BY 4.0

31st Annual European Symposium on Algorithms (ESA 2023).

Editors: Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman; Article No. 30; pp. 30:1–30:18

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

Leibniz International Proceedings in Informatics
LIPICS
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# 1 Introduction

In combinatorial optimization, a *min-max relation* establishes the equality between two quantities, one naturally associated with *minimizing* the size of an object satisfying some conditions, and the other one associated with *maximizing* the size of another object. Within graph theory, famous such min-max relations include Kőnig's Theorem [15] stating the equality between the sizes of a maximum matching and a minimum vertex cover in a bipartite graph or, more relevant to this article, Menger's Theorem [18] stating, in its simplest form, the equality between the maximum number of pairwise internally disjoint paths between two vertices, and the minimum size of a vertex set disconnecting them. Typically, min-max relations come along with polynomial-time algorithms to find the corresponding objects, making them extremely useful from the algorithmic point of view.

In this article we focus on directed graphs, or *digraphs* for short, and our results are motivated by the complexity of problems related to finding *directed disjoint paths* between given terminals. More precisely, in the *k-DIRECTED DISJOINT PATHS* problem (*k*-DDP for short), we are given a digraph *G* and *k* pairs of vertices *s*<sub>*i*</sub>, *t*<sub>*i*</sub>, *i* ∈ [*k*], and the objective is to decide whether *G* contains *k* pairwise disjoint paths connecting *s*<sub>*i*</sub> to *t*<sub>*i*</sub> for *i* ∈ [*k*]. A solution to this problem is usually called a *linkage* in the literature. Here we note that disjoint paths is equivalent to paths which are vertex-disjoint.

Unfortunately, Fortune et al. [9] proved that the *k*-DDP problem is NP-complete already for *k* = 2, and Thomassen [20] strengthened this result by showing that it remains so even if the input digraph is *p*-strongly connected (see Section 2 for the definition) for any integer *p* ≥ 1. Thus, in order to obtain positive algorithmic results, research has focused on either restricting the input digraphs (for instance, to being acyclic [19] or, more generally, to having bounded directed tree-width [12]), or on considering relaxations of the problem. Concerning the latter, a natural candidate is to relax the disjointness condition of the paths, and allow for *congestion* in the vertices. Namely, for an integer *c* ≥ 2, an input of the *k*-DIRECTED *c*-CONGESTED DISJOINT PATHS problem (($k, c$)-DDP for short) is the same as in the *k*-DDP, but now we allow each vertex of *G* to occur in at most *c* out of the *k* paths connecting the terminals. In the particular case *c* = 2, a solution to this problem is usually called a *half-integral linkage* in the literature.

Despite a considerable number of attempts, it is still open whether the (*k*,*c*)-DDP problem can be solved in polynomial time for every fixed value of *c* ≥ 2 and *k* > *c* (note that if *k* ≤ *c*, then the problem can be easily solvable in polynomial time just by verifying the connectivity between each pair of terminals). A positive answer for the case *c* = 2 has been recently conjectured by Giannopoulou et al. [11]. Again, in order to obtain positive results, several restrictions and variations of the problem have been considered, such as considering several parameterizations [2, 16], restricting the input graph to have high connectivity [8], or considering an *asymmetric* version of the (*k*,*c*)-DDP problem [11, 13, 14], where the input is as in (*k*,*c*)-DDP, but the goal is to either certify that it is a *no*-instance of *k*-DDP (without congestion) or a *yes*-instance of (*k*,*c*)-DDP. This asymmetric version has been solved in polynomial time for every fixed *k* (i.e., showing that it is in XP; see Section 2) for distinct values of *c* in a series of articles, namely for *c* = 4 by Kawarabayashi et al. [13], for *c* = 3 by Kawarabayashi and Kreutzer [14], and for *c* = 2 by Giannopoulou et al. [11].

The main motivation of this article stems from the techniques used in the latter two approaches mentioned above. In a nutshell, the main strategy used in [8, 11, 13, 14] is the following. First, one computes whether the directed tree-width of the input graph is bounded by an appropriate function of *k*, the number of terminal pairs. This can be done in time X
in *k* by the results of Johnson et al. [12], or even in time FPT by the results of Campos et al. [4] (see also [3, Theorem 9.4.4]). If the directed tree-width is bounded by a function of *k*, one solves the problem in time XP by using standard programming techniques from Johnson et al. [12] (cf. Proposition 3). If not, one exploits the fact that large directed tree-width implies the existence of large “structures” that can be used to carry out the routing of the desired paths. Typically, such a structure is a *bramble*, as for example in [8], or a *cylindrical grid*, as for example in [11, 14], making use of the celebrated Directed Grid Theorem of Kawarabayashi and Kreutzer [14] (see also [4] for recent improvements). For the sake of exposition, assume henceforth that the desired structure is a *bramble*, but the strategy is essentially the same with a *cylindrical grid*.

A bramble in a digraph *D* is a set *B* of strongly connected subgraphs of *G* that pairwise either intersect or have edges in both directions. The *order* of a bramble *B* is the smallest size of a vertex set of *G* that intersects all its elements, and its *congestion* is the maximum number of times that a vertex of *G* appears in the elements of *B*. It is known that large directed treewidth implies the existence of a bramble of large order and of congestion *c* ≥ 2. For *c* = 2, a proof about how to find such a bramble in polynomial time (with degree not depending on *k*), provided that a certificate for large directed tree-width is given, can be found in [8] (see also [17] for improved bounds for brambles of higher congestion). Assume for simplicity that *c* = 2, let *B* be such a bramble, and let *S* and *T* be the sets of sources and sinks, respectively, of the corresponding problem. The idea is that if one can find a set *P*<sup>*S*</sup> of disjoint paths from *S* to appropriate elements of *B*, and a set *P*<sup>*T*</sup> of disjoint paths from appropriate elements of *B* to *T* (regardless of the ordering of the vertices of *S* and *T*), then we are done. Indeed, once the paths starting in *S* reach *B*, one can use the connectivity properties of the bramble to “shuffle” the paths appropriately as required by the terminals, and then follow the paths from *B* to *T*. The fact that the bramble has congestion two, and that the paths in *P*<sup>*S*</sup>, as well as those in *P*<sup>*T*</sup>, are pairwise disjoint, together with a good choice for the destination and starting points of the those paths, implies that every vertex of *G* occurs in at most two of the resulting paths.

Otherwise, if such sets of paths $\mathcal{P}^S$ and $\mathcal{P}^T$ do not exist, the approach consists in using
a Menger-like min-max duality to obtain an appropriate separator (or cut) between the
terminals and the bramble of size bounded by a function of $c$ and $k$, and make some progress
toward the resolution of the problem, for instance by splitting into subproblems of lower
complexity. The ways to define and to exploit such a separator depend on every particular
application, and this ad-hoc subroutine is usually one of the most technically involved parts
of the resulting algorithms [8, 11, 13, 14].

**Our results and techniques.** Motivated by the inherent common essential strategy in the above articles, we aim at finding the crucial general ingredient that can be applied in order to define and find the corresponding separators. To this end, we introduce new objects that abstract the existence of the aforementioned desired paths $\mathcal{P}^S$ and $\mathcal{P}^T$ between the terminals and the bramble. These objects are what we call *D-paths*, *T-paths* and *R-paths*. The inspiration for D-paths and T-paths is what we believe to be the common essential strategies used by Edwards et al. [8] and Giannopoulou et al. [10]. We remark that a particular set of T-paths is directly constructed in [10], particularly inside the proof of [10, Theorem 9.1]. The presence of D-paths and T-paths in [8] is more subtle in the construction of a long algorithm and a collection of non-trivial proofs. In fact, they are not explicitly built due to constraints in their techniques, but our initial results for this paper included simplifying and improving the proofs in [8] using D-paths and T-paths. Once the new proofs were obtained,
we noticed that they could be further improved by a new object which we call R-paths. It must be noted that this paper includes results for D-paths, T-paths, and R-paths but we only show applications for R-paths. The reason for this is twofold. First, T-paths have stronger properties than R-paths which might be useful for solving different problems, and D-paths are needed in the proof of the duality of T-paths. And second, these three objects are similar to the point of having similar proofs for their min-max formulas and algorithms, and showing these variations incurs little additional effort. The formal definitions of these special types of paths can be found in Section 3.

All three types of paths are associated with a defining partition $P_1, \dots, P_ℓ$ sharing some properties and differing in others. For all three, it holds that any two paths in a same part $P_i$ are disjoint, and it is possible that two paths in distinct parts share vertices. In the context of the (k,c)-DDP problem, the main difference between D-paths, T-paths, and R-paths lies in how we want to reach (or, by applying a simple trick of reversing the edges of the digraph, be reached from) the elements of a bramble $\mathcal{B}$ in the given digraph. In D-paths we ask that all paths end in distinct vertices of a given $B \subseteq V(G)$. In T-paths we ask that all paths end in distinct vertices of the bramble, and that the set containing all last vertices of the T-paths forms a *partial transversal* (see Section 2 for the definition) of $\mathcal{B}$. In R-paths we ask that all R-paths end in elements of $\mathcal{B}$ and that there is a “matching-like” association between the last vertices of the paths and elements of $\mathcal{B}$ containing these vertices.

For each type of paths we define an associated notion of *cut* and its corresponding *order*
(see e.g. Definition 10). These cuts are respectively called *D-cuts*, *T-cuts*, and *R-cuts*. We
show that each of these special types of paths and cuts satisfies a Menger-like min-max
duality, that is, that the maximum number of paths equals the minimum order of a cut
(cf. Theorems 11, 13, and 15). Moreover, the corresponding objects attaining the equality
can be found in polynomial time. The proofs of these min-max relations basically consist
in applying Menger's Theorem [18] in appropriately defined auxiliary graphs. We provide
alternative simpler proofs of these equalities using intersections and unions of matroids,
namely gammoids and transversal matroids. Even if the resulting polynomial-time algorithms
using matroids have worse running time than the ones that we obtain by applying Menger's
Theorem [18], and that using the deep theory of matroids somehow sheds less light on
interpreting the actual behavior of the considered objects, we think that it is interesting to
observe that the paths and cuts that we define are in fact matroids with nice properties.

The main application we provide for R-paths/cuts in this article is in the proof of
Theorem 16, which is an improved version of [10, Theorem 9.1] both in the requested order of
the structure and by relying on brambles instead of cylindrical grids. Informally, Theorem 16
says that given a digraph $G$, ordered sets $S, T \subseteq V(G)$, and a large (depending on the
congestion $c$ and on the size $k$ of $S$ and $T$) bramble of congestion $c$, we can either find a
large set of R-paths from $S$ to the bramble and from the bramble to $T$, which in turn are
used to appropriately connect the pairs $s_i \in S, t_i \in T$, or find a separator of size at most
$k - 1$ intersecting every path from $S$ to a large subset of the bramble, or every path from a
large subset of the bramble to $T$. Additionally, if the bramble is given, one of the outputs
can be obtained in polynomial time, computing either the paths or one of the separators.

Since in *k*-strong digraphs the separators are never found, Theorem 16 immediately
implies an improved version of a result by Edwards et al. [8]. Namely, in [8, Theorem 11]
the authors show that, when restricted to (36$k^3$ + 2$k$)-strong digraphs, every instance of
(*k*, 2)-DDP where the input digraph contains a large (depending on *k*) bramble of congestion
two is positive and a solution can be found in polynomial time. When compared to theirs, our
result is an improvement in the following ways. First, it allows us to solve (*k*, *c*)-DDP for any
$c \ge 2$ in the larger class of $k$-strong digraphs instead of being restricted to $(36k^3 + 2k)$-strong digraphs as in [8]. This bound on the strong connectivity of the digraph is almost best possible according to [8, Theorem 2], unless $P = NP$ (note that an XP algorithm in $(k-d)$-strong digraphs, for some constant $d$, may still be possible). Second, we show how to find the desired paths using a bramble of congestion $c$ and size at least $2k(c \cdot k - c + 2) + c(k-1)$, which is equal to $4k^2 + 2k - 2$ when $c=2$, instead of the size $188k^3$ required in [8]. Finally, our proof is much simpler and shorter than the proof presented in [8]. A main reason of this simplification is that we can replace the seven properties of the paths requested in [8, Lemma 12] by R-paths. It is worth mentioning that our algorithm reuses the procedure of Edwards et al. [8] to find a large bramble of congestion two in digraphs of large directed tree-width (cf. Corollary 8).

We remark that it is also possible to improve the result by Edwards et al. [8] from $(36k^3 + 2k)$-strong digraphs to $k$-strong digraphs by replacing part of their proof, namely [8, Theorem 11], by the result of Giannopoulou et al. [10, Theorem 9.1]. The trade-off is that the latter relies on the stronger structure of a cylindrical grid (and such grids do contain brambles of congestion two [8]) instead of brambles. A fundamental difference stands on the fact that, given a certificate of large directed tree-width, one can produce a bramble of congestion two in polynomial time, while finding a cylindrical grid still requires FPT time parameterized by the order of the certificate [4]. Our result using R-paths keeps the best of both worlds: we are able to drop the request on the strong connectivity of the digraph to $k$ while relying only on brambles as the routing structures.

Our second application deals with the asymmetric version of the $(k, c)$-DDP problem discussed in the introduction. By using our min-max relations, we manage to simplify and improve one of the main results of Giannopoulou et al. [11] for the case $c=2$. Instead of using the Directed Grid Theorem [14] to reroute the paths through a cylindrical grid, we reroute them through a bramble of congestion two in a very easy manner after a careful choice of the paths reaching and leaving the bramble, which is done by applying the duality between R-paths and R-cuts. Namely, we can replace [10, Theorem 9.1] (this is the full version of [11]) entirely by Theorem 16 and mostly keep the remaining part of their proof to obtain an improved version of their XP algorithm for the asymmetric version of $(k, 2)$-DDP.

We hope that our min-max relations will find further applications in the future as, in our opinion, they are quite simple, robust, and versatile to be easily applicable to different types of routing problems in digraphs. A natural candidate is the $(k, c)$-DDP problem for any choice of fixed values of $c \ge 2$ and $k > c$, which has remained elusive for some time.

**Organization.** In Section 2 we present some preliminaries. In Section 3 we state and discuss our new Menger-like statements for paths in digraphs. The applications of our results are presented in Section 4. Due to space limitations, the proofs of the results marked with “(★)” can be found in the full version of this paper, available at https://arxiv.org/abs/2306.16134.

## 2 Preliminaries

Due to space limitations, in this section we provide only the most important or non-standard preliminaries, and additional ones can be found in the full version of this paper, namely basic definitions of digraphs and matroids.

We refer the reader to [5, 7] for background on parameterized complexity, and we define here only the most basic definitions. A *parameterized problem* is a language $L \subseteq \Sigma^* \times \mathbb{N}$. For an instance $I = (x, k) \in \Sigma^* \times \mathbb{N}$, $k$ is called the *parameter*. A parameterized problem $L$ is
fixed-parameter tractable (FPT) if there exists an algorithm $\mathcal{A}$, a computable function $f$, and a constant $c$ such that given an instance $I = (x, k)$, $\mathcal{A}$ (called an FPT algorithm) correctly decides whether $I \in L$ in time bounded by $f(k) \cdot |I|^c$. For instance, the VERTEX COVER problem parameterized by the size of the solution is FPT. A parameterized problem $L$ is in XP if there exists an algorithm $\mathcal{A}$ and two computable functions $f$ and $g$ such that given an instance $I = (x, k)$, $\mathcal{A}$ (called an XP algorithm) correctly decides whether $I \in L$ in time bounded by $f(k) \cdot |I|^{g(k)}$. For instance, the CLIQUE problem parameterized by the size of the solution is in XP.

Within parameterized problems, the class W[1] may be seen as the parameterized equivalent to the class NP of classical decision problems. Without entering into details, a parameterized problem being W[1]-hard can be seen as a strong evidence that this problem is not FPT. The canonical example of W[1]-hard problem is CLIQUE parameterized by the size of the solution.

If $\mathcal{B}$ is a collection of sets, for conciseness we use $\bigcup \mathcal{B}$ to denote the set $\bigcup_{A \in \mathcal{B}} A$. For a positive integer $k$, we denote by $[k]$ the set $\{1, \dots, k\}$. For a sequence of sets $\mathcal{B} = (B_1, \dots, B_k)$, a transversal of $\mathcal{B}$ is a set $\{b_1, \dots, b_k\}$ such that $b_i \in B_i$ for all $i \in [k]$. Here we remark that the terms in $\mathcal{B}$ need not be distinct but the elements in a transversal $\{b_1, \dots, b_k\}$ are distinct. For a set of indices $J$, we use $(B_j | j \in J)$ to denote the sequence of sets indexed by $J$ so we can use $\mathcal{B} = (B_j | j \in [k])$. A subsequence of $\mathcal{B}$ is a sequence $(B_j | j \in J)$ for $J \subseteq [k]$. A partial transversal of $\mathcal{B}$ is a transversal of some subsequence of $\mathcal{B}$. For convenience, we extend all notation regarding transversals and partial transversals to collections of sets.

If $P$ is a path in a digraph $G$, we denote by $s^{-}(P)$ and $s^{+}(P)$ the first and last vertices of $P$, respectively. Every vertex of $P$ other than $s^{-}(P)$ and $s^{+}(P)$ is an *internal vertex*. For $A, B \in V(G)$, we say that $P$ is an $A \to B$ *path* if $s^{-}(P) \in A$ and $s^{+}(P) \in B$. For $A, B \subseteq V(G)$ an $(A, B)$-separator is a set $X \subseteq V(G)$ such that there are no $A \to B$ paths in $G \setminus X$.

Let $\mathcal{P}$ be a collection of paths in $G$. We use $s^{-}(\mathcal{P})$ to denote $\bigcup_{P \in \mathcal{P}} s^{-}(P)$ and $s^{+}(\mathcal{P})$ to denote $\bigcup_{P \in \mathcal{P}} s^{+}(P)$. For conciseness, we say henceforth that the paths in $\mathcal{P}$ are *disjoint* if they are pairwise vertex-disjoint. For $A, B \in V(G)$, we say that $\mathcal{P}$ is a collection of $A \to B$ paths if $s^{-}(\mathcal{P}) \subseteq A$ and $s^{+}(\mathcal{P}) \subseteq B$. For the remaining of this article and unless stated otherwise, $n$ is used to denote the number of vertices of the input digraph of the problem under consideration.

**► Theorem 1 (Menger's Theorem [18]).** Let $G$ be a digraph and $A, B \subseteq V(D)$. The maximum size of a collection of disjoint $A \to B$ paths is equal to the minimum size of an $(A, B)$-separator. Furthermore, a maximum size collection of paths and a minimum size separator can be found in time $O(n^2)$.

A digraph $G$ is *strongly connected* if for every $u, v \in V(G)$ there are paths from $u$ to $v$ and from $v$ to $u$ in $G$. A separator of $G$ is a set $X \subseteq V(G)$ such that $G \setminus X$ has a single vertex or is *not* strongly connected. If $G$ has at least $k+1$ vertices and $k$ is the minimum size of a separator of $G$, we say that $G$ is *k-strongly connected* (or *k-strong* for short). A *strongly connected component* (or *strong component* for short) of a digraph $G$ is a maximal induced subgraph of $G$ that is strongly connected.

The *directed tree-width* of digraphs was introduced by Johnson et al. [12] as a directed analogue of tree-width of undirected graphs. Informally, the directed tree-width dtw$(G)$ of a digraph $G$ measures how close $G$ can be approximated by a DAG, and the formal definition immediately implies that dtw$(G) = 0$ if and only if $G$ is an acyclic digraph (DAG). Directed tree-width and arboreal decompositions are not explicitly used in this article and thus we refer the reader to [12] for the formal definitions. Here it suffices to mention a few known results. In the same paper where they introduced directed tree-width, Johnson et al. [12] showed that $k$-DDP can be solved in XP time with parameters $k + \text{dtw}(G)$.
► **Proposition 2** (Johnson et al. [12]). *The $k$-DDP problem is solvable in time $n^{O(k+dtw(G))}$.*

Notice that every instance of the (k, c)-DDP problem with c ≥ k is trivially solvable in polynomial time by simply checking for connectivity between each pair (sᵢ, tᵢ). Thus we can always assume that c < k. It is easy to reduce the congested version to the disjoint version of DDP: it suffices to generate a new instance by making c copies of each vertex v of the input digraph, each of them with the same in- and out-neighborhood as v. A formal proof of this statement was given by Amiri et al. [1]. Hence it follows that (k, c)-DDP is also XP with parameters k and dtw(G). A direct proof of this statement is also possible by applying the same framework used to prove Proposition 2, although such a proof is not given in [12]. A similar proof for a congested version of a DDP-like problem is given by Sau and Lopes in [16]. In any case, the following holds.

► **Proposition 3.** *The (k, c)-DDP problem is solvable in time (c·n)O(c(k+dtw(G))).*

For both the *k*-DDP and (*k*,*c*)-DDP problems, (a small variation of) the result of Slivkins [19] implies that the XP time is unlikely to be improvable to FPT, even when restricted to DAGs (although the result in [19] concerns the *edge*-disjoint version of *k*-DDP, it easily implies W[1]-hardness of the disjoint version by noticing that the line digraph of a DAG is also a DAG).

As it is the case with tree-width, Johnson et al. [12] also introduced a dual notion for
directed tree-width in the form of havens. However, although the duality in the undirected
case is sharp, in the directed case it is only approximate: they showed that the directed
tree-width of a digraph *G* is within a constant factor (more precisely, a factor three) from
the maximum order of a haven of *G*. Since havens and (strict) brambles are interchangeable
in digraphs whilst paying only a constant factor for the transformation (see [6, Chapter 6]
for example), we skip the definition of the former and focus only on the latter.

**► Definition 4 (Brambles in digraphs).** A bramble $\mathcal{B} = \{B_1, \dots, B_\ell\}$ in a digraph $G$ is a collection of strong subgraphs of $G$ such that if $B, B' \in \mathcal{B}$ then $V(B) \cap V(B') \neq \emptyset$ or there are edges in $G$ from $V(B)$ to $V(B')$ and from $V(B')$ to $V(B)$. We say that the elements of $\mathcal{B}$ are the bags of $\mathcal{B}$. A hitting set of a bramble $\mathcal{B}$ is a set $C \subseteq V(G)$ such that $C \cap V(B) \neq \emptyset$ for all $B \in \mathcal{B}$. The order of a bramble $\mathcal{B}$, denoted by $\text{ord}(\mathcal{B})$, is the minimum size of a hitting set of $\mathcal{B}$. A bramble $\mathcal{B}$ is said to be strict if for all pairs $B, B' \in \mathcal{B}$ it holds that $V(B) \cap V(B') \neq \emptyset$. For an integer $c \ge 1$ we say that $\mathcal{B}$ has congestion $c$ if every vertex of $G$ appears in at most $c$ bags of $\mathcal{B}$.

See Figure 1 for an example of a bramble. Notice that if $\mathcal{B}$ is a bramble of congestion $c$ for some constant $c$, its *order* increases together with its *size*; i.e., $|\mathcal{B}|$. More precisely, since every vertex of the host digraph can hit at most $c$ elements of $\mathcal{B}$ it holds that $\text{ord}(\mathcal{B}) \ge \lfloor |\mathcal{B}|/c \rfloor$. If $\mathcal{B}' \subseteq \mathcal{B}$ then we may say that $\mathcal{B}'$ is a *subbramble* of $\mathcal{B}$.

<figure><img src="image_4.png" /><figcaption>■ **Figure 1** Example of a bramble {$B_1, B_2, B_3$} of order two.</figcaption></figure>
30:8 **New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages**

Johnson et al. [12] gave an algorithm that, given a digraph $G$, either correctly decides
that $\mathrm{dtw}(G) \le 3k-2$ (also yielding an arboreal decomposition of $G$) or produces a bramble
of order $\lfloor k/2 \rfloor$. This was later improved to an FPT algorithm by Campos et al. [4]. Although
the authors do not explicitly say that the produced bramble is strict, it is easy to verify that
this is the case in their proof, and the same holds for the proof of [12].

**Proposition 5 (Campos et al. [4]).** Let $G$ be a digraph and $t$ be a non-negative integer. There is an algorithm running in time $2^{O(t \log t)} \cdot n^{O(1)}$ that either produces an arboreal decomposition of $G$ of width at most $3t-2$ or finds a strict bramble of order $t$ in $G$.

Brambles of constant congestion are a key structure used to solve instances of (k, c)-DDP
in f(k)-strong digraphs in the approach by Edwards et al. [8], as discussed in Section 4. In
particular, they use the following result, originally proved by Kawarabayashi and Kreutzer [14]
where an XP algorithm is given, and then improved by Campos et al. [4] with an FPT algorithm
and a better dependency on k. We refer the reader to [4, 14] for the definition of well-linked
sets, and we remark that, for convenience, we present the statement of the following result in
a slightly different way than in the original article.

**Proposition 6 (Campos et al. [4]).** Let $g(k) = (t+1)(\lfloor t/2 \rfloor + 1) - 1$ and $G$ be a digraph with directed tree-width at least $3g(t) - 1$. There is an algorithm running in time $2^{O(t^2 \log t)} \cdot n^{O(1)}$ that finds in $G$ a bramble $\mathcal{B}$ of order $g(t)$, a path $P$ that intersects every bag of $\mathcal{B}$, and a well-linked set $X$ of size $t$ such that $X \subseteq V(P)$.

**Proposition 7 (Edwards et al. [8]).** There exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ satisfying the following. Let $G$ be a digraph and $t \ge 1$ be an integer. Let $P$ be a path in $G$ and $X \subseteq V(P)$ be a well-linked set with $|X| \ge f(t)$. Then $G$ contains a bramble $\mathcal{B}$ of congestion two and size $t$ and, given $G, P$, and $X$, we can find $\mathcal{B}$ in polynomial time.

Pipelining Propositions 5–7 we obtain the following.

**Corollary 8.** There is a function $f: \mathbb{N} \to \mathbb{N}$ and an FPT algorithm with parameter $t$ that, given a digraph $G$ and an integer $t \ge 1$, either correctly decides that the directed tree-width of $G$ is at most $f(t)$ or finds a bramble $\mathcal{B}$ of congestion two and size $t$ in $G$.

3 **New Menger-like statements for paths and cuts in digraphs**

In this section we present the definition and the min-max formulas associated with each
pair D-paths/D-cuts, T-paths/T-cuts, and R-paths/R-cuts. Since all three types of paths
share some properties (in fact, the major distinction between them is in how they reach their
destinations), it is convenient to adopt the following notations.

**Definition 9 (Digraph-source sequences and respecting paths).** For an integer $\ell \ge 1$, a digraph-source sequence of size $\ell$ is a pair $(\mathcal{F}, \mathcal{S})$ such that $\mathcal{F} = (G_1, \dots, G_\ell)$ is a sequence of digraphs and $\mathcal{S} = (S_1, \dots, S_\ell)$ is a sequence of subsets of vertices with $S_i \subseteq V(G_i)$ for $i \in [\ell]$. We say that a set of paths $\mathcal{P}$ respects $(\mathcal{F}, \mathcal{S})$ or, alternatively, is $(\mathcal{F}, \mathcal{S})$-respecting if there is a partition $\mathcal{P}_1, \dots, \mathcal{P}_\ell$ of $\mathcal{P}$ such that

(a) for $i \in [\ell]$, $P_i$ is a set of disjoint paths in $G_i$, and

(b) for $i \in [\ell]$, $s_i(P_i) \in S_i$.

In this case, we say that $P_1, \dots, P_\ell$ is a defining partition of $\mathcal{P}$.

Thus in any set of $(\mathcal{F}, \mathcal{S})$-respecting paths, any two paths can intersect only if they belong to distinct parts of the defining partition.
To provide some intuition within the context of the (k, c)-DDP problem, in the next three definitions one can think of the sequence ($S_1, ..., S_ℓ$) as being formed by many copies of S followed by many copies of T. Notice that any set of ($F, S$)-respecting paths includes paths *leaving* T, which seems counter-intuitive when considering the goal of solving instances of (k, c)-DDP. We remark this can be easily addressed by associating, with each copy of T in the sequence S, the digraph $G^{rev}$ obtained by reversing the orientation of every edge of G.

**D-paths and D-cuts.** Within the context of this paper, D-paths and D-cuts are used as a tool to prove our results regarding T-paths and T-cuts. In this scenario, one should think of the set B in the following definition as the set of vertices of a highly connected structure that is intended to be used to appropriately connect the last vertices of paths from S to the first vertices of paths from T.

**► Definition 10 (D-paths and D-cuts).** For an integer $ℓ ≥ 1$, let ($F, S$) be a digraph-source sequence with $F = (G_1, ..., G_ℓ)$, $S = (S_1, ..., S_ℓ)$, and $B ⊆ ⋃_{i=1}^ℓ V(G_i)$. With respect to B, we say that a set of ($F, S$)-respecting paths $\mathcal{P}$ with defining partition $P_1, ..., P_ℓ$ is a set of D-paths if

(1) for all distinct $P, P' \in \mathcal{P}$ it holds that $s^+(P) \neq s^+(P')$, and

(2a) $s^+(\mathcal{P}) \subseteq B$.

A D-cut is a sequence $\mathcal{X} = (X_0, ..., X_ℓ)$ with $X_0 \subseteq B$ such that, for $i \in [ℓ]$, the set $X_i \subseteq V(G_i)$ is an $(S_i, B \setminus X_0)$-separator in $G_i$. The order of a D-cut $X$ is $\text{ord}(\mathcal{X}) = |X_0| + \sum_{i=1}^ℓ |X_i|$.

Thus, in the definition of D-paths we ask each collection of paths associated with each $P_i$ to be pairwise disjoint in $G_i$, and the paths from distinct parts $P_i, P_j$ may share vertices in $\bigcup_{i=1}^ℓ V(G_i)$ other than the last vertices of the paths. The “D” in the name stands for “disjoint”. For the min-max formula, we prove the following.

**► Theorem 11 (★).** Let ($F, S$) be digraph-source sequence of size $ℓ$ with $F = (G_1, ..., G_ℓ)$, and let $B \subseteq \bigcup_{i=1}^ℓ V(G_i)$. With respect to $F, S$, and $B$, the maximum number of D-paths is equal to the minimum order of a D-cut. Additionally, a D-cut of minimum order and a maximum collection of D-paths can be found in time $O((ℓ \cdot n^* + |B|^2)^2)$ where $n^* = \max_{i \in [ℓ]}(|V(G_i)|)$.

**T-paths and T-cuts.** For the sake of intuition, in the next definition one should think of $\mathcal{B}$ as a bramble. Informally, and given a digraph $G$, we use T-paths and T-cuts to find a large collection of paths from a given ordered $S \subseteq V(G)$ to the bags of a subbramble $\mathcal{B}^S \subseteq \mathcal{B}$, and from the bags of another subbramble $\mathcal{B}^T \subseteq \mathcal{B}$ to $T$ (we can achieve this orientation for these paths by reversing the orientation of the edges of $G$), while ensuring that every vertex outside of $\mathcal{B}$ appears in at most two of those paths, and that all elements of $\mathcal{B}^S \cup \mathcal{B}^T$ are pairwise distinct. The first property can be achieved by simply applying Menger's Theorem (cf. Theorem 1) twice. However, by doing this, we can end with a set of paths all ending on the same bag of $\mathcal{B}$. This scenario is far from ideal, since at some point the goal is to use the strong connectivity of $G[B \cup B']$ for every $B, B' \in \mathcal{B}$ to appropriately connect the ending vertices of the paths from $S$ to the starting vertices of the paths to $T$, while maintaining the property that every vertex appears in at most two (or $c$, in the general case) of those paths. If a unique bag $B$ contains all starting and ending vertices of the paths, then connecting those vertices while maintaining such properties may be as hard as finding a solution to an instance of (k, c)-DDP in the strong digraph $G[B]$, or downright impossible to do.

Therefore, in the proofs applying similar techniques, as seen in the works by Edwards et al. [8] and by Giannopoulou et al. [10], there is considerable effort into finding paths with “good properties” that can be used to connected the paths inside of $\mathcal{B}$ (or inside of a
30:10 New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages

cylindrical grid in the case of [10]), and these properties always include, as far as we know, that the paths end or start in distinct bags of $\mathcal{B}$ (or distinct sections of the cylindrical grid). In particular, [8, Lemma 16] includes a set of seven properties over a set of paths that we can substitute by $\mathcal{T}$-paths to achieve better results in a simpler manner.

We can prove the same results using $\mathcal{R}$-paths and $\mathcal{R}$-cuts, which are simpler than $\mathcal{T}$-paths and $\mathcal{T}$-cuts. We include the proofs for the two latter objects for potential applications in which the extra properties of $\mathcal{T}$-paths and $\mathcal{T}$-cuts may become handy.

**Definition 12 (T-paths and T-cuts).** For an integer $\ell \ge 1$, let $(\mathcal{F}, \mathcal{S})$ be a digraph-source sequence with $\mathcal{F} = (G_1, \dots, G_\ell)$ and $\mathcal{S} = (S_1, \dots, S_\ell)$, and $\mathcal{B}$ be a family of subsets of $\bigcup_{i=1}^\ell V(G_i)$. With respect to $\mathcal{B}$, we say that a set of $(\mathcal{F}, \mathcal{S})$-respecting paths $\mathcal{P}$ with defining partition $\mathcal{P}_1, \dots, \mathcal{P}_\ell$ is a set of $\mathcal{T}$-paths if

(1) for all distinct $P, P' \in \mathcal{P}$ it holds that $s^+(P) \neq s^+(P')$, and

(2b) the set $s^+(\mathcal{P})$ is a partial transversal of $\mathcal{B}$.

A $\mathcal{T}$-cut is a pair $(\mathcal{B}', \mathcal{X})$ with $\mathcal{B}' \subseteq \mathcal{B}$ and such that $\mathcal{X}$ is a $\mathcal{D}$-cut with respect to $\mathcal{F}, \mathcal{S}$, and $\bigcup \mathcal{B}'$. The order of a $\mathcal{T}$-cut $(\mathcal{B}', X)$ is $\mathrm{ord}(\mathcal{B}', X) = |\mathcal{B} \setminus \mathcal{B}'| + \mathrm{ord}(\mathcal{X})$.

For convenience, we keep only one set of parenthesis, writing $\mathrm{ord}(\mathcal{B}', \mathcal{X})$ instead of $\mathrm{ord}((\mathcal{B}', \mathcal{X}))$.

Notice that conditions (1) in the definition of $\mathcal{T}$-paths is the same as in the definition of $\mathcal{D}$-paths. Thus the difference between $\mathcal{D}$-paths and $\mathcal{T}$-paths is that in the former we ask the paths to end in distinct vertices of $\mathcal{B}$, while in the latter we ask the endpoints of the paths to form a partial transversal of $\mathcal{B}$. This implies that those endpoints are distinct, and that each of them is associated with a unique element of $\mathcal{B}$. The “$\mathcal{T}$” in the name stands for “transversal”. See Figure 2 for an example of a transversal of a collection of sets.

<figure><img src="image_5.png" /><figcaption>■ **Figure 2** Example of a transversal of the collection $\{B_1, B_2, B_3, B_4\}$. For $i \in [4]$ the vertex $v_i$ is associated with the set $B_i$.</figcaption></figure>

For the $\mathcal{T}$-paths/$\mathcal{T}$-cuts duality, we prove the following.

**Theorem 13 (★).** Let $(\mathcal{F}, \mathcal{S})$ be a digraph-source sequence of size $\ell$ with $\mathcal{F} = (G_1, \dots, G_\ell)$, and let $\mathcal{B}$ be a collection of subsets of $\bigcup_{i=1}^\ell V(G_i)$. With respect to $\mathcal{F}, \mathcal{S}$, and $\mathcal{B}$, the maximum number of $\mathcal{T}$-paths is equal to the minimum order of a $\mathcal{T}$-cut. Additionally, a $\mathcal{T}$-cut of minimum order and a maximum collection of $\mathcal{T}$-paths can be found in time $\mathcal{O}((\ell \cdot n^* + |\mathcal{B}|)^2)$, where $n^* = \max_{i \in [\ell]}(|V(G_i)|)$.

**R-paths and R-cuts.** The intuition for $\mathcal{R}$-paths is similar to the one for $\mathcal{T}$-paths, as is the motivation to use these objects in the context of $(k, c)$-DDP and similar problems. The difference between them is that, if $\mathcal{P}$ is a set of $\mathcal{T}$-paths, then all vertices of the form $s^+(P)$, where $P \in \mathcal{P}$, are distinct. In $\mathcal{R}$-paths this only holds when considering paths inside of the same part of its defining partition. More precisely, given a partition $\mathcal{P}$ of a set of $\mathcal{R}$-paths as defined below, $s^+(P)$ and $s^+(P')$ are guaranteed to be disjoint only when $P$ and $P'$ are in distinct parts of $\mathcal{P}$. In Section 4 we show that this relaxation poses no problem for the application of $\mathcal{R}$-paths/$\mathcal{R}$-cuts we show in this article.
**► Definition 14 (R-paths and R-cuts).** For $\ell \ge 1$, let $(\mathcal{F}, \mathcal{S})$ be a digraph-source sequence with $\mathcal{F} = (G_1, \dots, G_\ell)$ and $\mathcal{S} = (S_1, \dots, S_\ell)$, and $\mathcal{B}$ be a family of subsets of $\bigcup_{i=1}^\ell V(G_i)$. With respect to $\mathcal{B}$, we say that a set of $(\mathcal{F}, \mathcal{S})$-respecting paths $\mathcal{P}$ with defining partition $P_1, \dots, P_\ell$ is a set of R-paths if

(1c) for some family $\mathcal{B}^* \subseteq \mathcal{B}$ there is a bijective mapping $h : \mathcal{P} \to \mathcal{B}^*$ such that $h(P) = B$ implies $s^+(P) \in B$.

An R-cut is a pair $(\mathcal{B}', \mathcal{X})$ where $\mathcal{B}' \subseteq \mathcal{B}$ and $\mathcal{X}$ is a sequence $(X_1, \dots, X_\ell)$ such that each $X_i \in \mathcal{X}$ is an $(S_i, \bigcup \mathcal{B}')$-separator in $G_i$. The order of an R-cut $(\mathcal{B}', \mathcal{X})$ is $\text{ord}(\mathcal{B}', \mathcal{X}) = |\mathcal{B} \setminus \mathcal{B}'| + \sum_{i=1}^\ell |X_i|$.

We remark that the only difference between R-paths and T-paths is that, in the latter, condition (1) ensures that all vertices forming the partial transversal of $\mathcal{B}$ are distinct. The "R" in the name stands for "representatives". For the duality, we prove the following.

**► Theorem 15 (★).** Given a digraph-source sequence $(\mathcal{F}, \mathcal{S})$ of size $\ell$ and a set $B \subseteq \bigcup_{i=1}^\ell V(G_i)$ then, with respect to $\mathcal{F}, \mathcal{S}$, and $B$, the maximum number of R-paths is equal to the minimum order of an R-cut. Additionally, an R-cut of minimum order and a maximum collection of R-paths can be found in $\mathcal{O}((k \cdot n^* + |\mathcal{B}|)^2)$ where $n^* = \max_{i \in [\ell]}(|V(G_i)|)$.

Observe that the right side of the pair forming an R-cut cannot be simply a set of vertices $X$ because, for example, a vertex $v \in X$ can be in two distinct $G_i$ and $G_j$ and be part of the separator in $G_i$ but not part of the separator in $G_j$. In this case $v$ would be counted twice in the order of the R-cut, but it is only used in one separator. Also notice that when $|\mathcal{B}|$ is larger than the allowed budget to construct an R-cut, every R-cut of appropriate order must identify some separator in some $G_i$, i.e., $\mathcal{X} \neq \emptyset$. In fact, there are only two options for the size of $\mathcal{X}$: either $\mathcal{B}' = \emptyset$ and hence $\mathcal{X} = \emptyset$, or $\mathcal{B}' \neq \emptyset$ and $|\mathcal{X}| = \ell$. In the latter case, it is possible that some $X_i \in \mathcal{X}$ are empty. In Lemma 19 we exploit this fact to show how to either find in a digraph $G$ a large collection of R-paths from a set $S$ to the vertices appearing in the elements of some sufficiently large collection $\mathcal{B}$ (corresponding to a bramble), or a small separator intersecting every path from $S$ to all such vertices.

# 4 Applications

In this section we show how to exploit the duality between R-paths and R-cuts to improve on results by Edwards et al. [8] and Giannopoulou et al. [11]. The following is the main result that we prove, and then we use it to improve on results by [8, 11].

**► Theorem 16.** Let $k, c$ be integers with $k, c \ge 2$ and $g(k, c) = 2k(c \cdot k - c + 2) + c(k - 1)$. Let $G$ be a digraph, assume that we are given the bags of a bramble $\mathcal{B}$ of congestion $c$ and size at least $g(k, c)$, and $S, T \subseteq V(G)$ with $S = \{s_1, \dots, s_k\}$ and $T = \{t_1, \dots, t_k\}$. Then in time $\mathcal{O}(k^4 \cdot n^2)$ one can either

1. find a $\mathcal{B}^* \subseteq \mathcal{B}$ with $|\mathcal{B}^*| \ge g(k, c) - c(k-1)$ and an $(S, \bigcup \mathcal{B}^*)$-separator $X_S$ with $|X_S| \le k-1$ that is disjoint from all bags of $\mathcal{B}^*$, or

2. find a $\mathcal{B}^* \subseteq \mathcal{B}$ with $|\mathcal{B}^*| \ge g(k, c) - c(k-1)$ and an $(\bigcup \mathcal{B}^*, T)$-separator $X_T$ with $|X_T| \le k-1$ that is disjoint from all bags of $\mathcal{B}^*$, or

3. find a set of paths $\{P_1, \dots, P_k\}$ in $G$ such that each $P_i$ with $i \in [k]$ is a path from $s_i$ to $t_i$ and each vertex of $G$ appears in at most $c$ of these paths.

Theorem 16 yields an XP algorithm with parameter $k$ for the $(k, c)$-DDP problem in $k$-strong digraphs, as we proceed to discuss. First, we remark that the XP time is only required when a large bramble of congestion at most $c$ is not provided. If this is the case, we
first look at the directed tree-width of $G$, which can be approximated in FPT time applying Proposition 5. If $\text{dtw}(G) \le f(k)$ for some computable function $f$, then we solve the problem applying Proposition 3. Otherwise, we apply the machinery by Edwards et al. [8] pipelining Propositions 6 and 7 to obtain a large bramble of congestion two in digraphs of large directed tree-width, and use Theorem 16 to find a solution in polynomial time, which we show to always be possible. When assuming that the input digraph is $k$-strong, only the third output of Theorem 16 is possible, and therefore as a direct consequence of Theorem 16 we obtain the following.

**Theorem 17.** Let $G$ be a $k$-strong digraph and $\mathcal{B}$ be a bramble of congestion $c \ge 2$ with $|\mathcal{B}| \ge 2k(c \cdot k - c + 2) + c(k-1)$. Then for any ordered sets $S, T \subseteq V(G)$ both of size $k$, the instance $(G, S, T)$ of $(k, c)$-DDP with $c \ge 2$ is positive and a solution can be found in time $O(k^4 \cdot n^2)$.

As mentioned in the introduction, our result improves over the result of Edwards et al. [8] by relaxing the strong connectivity of the input digraph from $36k^3 + 2k$ to $k$ (and this bound is close to the best possible unless $P = NP$), by needing a smaller bramble (from size $188k^3$ to $4k^2 + 2k - 2$ when $c = 2$), and because the proof is simpler and shorter. Finally, applying Corollary 8, Proposition 3, and Theorem 17 (thus again using Proposition 7 by [8]) we immediately obtain the following.

**Corollary 18.** For every integer $c \ge 2$, the $(k, c)$-DDP problem is solvable in $\text{XP}$ time with parameter $k$ in $k$-strong digraphs.

As a tool to prove Theorem 16, we first show how we can take many copies of digraphs $G$ and $G'$, say $\ell$ copies of each, to either find $2\ell \cdot k$ R-paths to a given collection $\mathcal{B}$ of sufficiently large size, or find an appropriate separator of size at most $k-1$ in $G$ or in $G'$.

**Lemma 19.** Let $(\mathcal{F}, S)$ be a digraph-source sequence where $\mathcal{F}$ contains $\ell$ copies of a digraph $G_S$ and $\ell$ copies of a digraph $G_T$, in this order, and $S$ contains $\ell$ copies of a set $S \subseteq V(G_S)$ and $\ell$ copies of a set $T \subseteq V(G_T)$, in this order, where $|S| = |T| = k$. Finally, let $\mathcal{B}$ be a collection of subsets of $V(G)$ with $|\mathcal{B}| \ge 2\ell \cdot k$. Then either there is a set of R-paths with respect to $\mathcal{F}, S$, and $\mathcal{B}$ of size at least $2\ell \cdot k$, or for some non-empty $\mathcal{B}' \subseteq \mathcal{B}$ there is an R-cut $(\mathcal{B}', \mathcal{X})$ of order at most $2\ell \cdot k - 1$ such that $\mathcal{X}$ contains $\ell$ copies of an $(S, \cup \mathcal{B}')$-separator $X_S$ followed by $\ell$ copies of an $(T, \cup \mathcal{B})$-separator $X_T$ with $|X_S| + |X_T| \le 2k - 1$.

**Proof.** Assume that the maximum size of a set of R-paths with respect to $\mathcal{F}, S$, and $\mathcal{B}$ is at most $2\ell \cdot k - 1$. Then by Theorem 15 there is a minimum R-cut $Y = (\mathcal{B}', \mathcal{X}')$ of order at most $2\ell \cdot k - 1$.

Since $|\mathcal{B}| \ge 2\ell \cdot k$ we conclude that $\mathcal{B}' \ne \emptyset$ and thus $|\mathcal{X}'| = 2\ell$. (we refer the reader to the discussion in the end of the first part of Section 3). Hence by the choice of $\mathcal{F}$ and $S$ and the definition of R-cuts, we can construct an R-cut $(\mathcal{B}', \mathcal{X})$ with the same order as $Y$ by simply including in $\mathcal{X}$ exactly $\ell$ copies of the $(S, \cup \mathcal{B}')$-separator $X_S$ contained in $\mathcal{X}'$, and $\ell$ copies of the $(T, \cup \mathcal{B}')$-separator $X_T$ contained in $\mathcal{X}'$. Thus the newly generated R-cut satisfies $|\mathcal{B} \setminus \mathcal{B}'| + \ell(|X_S| + |X_T|) = \text{ord}(\mathcal{B}', \mathcal{X}) = \text{ord}(\mathcal{B}', \mathcal{X}') \le 2\ell k - 1$. This immediately implies that $|X_S| + |X_T| \le 2k - 1$ and the result follows. $\quad$

Now the plan is to apply twice the duality between R-paths and R-cuts. In the first application, we consider the digraph-source sequence formed by $2k(c \cdot k - c + 1)$ copies of $G_S = G$ and then exactly as many copies of $G_T = G^{\text{rev}}$, and the same number of copies of $S$ and $T$, also in this order. If we do not find a set of $2k(c \cdot k - c + 1)$ R-paths to the bags of the
bramble, then we apply Lemma 19 and find an R-cut ($\mathcal{B}', \mathcal{X}$) of small order and a separator of size at most $k-1$ in $G_S$ or $G_T$. Since the given bramble has congestion $c$, we show that we can stop with output 1 or 2 of Theorem 16 by taking the bramble $\mathcal{B}^*$ containing all bags of $\mathcal{B}$ that are disjoint from the small separator. This holds because no bag of $\mathcal{B}^*$ can be in the “wrong side” of the separator. That is, if for instance there is an $S \to A$ path $P$ avoiding the separator $X_S$ of size at most $k-1$ in $G_S$, then every bag of $\mathcal{B}^*$ must be in $\mathcal{B} \setminus \mathcal{B}'$ since otherwise one can construct a path in $G_S \setminus X_S$ from $S$ to a bag of $\mathcal{B}'$ by using $P$ and the connectivity properties of the bramble. In this case, we also arrive at a contradiction since the size of $\mathcal{B}^*$ is too large to be contained in the R-cut.

If the R-paths are found, then we refine the digraph by carefully choosing edges to delete from $G$ in such a way that, from a second application of the duality between R-paths and R-cuts, we are guaranteed to find $2k$ R-paths that can be used to construct the $\{s_i\} \to \{t_i\}$ paths while maintaining the congestion under control. In the refined digraph, we keep the R-paths found in the first iteration and delete edges leaving vertices of the bramble appearing in bags that were not used as destinations for the R-paths. We apply Lemma 19 in this digraph and show that the only possible outcome is that the R-paths are found. Otherwise, there is an R-cut of order at most $2k-1$ and hence there is a $\mathcal{B}'' \subseteq \mathcal{B}$ that contains at least one bag $A$ that is not in the R-cut and is disjoint from the separator, say $X_S'$, of size at most $k-1$ that is part of the R-cut. Now the size of $X_S'$ implies that there is a path from $S$ to a bag disjoint from $X_S'$ avoiding the separator, and thus we can reach $A$ from $S$ avoiding $X_S'$. Finally, the refined digraph allows us to associate each vertex of the bramble used by a path in $\{P_1, \dots, P_k\}$ with a bag of the bramble, depending on where the vertex appears in the path, in such a way that no vertex is associated twice with the same bag by two distinct paths. Together with the bound on the congestion of the bramble, this immediately implies that every vertex of the digraph appears in at most $c$ paths of the set $\{P_1, \dots, P_k\}$.

**Proof of Theorem 16.** Let $G, S, T$, and $\mathcal{B}$ be as in the statement of the theorem. Define $G_S = G$ and $G_T = G^{\text{rev}}$ and let $(\mathcal{F}, S)$ be a digraph-source sequence with $\mathcal{F}$ containing, in order, $c \cdot k - c + 1$ copies of $G_S$ followed by $c \cdot k - c + 1$ copies of $G_T$, and $S$ containing, in order, the same number of copies of $S$ followed by exactly as many copies of $T$. Now, applying Lemma 19 with respect to $\mathcal{F}, S, \mathcal{B}$, and $\ell = c \cdot k - c + 1$, we conclude that either there are $2k(c \cdot k - c + 1)$ R-paths or, for some $\mathcal{B}' \subseteq \mathcal{B}$ there is an R-cut $(\mathcal{B}', \mathcal{X})$ where $\mathcal{X}$ contains $\ell$ copies of an $(S, \bigcup \mathcal{B}')$-separator $X_S$ and $\ell$ copies of an $(S, \bigcup \mathcal{B}')$-separator $X_T$ with $|X_S| + |X_T| \le 2k-1$. We first consider the case where the separators are obtained. Thus $|X_S| \le k-1$ or $|X_T| \le k-1$. Since both cases are symmetric (the $T \to X_T$ paths become $X_T \to T$ paths when we restore the orientation of the edges of $G_T$), we suppose without loss of generality that $|X_S| \le k-1$.

Let $\mathcal{B}^*$ contain all bags of $\mathcal{B}$ that are disjoint from $X_S$. Since $\mathcal{B}$ has congestion $c$ we conclude that $|\mathcal{B}^*| \ge g(k, c) - c(k-1)$. We show that no vertex appearing in a bag of $\mathcal{B}^*$ is reachable from $S$ in $G_S \setminus X_S$. By contradiction, assume that there is an $S \to A$ path $P$ in $G_S \setminus X_S$ for some $A \in \mathcal{B}^*$. If there is $A' \in \mathcal{B}^* \cap \mathcal{B}'$ then we can use the strong connectivity of $G_S[A \cup A']$ and the path $P$ to construct an $S \to A'$ path in $G_S \setminus X_S$, contradicting the choice of $X_S$. Thus in this case $\mathcal{B}^*$ must be entirely contained in $\mathcal{B} \setminus \mathcal{B}'$. Again we obtain a contradiction since $2k(c \cdot k - c + 2) \le |\mathcal{B}^*| \le |\mathcal{B} \setminus \mathcal{B}'| \le \text{ord}(\mathcal{B}', \mathcal{X}) < 2k(c \cdot k - c + 1)$. In other words, the existence of path from $S$ to a vertex in a bag of $\mathcal{B}^*$ avoiding $X_S$ implies that every bag of $\mathcal{B}^*$ is reachable from $S$ in $G_S \setminus X_S$ and thus such path cannot exist since $\mathcal{B}^*$ is too large to be contained in any R-cut of order less than $2k(c \cdot k - c + 1)$. We conclude that no bag $A \in \mathcal{B}^*$ is reachable from $S$ in $G_S \setminus X_S$, and and output 1 of the theorem follows. Symmetrically, output 2 of the theorem follows if $|X_T| \le k-1$.
30:14 New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages

Assume now that a set of R-paths $\mathcal{P}$ of size at least $2k(c \cdot k - c + 1)$ is found. Let $\mathcal{B}^1 \subseteq \mathcal{B}$ and let $h: \mathcal{P} \to \mathcal{B}^1$ be the bijective mapping as in (1c) of Definition 14. Thus $h(p) = \mathcal{B}$ implies that $\mathbf{s}^+(P) \in \mathcal{B}$. Since $|S| = |T| = k$, we can split $\mathcal{P}$ into two sets of equal size $\mathcal{P}^S$ and $\mathcal{P}^T$, where every path in $\mathcal{P}^S$ is a path leaving $S$ in $G_S$ and every path in $\mathcal{P}^T$ is a path leaving $T$ in $G_T$. We define $\mathcal{B}_S = \{h(P) \in \mathcal{B}^1 \mid P \in \mathcal{P}^S\}$ and $\mathcal{B}_T = \{h(P) \in \mathcal{B}^1 \mid P \in \mathcal{P}^T\}$. The next step is to refine $\mathcal{P}$ to make it minimal with respect to $\mathcal{B}$. That is, we say that $\mathcal{P}$ is $\mathcal{B}$-minimal if no path of $\mathcal{P}$ contains an internal vertex that is in a bag $\mathcal{B} \setminus (\mathcal{B}_S \cup \mathcal{B}_T)$. In other words, when following a path $P \in \mathcal{P}$ from the first to the last vertex, if we find an internal vertex $v$ in a bag $B$ that is not in $\mathcal{B}_S$ nor in $\mathcal{B}_T$, we swap $P$ in $\mathcal{P}$ by its subpath ending in $v$ and update $\mathcal{B}_S$ or $\mathcal{B}_T$ accordingly. Clearly, condition (1c) of Definition 14 still hold with respect to the new choice of $\mathcal{P}$, and therefore from now on we assume that $\mathcal{P}$ is $\mathcal{B}$-minimal. This property is important later to bound the maximum number of times that a vertex can appear in the $S \to T$ paths we construct.

Next, we reduce $G_S$ and $G_T$ to digraphs that are still well connected to $\mathcal{B}$, thus ensuring that we can find a large set of R-paths in the new digraphs, in which we can maintain control over how many times a vertex can appear in the $S \to T$ paths we construct from these new R-paths. To this end, define

$$V_S = \bigcup_{P \in \mathcal{P}^S} (V(P) \setminus \{\mathbf{s}^+(P)\}) \cup \bigcup_{A \in \mathcal{B}_S} A \quad \text{and} \quad V_T = \bigcup_{P \in \mathcal{P}^T} (V(P) \setminus \{\mathbf{s}^+(P)\}) \cup \bigcup_{A \in \mathcal{B}_T} A. \quad (1)$$

Finally, we construct the digraphs $G'_S$ and $G'_T$ starting from $G_S$ and $G_T$, respectively, applying the following two rules:

- For every $v \in V(G_S)$, if $v \in (\bigcup \mathcal{B}) \setminus V_S$ then we delete from $G'_S$ every edge leaving $v$.

- For every $v \in V(G_T)$, if $v \in (\bigcup \mathcal{B}) \setminus V_T$ then we delete from $G'_T$ every edge leaving $v$.

Consider the digraph-source sequence $(\{G'_S, G'_T\}, \{S, T\})$ and let $\mathcal{B}' = \mathcal{B} \setminus (\mathcal{B}_S \cup \mathcal{B}_T)$, and notice that $\mathcal{B}'$ may not be a bramble in $G'_S$ nor in $G'_T$. Clearly $|\mathcal{B}'| \ge g(k, c) - 2k(c \cdot k - c + 1) = c(k - 1) + 2k > 2k$. We apply Lemma 19 with respect to $\{G'_S, G'_T\}, \{S, T\}$ (and thus $\ell = 1$), and $\mathcal{B}'$, to either obtain a set of R-paths $\mathcal{P}'$ of size at least $2k$ or an R-cut $(\mathcal{B}'', \{X'_S, X'_T\})$ with order at most $2k - 1$ where $|X'_S| + |X'_T| \le 2k - 1$ and $\mathcal{B}'' \ne \emptyset$. We claim that only the first output is possible. By contradiction, assume that the R-cut and the separators were obtained and, without loss of generality, that $|X_S| \le k - 1$. First notice that the upper bound on the order of the R-cut implies that $|\mathcal{B}'' \setminus \mathcal{B}'| \ge c(k - 1) + 1$. Since $|X_S| \le k - 1$ this implies that there is at least one bag $A' \in \mathcal{B}''$ that is disjoint from $X_S$ and not included in R-cut.

Now, set $q = 2(c \cdot k - c + 1)$ and let $\mathcal{P}_1, \dots, \mathcal{P}_q$ be the defining partition of $\mathcal{P}$. That is, for every $i \in [q]$, the part $\mathcal{P}_i$ is a set of $k$ disjoint paths in the $i$-th digraph of $\mathcal{F}$ (this is possible since $|S| = |T| = k$ and hence $\mathcal{P}$ cannot contain more than $k$ disjoint paths in any digraph in $\mathcal{F}$). Thus exactly $q/2$ parts $\mathcal{P}_i$ contain only paths starting in $S$. Now the size of $X_S$ allows it to intersect at most $c(k - 1)$ bags of $\mathcal{B}$, and thus for some $\mathcal{P}_i$ no bag in $\mathcal{B}_i = \{A \in \mathcal{B}_S \mid P \in \mathcal{P}_i \text{ and } \mathbf{s}^+(P) \in A\}$ is intersected by $X'_S$. Since $|X'_S| \le k - 1$, there is a $P \in \mathcal{P}_i$ from $S$ to a bag $A \in \mathcal{B}_i$ that is not intersected by $X'_S$. By the choice of $G'_S$ this path also exists in this digraph and, since $\mathbf{s}^+(P) \in A$ and $A \in \mathcal{B}_S$, every edge of $G_S$ leaving every vertex in $A$ is kept in $G'_S$ and thus $G'_S[A]$ is strong. Now, as $\mathcal{B}$ is a bramble, we can construct a path from $S$ to $A'$ (remember that $A' \in \mathcal{B}''$ and $A' \cap X_S = \emptyset$) by following the path $P$ and then taking a path from $\mathbf{s}^+(P)$ to $A'$ in $G'_S[A \cup A']$, which in turn is guaranteed to exist since either $A \cap A' \ne \emptyset$ or there is an edge from $A$ to $A'$ in $G'_S$. This contradicts our assumption that $(\mathcal{B}'', \{X'_S, X'_T\})$ is an R-cut and the claim follows.
Assume now that a set $\mathcal{P}'$ of $2k$ R-paths is obtained. Therefore, there are disjoint paths $\{Q_1^S, \dots, Q_k^S\}$ leaving $S$ and disjoint paths $\{Q'_1, \dots, Q'_k\}$ leaving $T$ in $\mathcal{P}$. By recovering the orientation of the edges of $G'_T$ (we remind the reader that $G_T = G^{\text{rev}}$), we construct paths $\{Q_1^T, \dots, Q_k^T\}$ reaching $T$ in $G$ and, by renaming the paths if needed, we assume that, for $i \in [k]$, each $Q_i^S$ is a path starting in $s_i$ and each $Q_i^T$ is a path ending in $t_i$. Moreover, by condition (1c) in the definition of R-paths (see Definition 14), each $s^+(Q_i^S)$ is associated with a unique bag $A_i \in \mathcal{B}$ and each $s^-(Q_i^T)$ is associated with a unique bag $A'_i \in \mathcal{B}$, such that all bags $A_1, \dots, A_k, A'_1, \dots, A'_k$ are distinct. Hence, since $\mathcal{B}$ is a bramble, it follows that for every $i \in [k]$ we can find a shortest path $Q_i$ from $s^+(Q_i^S)$ to $s^-(Q_i^T)$ in the strong digraph $G[A_i \cup A'_i]$. Finally, we construct the desired paths $\{P_1, \dots, P_k\}$, such that each $P_i$ with $i \in [k]$ is a path from $s_i$ to $t_i$, by appending $Q_i$ to $Q_i^S$ and then $Q_i^T$ to the resulting path. Notice that this construction may result in a walk instead of a path, but every walk can be easily shortened into a path $P_i$.

We now claim that every vertex of $G$ appears in at most $c$ paths of the collection $\{P_1, \dots, P_k\}$. First, notice that since the paths $\{Q_1^S, \dots, Q_k^S\}$ are disjoint and the paths $\{Q_1^T, \dots, Q_k^T\}$ are disjoint as well, any vertex not appearing in any bag of $\mathcal{B}$ can appear in at most two paths of $\{P_1, \dots, P_k\}$. Assume now that $v$ is a vertex appearing in some bag of $\mathcal{B}$. Depending on where $v$ is located in the paths $Q_i^S, Q_i^T$, and $Q_i$, we associate $v$ with a bag of $\mathcal{B}$. Since $\mathcal{B}$ has congestion $c$, this immediately validates the claim and the result follows. We remind the reader of our assumption that $\mathcal{P}$ is $\mathcal{B}$-minimal, and look again at Equation 1. If $v$ is in $V_S$ because $v$ is in path $P \in \mathcal{P}^S \cup \mathcal{P}^T$ and $v \neq s^+(P)$, then we say that $v$ is a *type 1* vertex. Otherwise, we say that $v$ is a *type 2* vertex.

For $i \in [k]$, if $v$ is a internal vertex of some $Q_i^S$, then $v \in V^S$ and is either a type 1 or a type 2 vertex. If $v$ is of type 1, then $v$ is an internal vertex of some path $P \in \mathcal{P}^S$ and $v \neq s^+(P)$. Since $\mathcal{P}$ is $\mathcal{B}$-minimal, this implies that $v$ is in some destination bag of $\mathcal{B}_S$ and we associate $v$ with this bag. If $v$ is of type 2, then $v$ is not an internal vertex of any path in $\mathcal{P}^S$ and is in some bag of $\mathcal{B}_S$. We associate $v$ with this bag. Since the paths $\{Q_1^S, \dots, Q_k^S\}$ are disjoint, $v$ appears only in one of those paths and thus no other $Q_j^S$ can associate $v$ with another bag of $\mathcal{B}$. The analysis is similar if $v$ is an internal vertex of some $Q_j^T$. Notice that it is possible that $v$ is in both $Q_i^S$ and $Q_j^T$ and, in this case, those two paths associate $v$ with two distinct bags of $\mathcal{B}_S$ and $\mathcal{B}_T$, respectively.

Now let $\mathcal{B}^2 \subseteq \mathcal{B}'$ and let $h' : \mathcal{P} \to \mathcal{B}^2$ be a bijective mapping as in (1c) of Definition 14. If $v$ is a vertex of some $P_i$ from $s^+(Q_i^S)$ to $s^-(Q_i^T)$ then we associate $v$ with $h'(Q_i^S)$ if $v \in h'(Q_i^S)$, and we associated $v$ with $h'(Q_i^T)$ if $v \in h'(Q_i^T)$.

Now, for $i, j \in [k]$, every path of the form $Q_i^S, Q_j^T$, or $P_i$ associates each of its vertex inside of the bramble with a unique bag of $\mathcal{B}$, each vertex associated with some bag appears in $V(Q_i^S) \setminus \{s^+(Q_i^S)\}, V(Q_j^T) \setminus \{s^-(Q_j^T)\}$, or $V(Q_i)$, no two distinct $Q_i^S, Q_j^T$ associate a vertex $v$ with the same bag, and the same holds with relation to distinct pairs of paths of the form $Q_i, Q_j$ and $Q_i^T, Q_j^T$. We remark that while it is possible that some $v$ appears in both $Q_i^S$ and $Q_j^T$, this does not pose an issue since in this case $v$ is associated with a pair of distinct bags $B \in \mathcal{B}_S$ and $B' \in \mathcal{B}_T$ by $Q_i^S$ and $Q_i^T$, respectively. Since $\mathcal{B}$ has congestion $c$, it follows that every vertex is associated with at most $c$ bags, which implies that every vertex is in at most $c$ paths of $\{P_1, \dots, P_k\}$, and the result follows.

The bound on the running time follows by Theorem 15 and by observing that a set of R-paths can be made $\mathcal{B}$-minimal in time $O(c \cdot k^2 \cdot n^2)$ ◀

**Application to the asymmetric version of (k, c)-DDP.** Theorem 16 is a direct translation of Giannopoulou et al. [10, Theorem 9.1] to our setting. As mentioned in the introduction, we can prove a weaker version of Theorem 17 by replacing Theorem 16 by [10, Theorem 9.1].
In comparison with the result by Edwards et al. [8], with this approach we can drop the
bound on the strong connectivity of the digraph from (36$k^3$ + 2$k$) to $k$, and the trade-off is
that in this case we have to rely on the topology of *cylindrical grids* to connect the paths,
instead of a bramble of congestion *c*. Although it is true that every digraph with large
directed tree-width contains a large cylindrical grid [14], and that such a grid can be found
in FPT time [4], to find a cylindrical grid of order *k* the directed tree-width of the digraph
has to increase much more than it is needed to find a bramble of congestion two (although
both dependencies still consist of a non-elementary tower of exponentials). Additionally, we
remark that if the goal is to solve the (*k*,*c*)-DDP problem with *c* ≥ 8, then as stated in
Theorem 17 a bramble of congestion eight suffices, and a polynomial dependency on how
large the directed tree-width of a digraph must be to guarantee the existence of a large
bramble of congestion eight was shown by Masarík et al. [17].

On the other hand, Theorem 16 improves upon [10, Theorem 9.1] in both its statement, since we use brambles instead of cylindrical grids, and in simplicity. Indeed, brambles of bounded congestion seem to be a weaker structure than cylindrical grids, since it is possible to extract such brambles with order $t$ from a cylindrical grid of order at least $2t$ (see [8, Lemma 9]), and the bound on how large the directed tree-width of a digraph has to be to guarantee the existence of such a bramble with size $t$ is, in many cases (see [17] for instance) and as far as we know also in the general case, substantially better than what is needed to find a cylindrical grid with the same order. Additionally, the algorithm to find cylindrical grids runs in FPT time [4] given a certificate of large directed tree-width and, in contrast, a large bramble of congestion two can be found in polynomial time when such certificates are provided, as stated in Proposition 7. Finally, we only ask the bramble to have order $2k(c \cdot k - c + 2) + c(k - 1)$ (which equals $4k^2 + 2k - 2$ when $c = 2$) instead of order $k(6k^2 + 2k + 3)$ for the cylindrical grid in [10, Theorem 9.1], where the goal is to compute solutions for $(k, 2)$-DDP. Their proof relies on the topology of cylindrical grids to connect the paths inside of this structure, after some careful selection on how to reach it from $S$ and leave it to reach $T$. In our proof of Theorem 16, it is very simple to connect the paths inside the bramble. Indeed, after applying twice the duality between R-paths and R-cuts, for each $i \in [k]$ we simply connect the ending vertex of the path from $s_i$ to the bramble containing the starting vertex of the path from the bramble to $t_i$, using the strong connectivity of the digraph induced by $B \cup B'$, where $B$ is the bag associated with $s_i$ and $B'$ the bag associated with $t_i$.

Their result [10, Theorem 9.1] is one of the cornerstones in their algorithm to solve the
asymmetric version of (*k*, 2)-DDP. Recall that, given ordered sets of terminals {*s*₁, ..., *s*ₖ}
and {*t*₁, ..., *t*ₖ}, the goal in this asymmetric version is to either produce a collection of
paths from each *s*ᵢ to the corresponding *t*ᵢ such that every vertex is in at most two paths
of the collection, or conclude that there is no collection of disjoint {*s*ᵢ} → {*t*ᵢ} paths.
In the first case, we say that we have constructed a *half-integral linkage*. In the second
case, we say that we have a *no*-instance. At any point of their dynamic programming
algorithm, if one of the subproblems they define deals with an instance in which there is no
small separator intersecting all paths from *S* to the grid or from the grid to *T*, then they
apply [10, Theorem 9.1] to find a solution to the instance. If a separator is found, then
they generate two easier instances, one of bounded directed tree-width, and one with fewer
number of terminals. Intuitively, the same holds true if we substitute [10, Theorem 9.1] by
our Theorem 16. In the full version of this paper, we give an informal sketch of why this is
indeed the case.
References

1 Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with congestion in acyclic digraphs. *Information Processing Letters*, 151:105836, 2019. doi: doi.org/10.1016/j.ipl.2019.105836.

2 Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with congestion in acyclic digraphs. *Information Processing Letters*, 151, 2019. doi:10.1016/j.ipl.2019.105836.

3 Jørgen Bang-Jensen and Gregory Gutin. *Classes of Directed Graphs*. Springer Monographs in Mathematics, 2018. doi:10.1007/978-3-319-71840-8.

4 Victor Campos, Raul Lopes, Ana Karolinna Maia, and Ignasi Sau. Adapting the Directed Grid Theorem into an FPT Algorithm. *SIAM Journal on Discrete Mathematics*, 36(3):1887–1917, 2022. doi:10.1137/21M1452664.

5 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, and Dániel Marx. *Parameterized Algorithms*. Springer, 2015.

6 Matthias Dehmer and Frank Emmert-Streib. *Quantitative Graph Theory: Mathematical Foundations and Applications*. Discrete Mathematics and its Applications. Chapman and Hall/CRC, 2014.

7 Rodney G. Downey and Michael R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013.

8 Katherine Edwards, Irene Muzi, and Paul Wollan. Half-Integral Linkages in Highly Connected Directed Graphs. In *Proc. of the 25th Annual European Symposium on Algorithms (ESA)*, volume 87 of *LIPIcs*, pages 36:1–36:12, 2017. Full version available in arXiv:1611.01004. doi:10.4230/LIPIcs.ESA.2017.36.

9 Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. *Theoretical Computer Science*, 10:111–121, 1980. doi:10.1016/0304-3975(80)90009-2.

10 Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon. The canonical directed tree decomposition and its applications to the directed disjoint paths problem, 2020. This article is the full version of reference [11]. arXiv:2009.13184.

11 Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon. Directed tangle tree-decompositions and applications. In *Proc. of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 377–405, 2022. The full version of this article is reference [10]. doi:10.1137/1.9781611977073.19.

12 Thor Johnson, Neil Robertson, Paul Seymour, and Robin Thomas. Directed tree-width. *Journal of Combinatorial Theory, Series B*, 82(01):138–154, 2001. doi:10.1006/jctb.2000.2031.

13 Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Stephan Kreutzer. An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In *Proc. of the 46th Annual ACM on Symposium on Theory of Computing (STOC)*, pages 70–78, 2014. doi: 10.1145/2591796.2591876.

14 Ken-ichi Kawarabayashi and Stephan Kreutzer. The Directed Grid Theorem. In *Proc. of the 47th Annual ACM on Symposium on Theory of Computing (STOC)*, pages 655–664. ACM, 2015. doi:10.1145/2746539.2746586.

15 Dénes Kőnig. Gráfok és mátrixok. *Matematikai és Fizikai Lapok*, 38:116–119, 1931.

16 Raul Lopes and Ignasi Sau. A relaxation of the Directed Disjoint Paths problem: A global congestion metric helps. *Theoretical Computer Science*, 898:75–91, 2022. doi:10.1016/j.tcs. 2021.10.023.

17 Tomás Masarík, Marcin Pilipczuk, Pawel Rzazewski, and Manuel Sorge. Constant congestion brambles in directed graphs. *SIAM Journal on Discrete Mathematics*, 36(2):922–938, 2022. doi:10.1137/21m1417661.

18 Karl Menger. Zur allgemeinen kurventheorie. *Fundamenta Mathematicae*, 10(1):96–115, 1927. URL: http://eudml.org/doc/211191.
30:18 New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages

19 Aleksandrs Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs.
*SIAM Journal on Discrete Mathematics*, 24(1):146–157, 2010. doi:10.1137/070697781

20 Carsten Thomassen. Highly connected non-2-linked digraphs. *Combinatorica*, 11(4):393–395, 1991. doi:10.1007/BF01275674