Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, $(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all $s_2t_2$-paths, and all $s_3t_3$-paths. The parameterized complexity of this case has been open since Chitnis, Cygan, Hajiaghayi, and Marx proved fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012, and Pilipczuk and Wahlstr\"{o}m proved the W[1]-hardness of the 4-terminal-pairs case at SODA 2016. On the technical side, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch, Pilipczuk, Wahlstr\"{o}m, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain.We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width, a recently introduced structural parameter [Bonnet, Kim, Thomass\'{e}, Watrigant, FOCS 2020]: By a recent characterization [Bonnet, Giocanti, Ossona de Mendes, Simon, Thomass\'{e}, Toru\'{n}czyk, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor, a vertex corresponding to the ``middle'' box in the grid minor can be proclaimed irrelevant -- not contained in the sought solution -- and thus reduced.


Introduction
Parameterized complexity studies the existence of fixed-parameter algorithms: algorithms with running time bound by f (k) · n c , where n is the size of the input, c is an arbitrary constant, f is an arbitrary computable function, and k is the parameter, which is a selected secondary measure of the input that is intended to reflect the hardness of the instance.
Graph separation problems yield a class of combinatorial problems where the goal is to find a small vertex or edge set in the given graph that satisfies some separation requirements. For example, Multiway Cut equips the input graph G with a set T ⊆ V (G) of terminals and asks to cut all paths between any two distinct terminals, whereas Subset Feedback Vertex Set equips the input graph G with a set R ⊆ V (G) of red vertices and asks to cut all cycles that contain at least one red vertex. The study of graph separation problems, with the cardinality of the sought cut as the natural choice of the parameter, has been one of the more vivid areas of parameterized complexity in the recent 15 years. A number of interesting algorithmic techniques emerged: important separators [21,5], applications of matroid techniques [18,19], shadow removal [9,24], randomized contractions [6,11], LP-guided branching [12,13,14], and treewidth reduction [23], among others.
The progress somewhat stalled around 5 years ago in the following state: we understood the complexity of the main bulk of graph separation problems in undirected graphs, mostly thanks to the wide variety of algorithmic techniques therein. However, in directed graphs, a number of questions remained widely open.
The Multicut problem is, given a graph G and a family T of pairs of vertices (called terminals), to delete a minimum number of non-terminal vertices so that for every terminal pair (s, t) ∈ T , there is no path from s to t in the remaining graph. The parameterized complexity of this problem in undirected graphs, after being a long standing open problem for a while, has been resolved around 2010 independently by two groups of researchers [24,4]. In directed graphs, the problem in full generality was quickly observed to be W [1]-hard [24]. However, some restrictions turned out to be tractable: the case of directed acyclic graphs [17], Directed Multiway Cut, where we are given just a set of terminals and we ask to cut all paths between every pair of distinct terminals, or Directed Multicut with two terminal pairs [9]. Observe that the one-terminal-pair case is just the classic Minimum Cut problem. In 2015, Pilipczuk and Wahlström [25] provided a hardness reduction for the four-terminal-pairs case, leaving the three-terminal-pairs case open until now.
Directed Multicut with three terminal pairs was by far not the only open problem left in the parameterized complexity of directed graph separation problems. Other open problems included the notoriously difficult Chain SAT problem [7] and most of the problems in the weighted setting. Here, the deletable objects (edges or vertices) have integer weights, and the question is to find a solution of cardinality at most k and minimum total weight (where k is the given parameter). One of the reasons for such a state of affairs was a lack of algorithmic techniques in directed graphs: Among all the aforementioned tools in undirected graphs, only important separators and shadow removal generalize to directed graphs [9,8].
Very recently, at STOC 2022, a new algorithmic technique for cut problems in directed graphs has been presented by Kim, Kratsch, Pilipczuk, and Wahlström [15], namely flow-augmentation. This new technique led to fixed-parameter algorithms for Chain SAT and numerous weighted versions of graph separation problems. In this work, we use it to answer the question of the parameterized complexity of Directed Multicut with three terminal pairs positively. Theorem 1.1. Directed Multicut with three terminal pairs is fixed-parameter tractable when parameterized by the size of the cutset (with a randomized algorithm).
Flow-augmentation alone is by far not enough to show Theorem 1.1. In the basic usage, the main tool of directed flow-augmentation [15] can be stated as follows: Theorem 1.2. There exists a polynomial-time randomized algorithm that, given a directed graph G, two distinguished vertices s, t ∈ V (G), and an integer k, outputs a set A ⊆ V (G)×V (G) (called augmentation edges) such that for every minimal edge st-cut Z of cardinality at most k, with probability 2 −O(k 4 log k) the cut Z becomes a minimum edge st-cut in G + A.
Here, G + A is the graph obtained from G by adding the arcs in A. That is, with good probability, the added arcs A not only do not break the edge cut Z (that is, connect the s-side of the cut to the t-side), but also increase the connectivity of the graph so that Z becomes a minimumcardinality cut. We remark that all randomization in Theorem 1.1 comes from Theorem 1.2. That is, if Theorem 1.2 were deterministic, so would be the algorithm of Theorem 1.1.
The following point of view on Theorem 1.2 turns out to be particularly useful. Let G be a directed graph, s, t ∈ V (G), and let k be the size of a minimum edge st-cut. How does the space of all minimum edge st-cuts look like? Let P be any maximum st-flow, seen as a collection of k edge-disjoint paths from s to t. Any minimum edge st-cut contains exactly one edge from each path in P . Furthermore, for every P 1 , P 2 ∈ P and every u 1 ∈ V (P 1 ), u 2 ∈ V (P 2 ), if G contains a path Q from u 1 to u 2 that does not contain any edge of P, then any minimum edge st-cut cannot contain an edge of P 1 after u 1 and an edge of P 2 before u 2 at the same time. This motivates the following CSP formulation. Every path P ∈ P becomes a variable x(P ) with domain E(P ), ordered naturally along P . For every tuple (P 1 , P 2 , u 1 , u 2 ) as above (i.e., P 1 , P 2 ∈ P, u 1 ∈ V (P 1 ), u 2 ∈ V (P 2 ), G contains a path from u 1 to u 2 that does not contain any edge of P), we introduce a constraint (x(P 1 ) ≤ u 1 ) ∨ (x(P 2 ) ≥ u 2 ), where the inequalities have the natural meaning of being before/after the corresponding vertex along the corresponding path. It is relatively easy to see that the space of all feasible solutions to such a CSP instance is exactly the space of all minimum edge st-cuts in G. In this light, Theorem 1.2 can be understood as follows: we can subsample the space of all minimal edge st-cuts in G of cardinality at most k, so that every cut is sampled with good probability (i.e., 2 −O(k 4 log k) ) and the subsampled set can be described by the aforementioned CSP instance.
A meticulous reader may observe that flow-augmentation speaks about edge cuts while Directed Multicut asks for a vertex cut. However, in directed graphs there are standard reductions between these two variants of the problem. Thus, the above framework of a CSP formulation can be easily adapted to minimal vertex st-cuts of cardinality at most k (where s and t are undeletable).
In the context of Directed Multicut with three terminal pairs, we can use flow-augmentation as follows. Let S be an inclusion-wise minimal solution to an input instance (G, k, (s i , t i ) i=1,2,3 ). Clearly, S = S 1 ∪ S 2 ∪ S 3 where S i is a minimal vertex s i t i -cut. Hence, we can apply flowaugmentation separately to (G, k, (s i , t i )) for i = 1, 2, 3, obtaining a set of augmentation edges A i . With good probability, for every i = 1, 2, 3 the set S i becomes a minimum vertex st-cut in G+A i . Let P i be a maximum (vertex-capacitated) s i t i -flow in G + A i and consider the aforementioned CSP formulation with variables {x i (P ) | P ∈ P i } and sets of constraints C i .
The crux of the difficulty of Directed Multicut lies in the fact that the sets S i may not be pairwise disjoint; in a sense, we can save on reusing some vertices in S to separate multiple terminal pairs. In the CSP regime, it means that for some i, j ∈ {1, 2, 3} and P ∈ P i and Q ∈ P j , the variables x i (P ) and x j (Q) describe the same vertex of S. Note that there is only 2 O(k log k) options of which pairs of variables describe the same vertex; we can exhaustively guess the set K of all pairs (i, j, P, Q) as above. Every (i, j, P, Q) ∈ K induces a constraint that x i (P ) and x j (Q) is the same vertex; in the CSP language, this is a permutation constraint, denoted henceforth C(i, j, P, Q), between a subset of the domain of x i (P ) and a subset of the domain of x j (Q).
It is important to observe that -assuming the flow-augmentation steps were successful and in the branching step we made the correct choice of which variables describe the same vertexthe final CSP instance is an equivalent reformulation of the original Directed Multicut instance. That is, every solution to the obtained CSP instance gives a set of non-terminal vertices that cuts all paths from s i to t i for i = 1, 2, 3. The coincidences guessed in the branching step determine the cardinality of the obtained cut, and we can terminate all branches that lead to cuts larger than k. Furthermore, every inclusion-wise minimal solution to the original Directed Multicut instance that is compliant with the flow-augmentation and branching steps yields a feasible solution to the obtained CSP instance. Thus, it "only" remains to solve the obtained CSP instance.
To this end, we need to understand how complex the permutation constraints C(i, j, P, Q) can be. Note that the number of variables is small -bounded by 3k -but the domains can be as large as |V (G)|. A reader experienced in W [1]-hardness reductions may notice at this point that the complexity of the permutation constraints is crucial: If one allows arbitrary permutation constraints (and constraints of the form (x ≤ a) ∨ (y ≥ b) for constants a, b and variables x, y, as in the encoding of the space of all minimum cuts), one can easily provide a W[1]-hardness reduction for the parameterization by the number of variables via the edge-choice gadgets (cf. [10] and Appendix A).
Here a recent major milestone in parameterized complexity comes into play: twin-width. Introduced by Bonnet, Kim, Thomassé, and Watrigant in 2020 [3], this structural complexity measure of graphs and, more generally, binary structures has turned out to explain and provide a number of fixed-parameter tractability results. Most importantly, a recent work from STOC 2022 [2] provides a fixed-parameter algorithm for FO model checking on ordered structures of bounded twin-width and provides a neat characterization under which conditions a 0-1 matrix gives bounded twin-width in the encoding.
In our case, the crucial notion is the one of a grid minor of a matrix. 1 Let A be a 0-1 matrix of dimension n × m. An × grid minor consists of two sequences of indices The value is often referred to as the size of the grid minor. One can deduce from the results of Bonnet et al. [2] the following statement: Our CSP formulation is FPT when parameterized by the number of variables, the number of permutation constraints, and the maximum size of a grid minor of the matrices of the permutation constraints. Hence, our task boils down to providing a bound on the size of a grid minor in our permutation constraints C(i, j, P, Q). 2 To this end and to complete our proof, we prove the following irrelevant-vertex rule: There exists an integer depending only on k such that if some constraint C(i, j, P, Q) has grid minor of size at least , then a vertex corresponding to a 1 in the "middle cell" of the grid minor (i.e., A[i, j] for i /2 −1 < i ≤ i /2 , j /2 −1 < j ≤ j /2 ) is irrelevant, that is, any so-called shadowless solution to the input Directed Multicut instance does not contain the said vertex. Hence, such a vertex can be reduced in a standard manner (and the analysis of the CSP formulation restarted).
The notion of a shadowless solution comes from the technique of shadow removal, pivotal for the fixed-parameter algorithms for Directed Multiway Cut [9] and Directed Subset Feedback Vertex Set [8]. In the context of Directed Multicut, a solution Z is shadowless if for every non-terminal vertex v / ∈ Z, the graph G − Z features a path from v to one of the terminals t i and a path from one of the terminals s j to v (note that necessarily the t-terminal and the s-terminal have distinct indices). In short, the shadow-removal technique [9,8] allows us to focus on the following task: Given a Directed Multicut instance (G, k, (s i , t i ) i=1,2,3 ), find any solution if there exists a shadowless solution (i.e., the algorithm is allowed to fail if there is a solution, but not a shadowless one). This last part of the proof -the irrelevant-vertex rule -is the only part of the proof that crucially relies on the fact that we are dealing with only three terminal pairs. In fact, it is inspired by the reduction for four terminal pairs [25] and our study why this reduction fails for three terminal pairs.
The irrelevant-vertex rule also requires us to look into the details of flow-augmentation (Theorem 1.2) and extract some extra properties of this tool. In short, we need to capture the following intuition: A sequence of deletable edges along the same flow path P ∈ P in the maximum flow P in G + A is in some sense sequentially positioned in the graph, so one can usually reach any later edge from an earlier one. This is not strictly true as stated above, but we prove a variant of this statement in Section 7.
One can ask if the proof of the irrelevant-vertex rule crucially needs the assumption of the solution being shadowless. In particular, the usage of shadow removal makes our algorithm inherently unweighted (the shadow-removal step involves a greedy argument that completely breaks down in the presence of weights). We complement our main result by proving (Section 8) that Weighted Directed Multicut is W[1]-hard even with two terminal pairs, so the shadow-removal step seems necessary. Theorem 1.3. Weighted Directed Multicut, parameterized by the cardinality of the cutset, is W[1]-hard even with two terminal pairs.
We remark that the one-terminal-pair case of Weighted Directed Multicut, or Biobjective st-cut, is proved to be FPT in [15] as one of the basic exemplary usages of flowaugmentation.
Since we rely on the whole meta-algorithmic toolbox of twin-width of [3], we cannot state an explicit dependency on the parameter in the running time bound of our algorithm. Relatedly, we would like to remark that the concept of encoding an instance at hand into a CSP instance with a number of variables that is bounded by a function of the parameter, but over large ordered domains, appeared also recently in the FPT algorithm for Optimal Discretization [16]. The encoding there also uses an unbounded number of constraints of the form (x ≤ a) ∨ (y ≥ b) and a bounded-in-parameter number of permutation constraints. However, the main effort in the proof in [16] lies in showing that the used permutation constraints have very simple structure (they are called in [16] segment reversions); in particular, one can observe that their permutation matrices do not contain a grid minor of size 3. As a result, in [16] the authors are able to design an explicit FPT algorithm for the obtained CSP instance (with an explicit single-exponential running time bound). Although using twin-width meta-algorithms prevents us from stating an explicit running time bound, it allows to claim fixed-parameter tractability of a much wider range of CSP instances: Permutations of bounded grid minor in their permutation matrices is a much wider class than the aforementioned segment reversions. We believe the presented framework of casting a problem into a small number of variables with unbounded ordered domains, bound by permutation constraints, and using twin-width toolbox to solve it, has a wider future potential in parameterized complexity.
Organization. After brief preliminaries, where in particular we state the shadow-removal tool and the extended version of flow-augmentation, we proceed to the main proof (of Theorem 1.1). Section 3 introduces the twin-width toolbox and shows fixed-parameter tractability of CSP instances with permutations only containing bounded grid minors. Section 4 contains the main proof, deferring the proof of the irrelevant-vertex rule to Section 5. Section 6 contains a (standard) proof of the used shadow-removal statement, while Section 7 contains a proof of the used extension of flow-augmentation. Finally, the proof of Theorem 1.3 can be found in Section 8.
Acknowledgements. The research leading to the results presented in this paper was partially carried out during the Parameterized Algorithms Retreat of the University of Warsaw, PARUW 2022, held in Będlewo in April 2022. We acknowledge insightful discussions with the twin-width experts at Będlewo: Édouard Bonnet, Jakub Gajarský, and Michał Pilipczuk, as well as later discussions with Szymon Toruńczyk.

Preliminaries
Let G be a directed graph. We use edge and arc interchangably for the directed edges of G. For two vertices u, v ∈ V (G), we say that u reaches v or v is reachable from u if there exists a directed path from u to v in G. A path starting in a vertex u and ending in a vertex v is also called a uv-path. Let e be a (directed) edge. Then s(e) (t(e)) is start (target) of e. Analogously, we use s(P ) (resp. t(P )) for first (resp. last) vertex of a path P . For s, t ∈ V (G), a set S ⊆ E(G) is an st-cut if t is not reachable from s in G−S and, similarly, a set S ⊆ V (G)\{s, t} is an st-separator if t is not reachable from s in G−S. In the latter, by G−S we denote the subgraph of G induced by V (G) \ S. Throughout the paper we use [k] as shorthand for the integer set {1, 2, . . . , k}.
In this work, an instance of Directed Multicut (3-DMC for short) is a tuple (G, k, (s i , t i ) i∈ [3] , V ∞ ) consisting of a directed graph G, six distinguished vertices s 1 , s 2 , s 3 , t 1 , t 2 , t 3 ∈ V (G), called terminals, an integer k, and a vertex subset V ∞ ⊆ V (G), called undeletable vertices. We sometimes denote the set of terminals as T = {s 1 , s 2 , s 3 , t 1 , t 2 , t 3 }. We require T ⊆ V ∞ . A solution is a set S of non-terminal vertices of G such that S ∩ V ∞ = ∅ and for every i = 1, 2, 3 the vertex t i is not reachable from the vertex s i in G − S. Directed Multicut asks for a solution of cardinality at most k.
For an instance (G, k, (s i , t i ) i=1,2,3 , V ∞ ) and a non-terminal vertex v, by bypassing v we mean the following operation. First, for every edge (u, v) ∈ E(G) and every edge (v, w) ∈ E(G), we add an edge (u, w) if it is not already present in the graph. Finally, we delete the vertex v. For a set X of nonterminal vertices, by bypassing X we mean bypassing vertices of X in arbitrary order; note that the result does not depend on the order. The following lemma is immediate and shows that bypassing is a good way to reduce vertices that are provably not in the sought solution.
Lemma 2.1 (Chitnis et al. [8], Lemma 3.11). Let G be a directed graph and let C ⊆ V (G). Let G be obtained from G after bypassing C and let S ⊆ V (G) \ C. For any a, b ∈ V (G) \ (C ∪ S), G − S has an ab-path if and only if G − S has an ab-path.
Shadows and shadow removal. Given an instance (G, k, (s i , t i ) i∈ [3] The set of vertices in the forward shadow of X in G, is denoted by f G (X) and the set of vertices in the reverse shadow of X in G, is denoted by r G (X).
The following statement encapsulates the shadow removal technique in the context of Directed Multicut. Though it follows directly from [9,8], we provide a formal proof in Section 6 for the sake of completeness.
Theorem 2.2. Given an instance (G, k, (s i , t i ) i∈ [3] , V ∞ ) of 3-DMC, there is an algorithm that runs in time 2 O(k 2 log k) n O(1) , and outputs a family Z of subsets of V (G) \ V ∞ such that |Z| = 2 O(k 2 log k) log 2 n and, if the input instance is a Yes-instance, then there exists Z ∈ Z such that (G , k, (s i , t i ) i∈ [3] , V ∞ \ Z) is a Yes-instance that admits a shadowless solution of cardinality at most k, where G is the result of bypassing Z in G.

Twin-width
Next, we state the definition of twin-width as introduced by Bonnet et al. [3]. They make use of the concept of a trigraph G, which consists of a vertex set V (G), and two disjoint edge sets, one containing black edges E(G) and the other containing red edges R(G). In particular, every graph G is a trigraph with only black edges and R(G) being empty. Let G be a trigraph. We say that we contract two vertices u, v ∈ V (G) if we merge them into a single vertex w, and then possibly color the edges incident to the new vertex w. Every existing edge wz remains black if and only if uz and vz were previously black edges. All other edges incident to w are colored in red. A contraction sequence of an n-vertex (tri)graph G is a sequence of trigraphs G = G n , . . . , G 1 = K 1 such that G i is obtained from G i+1 by contracting two vertices. A contraction sequence is called a d-sequence if all trigraphs in it have red degree at most d. The twin-width of G, denoted by tww(G), is the minimum integer d such that G admits a d-sequence.
Now we turn to matrices. Here, our main proxy to the twin-width are so-called rank-k divisions and the grid rank of the matrix which are closely related to twin-width graph parameter, see Bonnet et al. [2]. Let M be a 0-1 matrix. A division D of M is a pair (D R , D C ), where D R and D C are partitions of the rows and columns into intervals of consecutive rows and intervals of consecutive columns, respectively. A k-division is a division with such that each cell of D contains at least k distinct rows and at least k distinct columns, or, equivalently, has combinatorial rank at least k. The maximum integer k such that M admits a rank-k division is called the grid rank of M , denoted by gr(M ). A k-grid minor of M is a k-division D of M such that each cell of D contains at least one 1; note that any rank-k division of M for k ≥ 2 is necessarily a k-grid minor, too.
Let G be a graph and ≺ be a linear order on V (G). We denote by Adj ≺ (G) the adjacency matrix of G where rows and columns are ordered according to ≺. We use the following.  [2]). There is a computable function f : N → N such that the following hold. Let G be a graph.
• If tww(G) ≤ k, then there is a total order ≺ of V (G) such that gr(Adj ≺ (G)) ≤ f (k).
Lemma 2.4 (Bonnet et al. [1]). There is a computable function f : N → N such that the following holds. Let V be a set of vertices, let ≺ be a linear order on V , and let G 1 and G 2 be two graphs on the vertex set V . If gr(Adj ≺ (G i )) ≤ k for all i ∈ [2], then gr(Adj ≺ (G 1 ∪ G 2 )) ≤ f (k).
The following theorem can be deduced from the arguments of [3], but is not stated there explicitly; for completeness, we provide a proof in Appendix B.
Theorem 2.5. There is a computable function f with f (k) = 2 O(k log k) such that the following holds. There is an algorithm that, given a 0-1 matrix A, in f (k)n O(1) time either • finds a k-grid minor in A, or • certifies that gr(A) ≤ f (k).

(Permutation) CSP
An instance of a constraint satisfaction problem (CSP) is a triple (X, D, C), where X = {x 1 , . . . , x n } is a set of variables, D = {D 1 , . . . , D n } a set of domains, and each C ∈ C a constraint. A constraint C is an a C -tuple (x a 1 , . . . , x a C ) of variables and a relation R(C) ⊆ D a 1 × . . . × D a C . A valuation α assigns to each x i a value α(x i ) ∈ D i . A constraint C ∈ C is satisfied by α if (α(x a 1 ), . . . , α(x a C )) ∈ R(C). Valuation α satisfies (X, D, C) if it satisfies all constraints.

6
Let (D 1 , ≤ 1 ) and (D 2 , ≤ 2 ) be finite totally ordered sets. We need two types of relations in D 1 × D 2 . A relation R ⊆ D 1 × D 2 is called downwards-closed if for every (x 1 , x 2 ) ∈ R and every x 1 ≤ 1 x 1 and x 2 ≤ 2 x 2 it holds that (x 1 , x 2 ) ∈ R. Let X 1 ⊆ D 1 and X 2 ⊆ D 2 with |X 1 | = |X 2 | and let π : X 1 → X 2 be a bijection. We refer to the relation {(x, π(x)) | x ∈ X 1 } as the permutation constraint π. We denote by Adj(π) the 0-1 matrix of dimension |D 1 | × |D 2 | associated with π as follows. The rows and columns one-to-one correspond to D 1 and D 2 , respectively, following the orders ≤ 1 and ≤ 2 . The entry associated with (x, y) ∈ D 1 × D 2 equals 1 if and only if x ∈ D 1 and y = π(x). We deal with CSPs of the following form.
Definition 2.6. A Twin-width-w Permutation CSP instance consists of variables x 1 , . . . , x k with domains (D 1 , ≤ 1 ), . . ., (D k , ≤ k ), where for all i ∈ [k], (D i , ≤ i ) is a totally ordered set, and each constraint is, for some i = j, either • a downwards-closed relation R ⊆ D i × D j , or • a permutation constraint π : X i → X j where X i ⊆ D i and X j ⊆ D j . Furthermore, for each permutation constraint π, we have that gr(Adj(π)) ≤ w.

Flow-augmentation
Because the shadow removal technique is much easier to phrase and use in the vertex-deletion regime, we need to adjust flow-augmentation [15] from edge deletions to vertex deletions. This is pretty straightforward via the standard reductions between edge-and vertex-deletion regimes in directed graphs. More importantly, we need to squeeze an extra connectivity property out of flow-augmentation, which we formalize below as soybeans. We present here only the necessary definitions and the main statement that is used in the algorithm; its proof is deferred to Section 7.
Let G be a directed graph with two distinguished vertices s, t ∈ V (G). The vertices of G are partitioned into deletable vertices and undeletable vertices; s and t are undeletable. A (vertexbased) st-flow is a collection of st-paths that do not share a deletable vertex; the number of paths is the value of the flow. We use λ G (s, t) for the maximum possible value of an st-flow; a flow of value λ G (s, t) is an st-maxflow. As a convention we say that, if G contains an st-path consisting of undeletable vertices only, then the flow containing such a path has value +∞ and λ G (s, t) = +∞.
A set Z of deletable vertices is an st-separation if there is no path from s to t in G − Z. An st-separation Z is minimal if no proper subset of Z is an st-separation and minimum (or st-mincut) if it has minimum possible cardinality. By Menger's theorem, if λ G (s, t) < +∞ then the size of every st-mincut is exactly λ G (s, t) and there are no st-separations if λ G (s, t) = +∞. We drop the subscript if the graph G is clear from the context.
We say that a set of arcs A ⊆ V (G) × V (G) is compatible with a minimal st-separation Z if the following holds: for every v ∈ V (G), there is a path from s to v in G − Z if and only if there is a path from s to v in A soybean in G is an unordered pair of walks that have the same starting vertex and the same ending vertex. We do not require the walks to be disjoint in any sense; in particular, a pair consisting of the same walk twice is always a soybean. Two soybeans P Q and P Q are vertex-disjoint if (V (P ) ∪ V (Q)) ∩ (V (P ) ∪ V (Q )) = ∅. For two sets of vertices or edges C, D ⊆ V (G) ∪ E(G), a soybean P Q is a CD-soybean if one walk of P Q contains an edge or a vertex of C and the other walk of P Q contains an edge or a vertex of D. For a path P and two disjoint sets C, D ⊆ V (P ) ∪ E(P ), we say that C and D are interlaced on P if |C| = |D| = q for some integer q, C can be enumerated as c 1 , . . . , c q , D can be enumerated as d 1 , . . . , d q , and the order of these vertices and edges along P is c 1 , d 1 , c 2 , d 2 , . . . , c q , d q .
Theorem 2.7. There exist computable functions c : N → N and q : N × N → N such that the following holds.
There exists a polynomial-time randomized algorithm that, given a directed graph G (with possibly some vertices marked as undeletable), vertices s, t ∈ V (G), and an integer k, returns an arc set A ⊆ V (G)×V (G) and an st-maxflowP in G+A such that for every minimal st-separator Z of size at most k, with probability 2 −O(k 4 log k) , the tuple (A,P) is compatible with Z.
Additionally, the algorithm returns a partition B of the deletable vertices of P ∈P V (P ) into at most c(k) sets such that for every P ∈P, every integer p ∈ N, every B ∈ B and every two disjoint sets C, D of size at least q(k, p), consisting of vertices of B ∩ V (P ) that are interlaced on P , the graph G contains a family of p pairwise vertex-disjoint CD-soybeans.
Finally, one can take c and q such that c(k) = 2 O(k 3 log k) and q(k, p) = 2 O(k 3 log(kp)) .

Permutation CSP with bounded twin-width
In this section we show the following.
Theorem 3.1. Twin-width-w Permutation CSP parameterized by the number of constraints plus w is fixed-parameter tractable.
Proof. We transform the given Twin-width-w Permutation CSP instance I into an ordered, vertex-and edge-colored graph G whose twin-width only depends on w and the number of constraints in I. We then give an FO-formula φ such that G |= φ if and only if I is satisfiable. We can then apply the FO model checking algorithm on (ordered) graphs that runs in FPT time when parameterized by the twin-width of the input graph plus the length of the formula [2,3]. We denote the variables of I by x 1 , . . . , x k , by R the set of downwards-closed constraints of I, and by Π the set of permutation constraints of I.
, we introduce into G a set V i of n i vertices, colored with color i and denoted (and ordered) as v i 1 , . . . , v i n i . We reuse the symbols "≤ i " to denote the ordering of the vertices in V i in the FO-formula. At the heart of our FOformula φ is an existential guess of one vertex per V i , and choosing v i j for j ∈ [n i ] corresponds to setting the variable x i to d i j . The vertex colors are [k], and encode membership in the V i 's. We assume we have predicates col(y) = i for a vertex variable y and i ∈ [k] that verify whether the vertex assigned to y has color i (which in turn means that y ∈ V i ). The existential guess is: Encoding the constraints in (G, φ). Next we add edges to the graph G and color them using the constraints R ∪ Π of I as colors, thus indicating why an edge was added to G. Similarly to above, we assume that we have predicates col(e) = C where C ∈ R ∪ Π, that verify whether the edge assigned to e has color C. Let R ∈ R be a downwards-closed constraint with Note that the edges with color R form a matching, and that they mark the "boundary" of the relation R, in the following sense.
We construct the following part of φ which checks this condition, and therefore is true if and only if R is satisfied under the value assignment to x 1 , . . . , x k corresponding to the choice of the vertices y 1 , . . . , y k .
Now, let π ∈ Π with π : X i → X j for some X i ⊆ D i and X j ⊆ D j be a permutation constraint. Then, for each d i a ∈ X i , we let d j b = π(d i a ), and add the edge v i a v j b colored π to G. Again, the 8 edges with color π form a matching. This finishes the construction of G, and the last building block of φ is as follows. It checks that whenever y i (resp. y j ) is incident with some edge colored π, that the other endpoint of that edge is chosen to be y j (resp. y i ). This part of the formula evaluates to true if and only if the permutation constraint π is satisfied under the corresponding choice of values for the variables of I.
We now obtain φ as The correctness of this transformation immediately follows from the description above: It remains to show that the twin-width of G is bounded by a function of w and the number of constraints in I. To do that, consider the order where each V i is ordered according to ≤ i ; denote this order by ≺. We want to show that gr(Adj ≺ (G)) ≤ h(w, |R ∪ Π|), for some computable function h, which implies a desired bound on the twin-width of G by Theorem 2.3. This can be done by repeated application of Lemma 2.4 over all edge colors of G. All permutation constraints have grid rank at most w by assumption, so it remains to show that the grid rank of downwards-closed constraints is bounded as well. Before we do so, we observe one minor technical detail. Claim 3.3. Let (V, ≺) be an ordered set of vertices and let X i and X j be disjoint consecutive subsets of V . Let G be a graph on the vertex set V that only has edges between X i and X j . For we may assume (up to renaming i and j) that every cell of D intersects M i,j . This implies that k 2 cells of D are entirely contained in M i,j . Since each such cell has combinatorial rank at least k + 2, this gives a rank-k division of M i,j .
Suppose for a contradiction that there is a rank-2 division of M i,j with row intervals (R 1 , R 2 ) and column intervals (C 1 , C 2 ). Since each cell of this division has combinatorial rank at least 2, we know that each such cell contains at least one 1. Let e 1 = u 1 v 1 be the edge corresponding to the 1 in R 1 ∩C 1 , and let e 2 = u 2 v 2 be the edge corresponding to the 1 in But then, u 1 < i u 2 and v 1 < j v 2 , which means that the above construction would not have added the edge e 1 with color R. This implies that gr(M i,j ) ≤ 1, so by Claim 3.3, gr(Adj ≺ (G R )) ≤ 3.
Proof. For each C ∈ R ∪ Π, let E C ⊆ E(G) denote the set of edges colored C, and let By the assumption of the theorem, and Claim 3.4, we have that gr(Adj ≺ (G C )) ≤ max{3, w} for all C. Since E is a partition of the edge set of G, we can repeatedly apply Lemma 2.4 to conclude that gr(Adj ≺ (G)) ≤ h (w, |R ∪ Π|) for some computable function h . Theorem 2.3 in turn implies that tww(G) ≤ h(w, |R ∪ Π|) for some computable function h.
We can now run the FO model checking algorithm [2,3] on (G, φ) and return the same answer. Note that by [2], we can compute a contraction sequence of G whose twin-width is bounded by a computable function of tww(G) in FPT time parameterized by tww(G), using the ordering ≺. Correctness follows from Claim 3.2, and by Claim 3.5 the twin-width of G only depends on w and the number of constraints s in I. It is clear that the length of φ can be upper bounded by a function of k and s, and since we can assume that k ≤ s, the length of φ can be upper bounded by a function of s alone. The algorithm of [2,3] is fixed-parameter tractable in tww(G) + |φ|, which in our application translates to an FPT-algorithm for Twin-width-w Permutation CSP parameterized by w + s, as desired.
We would like to remark that Theorem 3.1 generalizes the fixed-parameter tractability result of another type of CSP, called Forest CSP [16]. Moreover, if we drop the twin-width of the permutation constraints as part of the parameter, then the resulting Permutation CSP problem parameterized by the number of constraints is W[1]-hard (see Appendix A).

Three-terminal-pair Directed Multicut is fixed-parameter tractable
This section is dedicated to proving the main theorem of this paper: Theorem 1.1. Directed Multicut with three terminal pairs is fixed-parameter tractable when parameterized by the size of the cutset (with a randomized algorithm).
To prove Theorem 1.1, we show how to reduce 3-DMC to Permutation CSP such that the twin-width of each constraint is bounded by some function of the desired separator size k. One main ingredient in this reduction is the flow-augmentation technique explained in Section 2.3. The outline is as follows. We first perform flow-augmentation for each of the terminal pairs, giving us an augmented graph and a flow of value k for each terminal pair. If there is a solution S, then with large-enough probability S is preserved as a separator after the augmentation steps. The solution thus corresponds to a selection of vertices, one for each of the obtained flow paths. To obtain a reduction to Permutation CSP, the idea is then to introduce one variable x for each flow path P where the domain of x is the set of vertices on P . A set of straightforward constraints ensures that the vertices selected by the variables form a separator for each terminal pair. One crux with this approach is how to ensure that the variables introduced for flow paths between different terminal pairs select vertices in a consistent way. We note that, after trying all possibilities of the possible overlaps of selected vertices, the consistency requirement can be modelled as a permutation constraint, we also call these consistency constraints. In this way, we obtain an instance of Permutation CSP with O(k 2 ) constraints. However, as mentioned in Section 3, Permutation CSP in general is W[1]-hard with respect to the number of constraints. Thus, we need more work to obtain Theorem 1.1. We show how to ensure that the obtained constraints are simple, in the sense that they have low twin-width, crucially leveraging our improved version of flow-augmentation from Section 2.3. We then apply the algorithm from Section 3 for solving Permutation CSP instances of low twin-width.
For use in the remainder of the section, fix an instance (G, (s i , t i ) i∈ [3] , k) of 3-DMC. We show how to solve this instance in fixed-parameter time with large-enough probability. The algorithm is partitioned into four main steps; they are reflected in the structure of the remainder of this section, also see Figure 1 for an illustration. The first step is the shadow-removal technique, which ensures in fixed-parameter time that each vertex is reachable from some terminal and reaches some terminal. We crucially use this property when bounding the twin-width later on. The second step is using flow-augmentation and reducing to Permutation CSP.  step is to reduce the twin-width of the constraints in the Permutation CSP instance. Finally, we solve the Permutation CSP instance using the algorithm from Section 3.
Shadow removal. The first step in the algorithm is to remove vertices from the graph in order to ensure that if there is a solution, then there is also one without a shadow. Recall the definition of being shadowless from Section 2 and recall Theorem 2.2 which we restate for convenience below and prove in Section 6.
We apply the algorithm of Theorem 2.2, yielding the family Z. We then iterate over all instances of 3-DMC resulting from bypassing a set Z ∈ Z in the input graph G. For each such constructed instance we continue with the remainder of the algorithm as described below. For simplicity, we call the instance of the current iteration (G, k, (s i , t i ) i∈ [3] , V ∞ ). Note that, from now on, it is enough to find a shadowless solution. This is not immediately relevant, but we crucially use this property when bounding the twin-width later on.
Flow-augmentation and reduction to Permutation CSP. We continue with the reduction to Permutation CSP, however, without at first bounding the twin-width of all constraints. (Recall that the definition of Permutation CSP can be found in Section 2.2 as Definition 2.6.) Recall that (G, k, (s i , t i ) i∈ [3] , V ∞ ) is the instance of 3-DMC that we are working on. The reduction to Permutation CSP works as follows. For each terminal pair (s i , t i ), i ∈ [3], run the algorithm from Theorem 2.7 with input s = s i , t = t i , the graph G, and k. We obtain a triple and a partition B i of the deletable arcs on P i . For each P i let k i be its flow value and fix an arbitrary ordering P i 1 , P i 2 , . . . , P i k i of the paths in P i . Note that not necessarily k i ≤ k, but this is the case if A i is in a sense compatible with a solution, see the notion of safe augmentation below. Hence, at this point if for some i ∈ [3] we have k i > k we stop and return a failure symbol. Otherwise we continue and denote G i := G + A i .
In order to define a Permutation CSP instance, for each The ordering ≤ i j of D i j corresponds to a traversal of the path P i j from s i to t i and the ordering ≤ i j of D i j corresponds to a traversal of the path P i j from t i to s i . (Intuitively, x i j and x i j always choose the same vertex, but we need both orderings of their 11 domain in order to define downwards-closed constraints below.) Below we let X denote the set of variables x i j and X the set of variables x i j . As to the constraints, first, for each i ∈ [3] and j ∈ [k i ] we introduce a permutation con- Next, we define the constraints that ensure that for each i ∈ [3] the vertices selected by the variables form an s i t i -separator. For each i ∈ [3] and each pair of variables x i j ∈ X, x i j ∈ X introduce a constraint R i j,j ⊆ D i j × D i j as follows; refer to Figure 2 for an illustration. At first, (This means that u occurs before x on path P i j and v occurs after y on path P i j . Intuitively, no solution may choose x and y because Q bypasses the corresponding vertex set, showing it is not a separator. Note that the path Q may consist of a single edge and that one of its endpoints may be s i or t i .) This finishes the description of the constraint R i j,j . (Note that not necessarily R i j,j = R i j ,j .) Note that if (x, y) ∈ R i j,j and x ≤ j x and y ≤ j y then (x , y ) ∈ R i j,j : Otherwise, at the point where we have removed (x , y ) from R i j,j in the above construction, say due to some pair (u, v), we have u ≤ j x ≤ j x and v ≤ j y ≤ j y and thus we would have removed (x, y) as well, a contradiction. Thus, R i j,j is downwards-closed.
We add further constraints to the Permutation CSP instance below. But first we observe that already at this point, every solution to the 3-DMC instance (G, k, (s i , t i ) i∈ [3] , V ∞ ) induces a solution for the Permutation CSP instance and every solution to the Permutation CSP instance induces three separators between the three terminal pairs. Let C 1 denote the Permutation CSP instance constructed so far, that is, Observe that we can construct C 1 in polynomial time because the algorithm of Theorem 2.7 runs in polynomial time and the paths underlying the construction of R i j,j can be computed in polynomial time.
For proving the soundness of the algorithm, we need the following definition. Let S be a solution to (G, k, (s i , t i ) i∈ [3] , V ∞ ). Define the event safely augmented (wrt. S) as the intersection of the three events E i , i ∈ [3], that state that there exists a minimal s i t i -separator S i that is contained in S such that (A i , P i ) is compatible with S i . We also say that the S i are the witnesses to having safely augmented. Note that, if we have safely augmented, then the flow value k i of each P i is at most k. In order to prove soundness, we make use of the following two statements.
Lemma 4.1. Let S be an arbitrary fixed solution to (G, k, (s i , t i ) i∈ [3] , V ∞ ). Then with probability at least 2 −O(k 4 log k) we have safely augmented wrt. S.
, be a minimal s i t i separator (in G) contained in S. The three events E i are independent from each other. They each have probability lower bounded by the probability of the event that (A i , P i ) is compatible with S i . By Theorem 2.7 they thus each have probability at least 2 −O(k 4 log k) , which implies the desired bound.
as specified in the statement. Clearly the permutation constraints ρ i j are satisfied. Assume towards a contradiction that some downwards-closed constraint R i j,j is not satisfied. Thus, at some point in the construction of We construct an s i t i -path Q in G i by following P i j from s i to u, then adding Q, and finally following P i j from v to t i . Observe that V (Q ) ∩ S i = ∅. Since A i is compatible with S i , this implies that there is an s i t i -path in G, a contradiction to the fact that S i is an s i t i -separator.
In order to prove completeness, we need the following.
. . such that each segment is of maximal length with respect to not having an internal vertex of a path P i j , j ∈ [k i ]. That is, the endpoints of the segments are either s i , t i , or an internal vertex of a path P i j . Label each segment Q p by a label in {−, +} × {−, +} as follows. Let u, v be the first and the last vertex of Q p , respectively, and observe that one of them occurs as internal vertex on a path in P i . The first part of the label of Q p is − if u = s i or if u occurs on a path P i j before φ(x i j ); otherwise the first part of the label is +. The second part of the label is + if v = t i or if v occurs on a path P i j after φ(x i j ); otherwise the second part of the label is −. Note that, since Q is an s i t i -path, there is at least one segment with label (−, +), say segment Q p . Let u, v be the first and the last vertex of Q p , respectively. Without loss of generality, by symmetry, assume that u = s i , that is, u appears as internal vertex on a path in P i , say P i j . If v appears as 13 internal vertex on a path in P i then let P i j be that path; otherwise take P i j to be an arbitrary path in P i different from P i j . By construction of Q p , we have u ≤ i j φ(x i j ) and v ≤ i j φ(x i j ). But then, by construction of R i j,j we would have removed (φ(x i j ), φ(x i j )) from R i j,j due to the path Q p , a contradiction. Thus, indeed S i is an s i t i -separator in G i .
Next, we aim to add the consistency constraints between variables mentioned in the outline above. To this end, we iterate over all possibilities of variables being assigned to the same vertex. More precisely, we iterate over all of the 2 O(k log k) partitions X of the variable set X into at most k parts of size at most three such that no part contains two variables x i · , x i · with i = i . (Intuitively, these capture all possibilities because no two paths in P i share a vertex and thus no cluster of pairwise equal variables exceeds size three.) We call this the consistency iteration.
Next, for each pair of variables x i j , x i j in the same part in X , restrict their domains to the set of shared vertices of P i j and P i j , that is, replace both D i j and D i j by their intersection D i j ∩ D i j . Perform analogous restrictions to the domains of the variables x i j , x i j . Omit the thereby invalidated bindings from the constraints ρ i j and R i j,j . Finally, we introduce the permutation constraints enforcing the guessed consistency relation represented by X . For every pair of variables x i j , x i j contained in same part of X , we introduce the constraint π i,i j,j : D i j → D i j mapping each u ∈ D i j as π i,i j,j (u) = u ∈ D i j . This concludes the description of the reduction to Permutation CSP. Let C 2 denote the resulting Permutation CSP instance Note that iterating over all possibilities for X can be done in 2 O(k log k) time and thus constructing all the instances C 2 takes 2 O(k log k) · n O(1) time.
We can now extend Lemmas 4.2 and 4.3 to C 2 . To this end, let S be a solution to (G, k, (s i , t i ) i∈ [3] , V ∞ ) and assume we have safely augmented with witnesses S i . We say that X complies (with S and the witnesses S i ) if for each pair i, i ∈ [3], each j ∈ [k i ], and j ∈ [k i ] we have that j and x i j are both contained in the same part of X .
Lemma 4.4. Let S be a solution to (G, k, (s i , t i ) i∈ [3] , V ∞ ) and assume we have safely augmented with witnesses S i . Then, one of the partitions considered in the consistency iteration complies.
Proof. Since we have safely augmented and by Lemma 4.2, we have |V (P i j ) ∩ S i | = 1 for each i ∈ [3] and for each j ∈ [k i ]. For every vertex v ∈ S define a set of variables To see that X is considered in the consistency iteration observe that |X | ≤ k. Furthermore, for each i ∈ [3] there are no two variables x i j , x i j in the same part in X , which proves the claim.
Lemma 4.5. Let S be a solution to (G, k, (s i , t i ) i∈ [3] , V ∞ ), assume we have safely augmented with witnesses S i and assume that X complies. Then, we have |V (P i j ) ∩ S i | = 1 for each i ∈ [3] and for each j ∈ [k i ]. Define the mapping φ by defining φ(x i j ) and φ(x i j ) both as the single vertex in V (P i j ) ∩ S i for every i ∈ [3] and j ∈ [k i ]. Then, φ is a solution to the Permutation CSP instance C 2 .
Proof. By Lemma 4.2, |V (P i j ) ∩ S i | = 1 and the mapping φ satisfies all constraints ρ i j and R i j,j . It remains to show that the values of φ have not been removed from the domains and that the permutation constraints π i,i j,j are satisfied. For the claim about the domains, fix some variable x i j . Towards a contradiction, assume that φ(x i j ) was removed in the domain-restriction step. Then, there is some other variable x i j that is in the same part of X such that φ(x i j ) / ∈ D i j . In other words, V (P i j ) ∩ S i = V (P i j ) ∩ S i . Since X complies, x i j and x i j are in different parts in X , a contradiction. In order to show that the permutation constraints are satisfied, fix some constraint π i,i j,j . By construction of π i,i j,j , variables x i j and x i j are in the same part of X . Since X complies, Finally, we prove that solutions to C 2 yield solutions to our 3-DMC instance.
In comparison to C 1 , instance C 2 contains only smaller domains and more constraints. Thus, the conclusion of Lemma 4.3 still holds for C 2 . Hence, each S i is an s i t i -separator in G. Thus it remains to show that |S| ≤ k. For this, observe that, due to the constraints π i,i j,j , we have that for each part Y ∈ X all the variables in Y have the same value. Since |X | ≤ k by construction of X it follows that |S| ≤ k, as required.
We now continue working with C 2 ; first reducing the twin-width of its constraints and then applying the algorithm from Section 3.
Twin-width reduction by irrelevant vertices. We next show how to bound the twinwidth of the constraints in C 2 . First, observe that the twin-width of the constraints ρ i j is already bounded. Recall the definition of grid rank gr from Section 3. Proof. Let M = Adj(ρ i j ). Observe that M is an anti-diagonal matrix. Each cell of M with at least two distinct rows or columns thus contains an entry of the anti-diagonal. Consider the upper-left cell C in a rank-k division of M . For a contradiction, assume that k ≥ 2. Then, C contains an entry of the anti-diagonal. Consider the cell C that is south east of C. Cell C contains only zero entries, a contradiction.
The crucial constraints are the constraints π i,i j,j and they are indeed a priori not of bounded twin-width. However, using an irrelevant vertex argument, we can bound their twin-width.
, and j ∈ [k i ] and the augmented paths P i j , P i j together with the partitions B i and B i (from Theorem 2.7), certifies that gr(Adj(π i,i j,j )) ≤ h(k) or finds a vertex v ∈ D i j ∩ D i j such that there is no shadowless solution S with v ∈ S and: • all vertices before v on P i j do not reach t i and all vertices after v on P i j are not reachable from s i in G − S; • all vertices before v on P i j do not reach t i and all vertices after v on P i j are not reachable from s i in G − S. Moreover, the algorithm runs in fixed-parameter time with respect to k.
The proof is given in Section 5. Note that if the instance is safely augmented and X complies with S, then P i j contains a unique vertex of S i , P i j contains a unique vertex of S i , and this is the same vertex. Lemma 4.8 returns v that is guaranteed not to be the said vertex, so we can remove it from the domains of the variables corresponding to P i j and P i j . Formally, we use Lemma 4.8 as follows. We iterate over all consistency constraints. That is, for each i, i ∈ [3], j ∈ [k i ], and j ∈ [k i ], we consider the constraint π i,i j,j in C 2 . We iteratively apply the algorithm of Lemma 4.8 to it. If it returns a vertex v, then we remove v from both the domains D i j and D i j of x i j and x i j , and repeat. If it returns that the grid rank is at most h(k), we continue to the next constraint. Since we may drop at most n vertices from a domain, this eventually leads to an empty domain for a variable, that is, a no-instance, or a situation in which for every constraint π i,i j,j in C 2 the matrix has grid rank bounded by h(k). In the latter case, we apply Theorem 3.1 to solve C 2 in fixed-parameter time with respect to k.
We are now able to prove Theorem 1.1. Proof. We claim that the algorithm described in this section solves (G, k, (s i , t i ) i∈ [3] , V ∞ ) in fixed-parameter time with respect to k with large-enough probability. By the arguments given throughout the section, the algorithm indeed runs in fixed-parameter time. If the algorithm returns a vertex set S, then S is a solution to (G, k, (s i , t i ) i∈ [3] , V ∞ ) by Lemma 4.6. Assume now that there is a solution S to (G, k, (s i , t i ) i∈ [3] , V ∞ ). By Theorem 2.2, we may assume that S is shadowless. By Lemma 4.1, with probability at least 2 −O(k 4 log k) the algorithm safely augmented with respect to S. By Lemma 4.4, one of the considered X complies with S. Thus, by Lemma 4.6, the Permutation CSP instance C 2 has a solution. By Lemma 4.8, C 2 maintains having a solution even after removing the vertices computed in Lemma 4.8 from the respective domains. Thus, the algorithm of Theorem 3.1 returns a solution, as required.

Irrelevant vertex rule-Proof of Lemma 4.8
In this section, we give a tool that reduces the complexity of complicated permutation constraints in C 2 . In fact, we argue that due to the shadow removal (as described in Section 6) and an improved version of the flow augmentation (Theorem 7.2), we obtain the following. If the permutation constraint has a high grid rank (gr), then we can explicitly find a vertex v that cannot play the role of the solution vertex in the given permutation constraint.
First, we provide some very brief intuition. Shadow removal grants us some additional information about the reachability relation with respect to the terminals: For example, if some vertex cannot be reached from s 1 and s 2 after removal of a shadowless solution S, then it must be reachable from s 3 . Symmetrically, if a vertex cannot reach t 1 and t 2 , it has to reach t 3 . Using the large grid rank, this additional reachability can be easily extended first along flow path P i j and then along flow path P i j , which gives a forbidden path s 3 t 3 -path. However, this does not prove the existence of such an s 3 t 3 -path in the original graph, as the flow paths might contain augmented edges. Therefore, we make use of the improved flow augmentation (Theorem 7.2) in order to still reach a contradiction. In particular, if S satisfies the additional assumption stated in Lemma 4.8 (which still follows from the flow augmentation), the soybeans (introduced in Section 2.3) provide the needed connectivity without using the augmented edges. Unfortunately, their structure is (and has to be; see Section 7) a bit more complicated than just a simple path, but using additional shadow removal arguments, we are able to derive the existence of an s 3 t 3path and therefore, the desired contradiction.
Note one more complication: The soybeans may use vertices in other flow paths, but as they are vertex disjoint, at most k of them can intersect S, so if we set the threshold high enough, we still reach the contradiction. Lemma 4.8. There exists a computable function h : N → N and an algorithm that, given an instance (G, k, (s i , t i ) i∈ [3] , V ∞ ), the constraint π i,i j,j in C 2 for i, i ∈ [3] distinct, j ∈ [k i ], and j ∈ [k i ] and the augmented paths P i j , P i j together with the partitions B i and B i (from Theorem 2.7), certifies that gr(Adj(π i,i j,j )) ≤ h(k) or finds a vertex v ∈ D i j ∩ D i j such that there is no shadowless solution S with v ∈ S and: • all vertices before v on P i j do not reach t i and all vertices after v on P i j are not reachable from s i in G − S; • all vertices before v on P i j do not reach t i and all vertices after v on P i j are not reachable from s i in G − S. Moreover, the algorithm runs in fixed-parameter time with respect to k.
Proof. For simplicity, denote P j = P i j and P j = P i j . Without loss of generality suppose that i = 1 and i = 2.
For a (sub)matrix A of Adj(π 1,2 j,j ), we refer to the vertices that correspond to domains of A as the vertices corresponding to A. Note that whenever there is a 1 in the (sub)matrix A, it means that the corresponding two domain values are, in fact, the same vertex in G.
Recall functions c and q of Theorem 2.7. We set ζ := 2q(k, q(k, k + 1) + 1 + k) + 1. Let ρ be the bipartite Ramsey number for (c(k)) 2 colors and a monochromatic biclique of size 2ζ; that is, every edge coloring of K ρ,ρ with (c(k)) 2 colors contains a monochromatic copy of K 2ζ,2ζ . We apply Theorem 2.5 to Adj(π 1,2 j,j ) and ρ to either obtain that gr(Adj(π 1,2 j,j )) is bounded by 2 O(ρ log ρ) (and a computable function of k), or obtain an ρ-division of Adj(π 1,2 j,j ) that has at least one 1 in every cell. In the first case, we return that gr(Adj(π 1,2 j,j )) is bounded by a computable function of k, in the second case we proceed further; we leverage the obtained ρ-division to obtain the desired irrelevant vertex v.
We fix one such entry with value 1 for every (p, q)-cell of the said division, which corresponds to a vertex, and call it the (p, q)-representative. For every cell (p, q), we color it with a pair (B 1 , B 2 ), where for ι = 1, 2 the set B ι ∈ B ι is the set containing the (p, q)-representative in the application of Theorem 2.7 for the pair s ι , t ι . Clearly, there are at most (c(k)) 2 colors. By the choice of ρ, there is a coarser 2ζ-division of Adj(π 1,2 j,j ) such that we can choose a representative in every cell of this division such that all representatives are of the same color (B 1 , B 2 ). In what follows, we only work with the latter division and representatives and hence use the name (p, q)-representative for them. For a (sub)matrix A of Adj(π 1,2 j,j ), we say representatives for the set of all (p, q)-representatives within A.
We choose v as the (ζ, ζ)-representative. Now, towards a contradiction, suppose that v ∈ S and v splits P j and P j as in the lemma statement.
This split in particular applies to the representatives. The first part of P j (resp. P j ) contains the vertices not reaching t 1 (resp. t 2 ) up to the cell index i = ζ −1 (resp. j = ζ −1) and the second part contains vertices not reachable from s 1 (resp. s 2 ) in G − S. Based on the above, we split the cells of the matrix Adj(π 1,2 j,j ) into four quadrants and take submatrices consisting only of their representatives: A t12 , A t1s2 , A t2s1 , and A s12 , where the subscript indicates the non-reachability of the quadrant. More formally, A t12 consists of the (p, q)-representatives for 1 ≤ p, q ≤ ζ −1 (and they do not reach t 1 nor t 2 in G − S), A t1s2 consists of the (p, q)-representatives for 1 ≤ p ≤ ζ − 1 and ζ + 1 ≤ q ≤ 2ζ (and they do not reach t 1 and are not reachable from s 2 in G − S), A t2s1 consists of the (p, q)-representatives for 1 ≤ q ≤ ζ − 1 and ζ + 1 ≤ p ≤ 2ζ (and they do not reach t 2 and are not reachable from s 1 in G − S), and finally A s12 consists of the (p, q)-representatives for ζ + 1 ≤ p, q ≤ 2ζ (and they are not reachable from s 1 nor s 2 in G − S).
As S is shadowless thus all vertices in A t12 have to reach t 3 and all vertices in A s12 have to be reachable from s 3 in G − S. In order to make use of the soybeans given by the flowaugmentation (Theorem 2.7) we need to define suitable interlaced sets. Let ξ o be the vertices of P j corresponding to (p, q)-representatives of A s12 for every odd p ≥ ζ + 1 and any one fixed q ≥ ζ + 1, and let ξ e be the set of vertices of P j corresponding to (p, q)-representatives of A t1s2 for every even p ≥ ζ + 1 and q := p − ζ. It follows that ξ o and ξ e form interlaced sets on path P j of size ζ/2 = (2q(k, q(k, k + 1) + 1 + k) + 1)/2 ≥ q(k, q(k, k + 1) + 1 + k).
Hence we obtain q(k, k + 1) + 1 + k ξ o , ξ e -soybeans by Theorem 2.7 (note that the interlaced sets are within one set B 2 ∈ B 2 ). Let Q 1 Q 2 be one of these ξ o ξ e -soybean that does not intersect S. Pick two vertices v 1 ∈ ξ o and v 2 ∈ ξ e . As v 1 corresponds to a vertex of A s12 , vertex v 1 is not reachable from s 1 and s 2 in G − S. As Q 1 Q 2 is disjoint with the solution S, s( For an illustration, consider the left part of Figure 3. Some of the ξ o , ξ e -soybeans may intersect S, but as they are pairwise vertex disjoint, at most k of them can. Hence, the above properties hold for q(k, k + 1) + 1 of them. We restrict the submatrix A t1s2 only to entries in ξ e that correspond to ξ o , ξ e -soybeans that are disjoint from S. We call the resulting submatrix A t1s2 . Observe that A t1s2 has at least q(k, k + 1) + 1 columns with at least one 1. Now, we construct another pair of interlaced sets. Let χ 1 be the set of vertices that are contained in ξ e and that correspond to the soybeans selected in the previous step (i.e., to the representatives in A t1s2 , except for the last one on the path P j ). Note that by our previous construction, for (p, q)-representatives in χ 1 , all values of q are pairwise different and of the same parity. For every (p, q)-representative in χ 1 , we insert into χ 2 a (p , q )-representative of A t12 for q = q + 1 and any fixed p ≤ ζ − 1. It follows that χ 1 , χ 2 are interlaced sets on path P j of size q(k, k +1), and they are within the same set B 1 ∈ B 1 . (We removed the last representative in χ 1 as it could be the in the (p, ζ − 2)-cell of Adj(π 1,2 j,j ) for some p ≥ ζ + 1.) Hence we obtain k + 1 vertex-disjoint χ 1 , χ 2 -soybeans by Theorem 2.7. At most k of them can intersect S. Therefore let Q 3 Q 4 be one χ 1 , χ 2 -soybean that does not. We know that v 3 ∈ Q 3 ∩ χ 1 is reachable by s 3 in G − S by the arguments in the previous paragraph.
We know that v 4 ∈ Q 4 ∩ A t12 does not reach t 1 nor t 2 in G − S. Hence, t(Q 3 Q 4 ) does not reach t 1 nor t 2 . Since S is shadowless, t(Q 3 Q 4 ) reaches t 3 in G − S. Since Q 3 Q 4 is disjoint with the solution, v 3 reaches t 3 in G − S. This is the desired contradiction, see the right part of Figure 3 for this case.

Shadow removal
In this section, we prove Theorem 2.2. Recall that (G, k, (s i , t i ) i∈ [3]  To prove Theorem 2.2, we use the tool of random sampling of important separators from [24,9,8], presented in its derandomized form and in the form that is convenient for us to use, as Proposition 6.1. Proposition 6.1 (Theorem 3.18 by Chitnis et al. [8]). Given an instance (G, k, (s i , t i ) i∈ [3] , V ∞ ), there is a deterministic algorithm that runs in time 2 O(k 2 ) · n O(1) and outputs a family Z ⊆ 2 V (G)\V ∞ of size 2 O(k 2 ) log n such that the following holds. Let W ⊆ V (G) be a thin set of size at most k and let Y ⊆ V (G) such that for each v ∈ Y , there is an important (v, T )-separator W ⊆ W . For every such pair (W, Y ), there exists Z ∈ Z such that Z ∩ W = ∅ and Y ⊆ Z.
Connects s 3 and The idea is to use Proposition 6.1 to find a family of sets such that at least one of the sets in this collection contains the reverse and forward shadow of some solution, but does not contain the corresponding solution. We apply Proposition 6.1 in two steps: first to cover the reverse shadow of a solution and then to also cover its forward shadow. To apply Proposition 6.1 where the set W corresponds to some solution and the set Y corresponds to the reverse shadow of W , one needs to guarantee that there is a solution W and its reverse shadow Y that satisfies the properties of Proposition 6.1. In order to prove this, we define shadow-maximal solutions (as in [9,8]). Definition 6.2 (Shadow-maximal solution). Let I = (G, k, (s i , t i ) i∈ [3] , V ∞ ) be an instance of 3-DMC. An inclusion-wise minimal solution S for I is called a shadow-maximal solution if r G (S) ∪ f G (S) ∪ S is inclusion-wise maximal among all minimal solutions S.
A shadow-maximal solution S is called a best shadow-maximal solution, if it is shadowmaximal and amongst all shadow-maximal solutions |r G (S)| is maximum.
We now show in Lemmas 6.3 and 6.4 that if W is a best shadow-maximal solution and Y = r G (W ), then W and Y satisfy the properties of Proposition 6.1. Lemma 6.3. Every minimal solution of the instance (G, k, (s i , t i ) i∈ [3] , V ∞ ) of 3-DMC is thin.
Proof. Let W be a minimal solution of the instance (G, k, (s i , t i ) i∈ [3] , V ∞ ). We show that if v ∈ W and v ∈ r G (W ) for some W ⊆ W , then W \v is also a solution for (G, k, (s i , t i ) i∈ [3] , V ∞ ), contradicting the minimality of W . Towards this, if W \ v is not a solution, then there exists an Since v ∈ r G (W ), P must contain a vertex of W ⊆ W \ v, which yields a contradiction. [3] , V ∞ ) be an instance of 3-DMC and let S be a shadowmaximal solution. Then, either for every v ∈ r G (S), there exists S v ⊆ S such that S v is a (v, {t 1 , t 2 , t 3 })-important separator, or there exists another shadow-maximal solution S such that r G (S) ⊂ r G (S ).
and r G (S) ⊂ r G (S ), which proves the lemma.
Now suppose, for the sake of contradiction, that x ∈ r G (S) but x ∈ r G (S ). Consider an (x, {t 1 , t 2 , t 3 })-path P in G − S . Then there exists y ∈ V (P ) such that y ∈ S \ S . From the claim in the previous paragraph, y ∈ r G (S ). Thus, there exists a vertex of S on the (y, {t 1 , t 2 , t 3 })-subpath of P , which is a contradiction. From Claim 6.5 and since |S \ S | ≥ 1, r G (S) ⊂ r G (S ). We now show that S is a solution for the instance (G, k, (s i , t i ) i∈ [3] , V ∞ ). Claim 6.6. S is a solution for the instance (G, k, (s i , t i ) i∈ [3] , V ∞ ) of 3-DMC.
Proof. For the sake of contradiction, say S is not a solution. Then there exists an s i t i -path in G − S that uses a vertex x ∈ S v \ S v . In particular, there exists an xt i -path in G − S , that is x ∈ r G (S ). Since S v \ S v = S \ S , from Claim 6.5, x ∈ r G (S ). This is a contradiction.
Proof. From Claim 6.5, (r G (S)∪S) ⊆ (r G (S )∩S ). We now show that for any v ∈ f G (S)\r G (S), v ∈ f(S ) ∪ r G (S ). Suppose not. Then there exists an s i v-path, say P 1 , and a vt j -path, say Since v ∈ f G (S), the path P 1 contains a vertex x ∈ S \ S . From Claim 6.5, x ∈ r G (S ). But the xv-subpath of P 1 , together with the vt j -path P 2 gives an xt j -path in G − S , which is a contradiction because x ∈ r G (S ).
From Claims 6.5 and 6.6 and since |S \ S | ≥ 1, we have shown that S has the properties stated earlier, which contradict that S is a best shadow-maximal solution.
The following lemma, uses Lemmas 6.3 and 6.4 to show that appropriate applications of Proposition 6.1 result in a family of sets that cover the shadow of some solution.

Lemma 6.8 (Covering the shadow). There is an algorithm that given an instance
Proof. Let X be the family returned by the algorithm of Proposition 6.1 on the instance I. Suppose I is a Yes-instance. Fix a best shadow-maximal solution S * of I. From Lemmas 6.3 and 6.4 follows that the pair of sets (W, Y ) = (S * , r G (S * ) satisfies the properties of the sets in Proposition 6.1 on input I. Thus, there exists Z r ∈ X such that Z r ∩ S * = ∅ and r G (S * ) ⊆ Z r .
Let G be the graph obtained from G after reversing all the edges of G. For each Z ∈ X , create an instance I Z = ( G, k, (t i , s i ) i∈ [3] Let Y Z be the family returned by the algorithm of Proposition 6.1 on input I Z . Then output the family Z = {{Z 1 ∪ Z 2 } : Z 1 ∈ X , Z 2 ∈ Y Z 1 }. We now show that Z is the desired family. The size bound and the running time follow from Proposition 6.1.
Observe that S * is also a solution for I Z r . Further observe that for any set S ⊆ V (G), the forward shadow of S in G, with respect to {s 1 , s 2 , s 3 } is equal to the reverse shadow of S in G with respect to {t 1 , t 2 , t 3 }, and the reverse shadow of S in G, with respect to {t 1 , t 2 , t 3 } is equal to the forward shadow of S in G with respect to {s 1 , s 2 , s 3 }. That is, r G (S) = f G (S) and f G (S) = r G (S). In particular, S * is a shadow-maximal solution of I Z r . We now want to show that the pair (W, Y ) = (S * , r G (S * )) satisfies the properties of Proposition 6.1 on input I Z r . Towards this we prove the following claim.
Proof. Suppose the claim does not hold. Then, by Lemma 6.4, there exists a shadow-maximal solution S of I Z r such that r G (S * ) ⊂ r G (S ). Since S * is also a shadow-maximal solution of I Z r , we conclude that (r G (S * ) ∪ f G (S * ) ∪ S * ) = (r G (S ) ∪ f G (S ) ∪ S ). In particular, S \ S * ⊆ (r G (S * ) ∪ f G (S * ) ∪ S * ). That is, for any v ∈ S * \ S , either v ∈ r G (S * ) or v ∈ f G (S * ).
Since f G (S * ) = r G (S * ) ⊆ Z r ⊆ V ∞ Z r and S * is a solution of I Z r , S * ∩ f G (S * ) = ∅. If v ∈ r G (S * ), then, since r G (S * ) ⊂ r G (S ), v ∈ r G (S ). This is a contradiction as v ∈ S \ S * .
Thus from Claim 6.9 and Lemma 6.3 follows that the pair (W, Y ) = (S * , r G (S * )) satisfies the properties of Proposition 6.1 on input I Z r . Thus, there exists Z f ∈ Y Z r such that Z f ∩ S * = ∅ and f G (S * ) ⊆ Z f . Let Z * = Z r ∪ Z f . Then from the above arguments Z * ∩ S * = ∅ and (r G (S * ) ∪ f G (S * )) ⊆ Z * . Also Z * ∈ Z.
Finally we use Lemma 6.8 to prove Theorem 2.2.
Theorem 2.2. Given an instance (G, k, (s i , t i ) i∈ [3] , V ∞ ) of 3-DMC, there is an algorithm that runs in time 2 O(k 2 log k) n O(1) , and outputs a family Z of subsets of V (G) \ V ∞ such that |Z| = 2 O(k 2 log k) log 2 n and, if the input instance is a Yes-instance, then there exists Z ∈ Z such that (G , k, (s i , t i ) i∈ [3] , V ∞ \ Z) is a Yes-instance that admits a shadowless solution of cardinality at most k, where G is the result of bypassing Z in G.
Proof. Given an instance (G, k, (s i , t i ) i∈ [3],V ∞ ), let Z be the collection returned by Lemma 6.8. From Lemma 6.8, if I is a Yes-instance, then there exists a solution S and Z ∈ Z such that Z ∩ S = ∅ and (r G (S) ∪ f G (S)) ⊆ Z. Let G be obtained from G by bypassing Z. From Lemma 2.1, S is also a solution of (G , k, (s i , t i ) i∈ [3] , V ∞ \ Z). We now show that is S is a shadowless solution of (G , k, (s i , t i ) i∈ [3],V ∞ ), that is r G (S) = f G (S) = ∅. For the sake of contradiction, say r G (S) = ∅. Let x ∈ r G (S). In particular, x ∈ V (G ) = V (G) \ Z. Since x ∈ r G (S), G − S has no (x, {t 1 , t 2 , t 3 })-path. From Lemma 2.1, G − S also has no (x, {t 1 , t 2 , t 3 })-path, which implies that x ∈ r G (S). This is a contradiction, since then x ∈ Z and hence x ∈ V (G ).

Harvesting soybeans
This section is devoted to the proof of Theorem 2.7. The proof revisits the whole proof of flowaugmentation of [15] (recalled below as Theorem 7.1) and extracts the additional information along the way. Furthermore, we need to slightly revise the behavior of the algorithm in the base case to ensure the desired properties. This section assumes that the reader is familiar with the proof of Theorem 7.1 from [15].

Back to the edge-deletion regime
Since flow-augmentation in [15] is defined on edge-cuts, but Theorem 2.7 is in the vertex-deletion regime, we first go back to the edge-deletion regime. We need a few more definitions that closely follow [15].
In the edge-deletion regime, the edges of G can be deletable or undeletable. An (edge-based) st-flow, in this context, is a collection of st-paths that do not share a deletable edge and an st-cut is a set of deletable edges that intersects all st-paths. It is always clear from the context whether we speak about the vertex-or the edge-deletion regime, and hence we reuse names like st-flow or st-mincut or the notation λ G (s, t) for both regimes.
An st-cut Z is a star st-cut if for every (u, v) ∈ Z in the graph G − Z there is a path from s to u but there is no path from s to v; observe that every minimal st-cut is a star st-cut. For a star st-cut Z in G, by core G (Z) ⊆ Z we denote the set of arcs (u, v) ∈ Z such that there exists a path from v to t in G − Z.
Being compatible is slightly more complicated for star cuts: a set of arcs A ⊆ V (G) × V (G) is compatible with a star st-cut Z if the set of vertices reachable from s in G − Z and (G + A) − Z is the same. We also need the notion of a witnessing flow: for a star st-cut Z in G, if core(Z) is an st-mincut, then an st-maxflow P is a witnessing flow if E(P) ∩ Z = core(Z). The pair (A, P) is compatible with Z if A is compatible with Z, core G+A (Z) is an st-mincut in G + A, and P is a witnessing flow for Z in G + A. Note that if Z is a minimal st-cut, and A is compatible with Z, then any st-maxflow in G + A is a witnessing flow for Z, but if Z is a star st-cut, the notion of a witnessing flow is more intricate.
The flow-augmentation technique is represented by the following statement.
Theorem 7.1 (Kim et al. [15]). There exists a polynomial-time algorithm that, given a directed graph G, vertices s, t ∈ V (G), and an integer k, returns a set A ⊆ V (G) × V (G) and an st-maxflow P in G + A such that for every star st-cut Z of size at most k, with probability 2 −O(k 4 log k) the pair (A, P) is compatible with Z.
Most of this section is devoted to the proof of the following edge-deletion variant of Theorem 2.7.
Theorem 7.2. There exist computable functions c : N → N and q : N × N → N such that the following holds.
There exists a polynomial-time randomized algorithm that, given a directed graph G, vertices s, t ∈ V (G), and an integer k, returns a set A ⊆ V (G) × V (G) and an st-maxflowP in G + A such that for every star st-cut Z of size at most k, with probability 2 −O(k 4 log k) , the pair (A,P) is compatible with Z.
Additionally, the algorithm returns a partition B of the deletable edges of P ∈P E(P ) into at most c(k) sets such that for every P ∈P, every integer p ∈ N, every B ∈ B and every two disjoint sets C, D of size at least q(k, p), consisting of edges of B ∩ E(P ) that are interlaced on P , the graph G contains a family of p pairwise vertex-disjoint CD-soybeans.
Finally, one can take c and q such that c(k) = 2 O(k 3 log k) and q(k, p) = 2 O(k 3 log(kp)) .
Observe that if P ∩ A = ∅, that is, P does not contain any augmentation edge, then one can simply enumerate C = {c 1 , . . . , c q } and D = {d 1 , . . . , d q } for q = q(k, p) along the path P , define P i to be the subpath of P from c i to d i , and use soybeans {P 2i P 2i | 1 ≤ i ≤ q/2}. (We skip every second such soybean in order to make them vertex-disjoint.) However, when P contains augmentation edges, the situation is more complex, as a soybean cannot use them.
We now formally show that Theorem 7.2 implies Theorem 2.7, restated below: Theorem 2.7. There exist computable functions c : N → N and q : N × N → N such that the following holds. There exists a polynomial-time randomized algorithm that, given a directed graph G (with possibly some vertices marked as undeletable), vertices s, t ∈ V (G), and an integer k, returns an arc set A ⊆ V (G)×V (G) and an st-maxflowP in G+A such that for every minimal st-separator Z of size at most k, with probability 2 −O(k 4 log k) , the tuple (A,P) is compatible with Z.
Additionally, the algorithm returns a partition B of the deletable vertices of P ∈P V (P ) into at most c(k) sets such that for every P ∈P, every integer p ∈ N, every B ∈ B and every two disjoint sets C, D of size at least q(k, p), consisting of vertices of B ∩ V (P ) that are interlaced on P , the graph G contains a family of p pairwise vertex-disjoint CD-soybeans.
Finally, one can take c and q such that c(k) = 2 O(k 3 log k) and q(k, p) = 2 O(k 3 log(kp)) .
Proof. We construct a new graph G as follows. For each vertex v ∈ V (G), graph G contains two vertices v 1 and v 2 and a deletable arc (v 1 , v 2 ); we call these arcs important. If v is undeletable or if v = s or v = t, then the arc (v 1 , v 2 ) is undeletable instead. For each arc (u, v) ∈ A(G), graph G contains an undeletable arc (u 2 , v 1 ). We apply Theorem 7.2 to G , s 2 , t 1 , and k, obtaining an arc set A , an edge-based s 2 t 1maxflow P in G + A , and a partition B of deletable arcs of P .
We now perform the following cleanup step of A and P . First, for every x, y ∈ V (G ) such there is a path from x to y in G + A that uses undeletable arcs only (recall that every arc of A is considered undeletable), we add an undeletable arc (x, y) to A if it is not present already in G + A . Second, for every P ∈ P and every maximal subpath Q of P that uses undeletable arcs only and is of length at least 2, we replace Q with only an arc (s(Q), t(Q)) (which is now in G + A due to the previous step). Finally, we restrict A to contain only arcs that are present on some flow path in P .
Observe that the first step does not change the space of s 2 t 1 -cuts in G + A (as any newly added arc (x, y) cannot lead from the s-side to the t-side of any s 2 t 1 -cut in G + A due to the assumed path of undeletable edges from x to y) while P remains an s 2 t 1 -maxflow in G + A throughout the process (as we only reroute the paths through undeletable arcs) and every path P ∈ P still visits the same deletable arcs, in the same order (so the properties of B are unharmed). The deletion of arcs in A in the last step only extends the space of s 2 t 1 -cuts in G + A , so if (A , P ) was compatible with some s 2 t 1 -cut Z before the process, then it is also compatible after the process. Furthermore, as the only deletable arcs in G +A are the important arcs, in the end we have the following property: every (x, y) ∈ A is of the form (x, y) = (u 2 , v 1 ) for some u, v ∈ V (G).
The above discussion implies that we can obtain the desired result (A, P, B) in the natural manner: for every (x, y) = (u 2 , v 1 ) ∈ A , we add (u, v) to A, for every P ∈ P we add to P a path P being the path P with all important edges on it contracted, and for every B ∈ B we add to B the set Thus, it remains to prove Theorem 7.2. This proof spans the rest of this section.

Initial setup
The algorithm of Theorem 7.1 first filters out some trivial cases in which A = ∅ can be returned. In these cases one can take B to be a singleton and construct the desired soybeans as in the comment after the statement of Theorem 7.2. After treating these trivial cases, the algorithm of Theorem 7.1 invokes a recursive subroutine.
The recursion has depth strictly less than h max (k) = O(k 3 ). The input to the recursive call consists of a graph G with distinguished vertices s, t ∈ V (G), an integer k, an st-flow P, and an integer κ. The output is a set A ⊆ V (G) × V (G) and an st-maxflowP such that λ G+A (s, t) ≥ κ and for every star st-cut Z with |Z| ≤ k and |core(Z)| ≥ κ, (A,P) is compatible with Z with high probability.
An important insight about the structure of the recursion is that for every recursive call ρ on a graph G the following holds: For every subcall on a graph G , G − {s, t} is a subgraph of G − {s, t}. Furthermore, the graphs G − {s, t} over all recursive subcalls are pairwise vertexdisjoint (as subgraphs of G).
Constructing B. Let (A,P) be the output of the algorithm of Theorem 7.1 and consider P ∈P. (We separately partition the deletable edges of E(P ) into sets of B, so that every B ∈ B is contained in E(P ) for one P ∈P.) If present, we put at most two deletable edges of E(P ) that are incident with s or t into separate singleton sets of B and do not worry about them further.
For every vertex v ∈ V (G), we can consider all recursive calls on graphs G that contain v. By the previous observation on the structure of the recursion, these calls form an upward path in the recursion tree. For every call ρ in the recursion whose parent ρ corresponds to the "large " case, we assign to e a local signature as follows. The recursive call is applied to a graph G α for some α such that G α − {s, t} is a subgraph of G between the st-mincuts C b α ← −1 and C b α → +λ , the edges incident to s and t in G α correspond to the edges of the two said mincuts, and every vertex in G α is reachable from s and reaches t. Pick a path Q 1 from s to v in G α and let i 1 be the index of the path of the flow P in the parent call ρ that contains the edge of C b α ← −1 corresponding to the first edge of Q 1 . Pick a path Q 2 from v to t in G α and let i 2 be the index of 24 the path of the flow P in the parent call ρ that contains the edge of C b α → +λ corresponding to the last edge of Q 2 . Then (i 1 , i 2 ) is the local signature of v at ρ . The signature of v is the sequence of all local signatures of v, in the top-to-bottom order in the recursion tree. The signature of an edge e is the pair consisting of the signatures of its endpoints. Finally, we define B as the partition of the deletable edges ofP according to the path ofP they belong to and according to their signatures. Since there are Let f p (x) = 1 + 2px, q 0 (p) = 2p, q i+1 (p) = f p (q i (p)) for 0 ≤ i < h max (k), and q(k, p) = q hmax(k) (p); recall that h max (k) = O(k 3 ) is the maximum possible depth of the recursion for a fixed value of k. We have q(k, p) = 2 O(k 3 log(kp)) . We prove, by the bottom-to-top induction over the recursion tree, that if the recursive call ρ at depth i applied to a tuple (G, s, t, k, P, κ) returned (A,P), P ∈P, and C and D are two disjoint sets of size q h−i (p) consisting of deletable edges of E(P ) of the same signature that are interlaced on P , then G−{s, t} contains a family of p pairwise vertex-disjoint CD-soybeans. Here h ≤ h max (k) is the actual depth of the recursion.
In the subsequent paragraphs we consider different cases the algorithm of Theorem 7.1 can enter and in each of them prove the desired claim.

Initial steps
We first investigate the initial preprocessing steps.
These can be split into two types. The first type are leaves of the recursion: when λ G (s, t) = 0 and when λ > k. In the first case, the algorithm returns A = ∅ andP = ∅, so there is nothing to prove. In the second case, the algorithm returns A = {(s, t)} andP consisting of a single path P along the edge of A, and again there is nothing to prove.
The second type of steps invoke one recursive call ρ on a modified graph G , obtaining (A ,P ). Recall that in all cases, G − {s, t} is a subgraph of G − {s, t}. The algorithm returns (A,P) that is constructed from (A ,P ) by setting A to be A plus at most 2λ + 1 ≤ 2k + 1 additional edges, all incident with s or t, andP to beP with possibly one additional one-edge path. The claim is again straightforward as q h−i−1 (k, p) ≤ q h−i (k, p) and the requested soybeans cannot use vertices s nor t.

Base case
In the base case of the algorithm, P is an st-maxflow and for every i = j, i, j ∈ [λ], there is no path from V (P i ) to V (P j ) in G − {s, t}. This is a place where we need to slightly modify the behavior of the algorithm of Theorem 7.1.
Let B be the set of all bottleneck edges. For every i ∈ [λ], let (u i,1 , v i,1 ), . . . , (u a i , v a i ) be the bottleneck edges on P i , in the order along P i . Denote v i,0 = s and u i, Note that the graphs G i intersect only in vertices s and t and λ G i (s, t) = 1.
For a star st-cut Z of size at most k, let Z i = Z ∩ E(G i ). The analysis of the base case shows that Z i is a star st-cut in G i and core G (Z) = i∈[λ] core G i (Z i ). Furthermore, either core G i (Z i ) consists of a single bottleneck edge and Z i contains no other bottleneck edge on P i , or Z i does not contain any bottleneck edge of P i at all.
For every i ∈ [λ], we proceed as follows. We guess integers 1 ≤ κ i ≤ k i ≤ k such that i∈[λ] κ i ≥ κ and i∈[λ] k i ≤ k. We aim at k i = |Z i | and κ i = |core G i (Z i )|. This happens in total with probability 2 −O(k log k) .
If κ i = 1, we aim at capturing star st-cuts Z i with core G i (Z i ) consisting of a single bottleneck edge. We set A i = {(v i,b , u i,b+1 ) | 0 ≤ b ≤ a i } and P i to be a path consisting of edges The algorithm returns A i as part of the set A and P i as one of the flow paths inP.
For our desired claim, observe that the deletable edges on P i are only bottleneck edges. Thus, given C and D interlaced on P i , each of size at least q 0 (k, p) = 2p, one can construct the desired soybeans as follows: If c 1 , c 2 , . . . , c 2p and d 1 , d 2 , . . . , d 2p are the first 2p edges of C and D, respectively, and P i,j is the subpath of P i from c 2j to d 2j , then {P i,j P i,j | j ∈ [p]} is the desired family of soybeans. So we can put the whole A i as a single set in B.
If κ i > 1, we aim at capturing star st-cuts Z i that do not contain any bottleneck edge on P i . Let A • i be the set of copies of all bottleneck edges on P i . For every 0 ≤ b ≤ a i , we recurse on G i,b with v i,b playing the role of s and u i,b+1 playing the role of t, parameters k i , κ i , and a flow consisting of a single flow path The returned setP consists of, for every i ∈ [λ], κ i flow paths, combined from flow pathsP i,b (recall that eachP i,b is of size at least κ i ) concatenated using edges of A • i . For our desired claim, consider a returned path P ∈P and interlaced sets C, D of q h−i (k, p) deletable edges on P . We have two cases. First, there exists an integer 0 ≤ b ≤ a i such that G i,b contains at least q h−i−1 (k, p) + 1 edges of C. Then, the path ofP i,b used to construct P contains interlaced subsets of C and D of size q h−i−1 (k, p). The claim follows from the inductive hypothesis for the recursive call on G i,b .
In the second case, there are at least 2p + 1 indices b such that G i,b contains an edge of C.
, G i,b j contains an edge of C and G i,b j contains an edge of D. For j ∈ [p], let Q j be a path from v j,b j to u j,b j +1 containing an edge of C from G i,b j and let Q j be a path from v j,b j to u j,b j +1 containing an edge of D from G i,b j . Such paths exist by the construction of the graphs } is the desired soybean harvest.

Small case
In the small case the situation is very similar to the second type of initial steps.
The algorithm always invokes one recursive call, on a graph G such that G − {s, t} is a subgraph of G − {s, t}, obtaining (A ,P ). The returned set A consists of A and additional edges A 0 with |A 0 | ≤ 4λ big + 2 ≤ 16k 3 + 14, all incident with s or t. The returned flowP consists of the pathsP , possibly with an edge of A 0 added at the beginning or end, and possibly one additional path that contains at most one deletable edge.
Thus, the claim follows directly from the inductive hypothesis for the recursive subcall.

Large case
In the large case the situation is quite similar to the base case, but a bit more complex. Let (G, s, t, k, P, κ) be the input to the recursive call in question. The algorithm recurses on graphs G α for all excellent indices α, obtaining pairs (A α ,P α ) Observe that in the returned flowP, the only deletable edges are those in graphs G α on pathŝ P α . Fix P ∈P; the path P consists of edges of A and some flow paths from flowsP α . Assume that we have interlaced sets C, D of deletable edges on P of the same signature, each of size q h−i (k, p).
As in the base case, there are two cases. First, there exists α such that C contains at least q h−i−1 (k, p) + 1 edges in G α . Then, the flowpath P ∈P α contained in P contains interlaced subsets C , D of C and D of size q h−i−1 (k, p) each. The claim follows from the inductive hypothesis.

26
In the second case, there are at least 2p + 1 indices α for which there is an edge of C in G α . Thus, there are indices α 1 ≤ α 1 < α 2 ≤ α 2 < α 3 ≤ α 3 < . . . < α p ≤ α p such that for every j ∈ [p], there is an edge c j of C in G α j and an edge d j of D in G α j .
Recall that all edges of C and D are of the same signature. That is, there are two paths P 1 , P 2 ∈ P such that, for edge e ∈ C ∪ D, if e lies in G α then there is a walk W (e) in G from the head of the edge of E(P 1 ) ∩ C b α ← −1 to the tail of the edge of E(P 2 ) ∩ C b α → +λ that contains e and is completely contained between C b α ← −1 and C b α → +λ . For every j ∈ [p], let W j be a concatenation of W (c j ) and a subpath of P 2 from the tail of the edge of E(P 2 ) ∩ C b α j → +λ to the tail of the edge of E(P 2 ) ∩ C b α j → +λ and let W j be a concatenation of and a subpath of P 1 from the head of  . In this section, we show that Weighted Directed Multicut is W[1]-hard parameterized by k, even with two terminal-pairs (that is when p = 2). In fact, we show that it does not admit an f (k) · n o(k/ log k) algorithm under the ETH. We denote this problem with two terminal pairs by 2-Wt-DMC. The hardness proof we provide is essentially a simplification of the reduction given by Pilipczuk and Wahlström [25] for proving the W[1]-hardness of the Directed Multicut problem with four terminal-pairs. Our reduction essentially demonstrates that the synchronization of some gadgets achieved in the reduction in [25] using two additional terminal-pairs can also be achieved if the vertices are allowed polynomial (in the input size) weights. This helps us to eliminate two terminal-pairs in the reduction of [25] at the cost of adding polynomial weights.
Theorem 8.1. Weighted Directed Multicut is W[1]-hard even for two terminal pairs. Furthermore, assuming the ETH, the problem cannot be solved in f (k) · n o(k/ log k) time, where n is the number of vertices of the input graph.
To prove Theorem 8.1, we give a reduction from Partitioned Subgraph Isomorphism (PSI), parameterized by the number of edges in the pattern graph. In the Partitioned Subgraph Isomorphism problem, given two undirected graphs G, H such that V (G) = i∈V (H) V i , the goal is to determine if there exists a homomorphism ξ : V (H) → V (G) such that ξ(i) ∈ V i for each i ∈ V (H). This problem has been shown to be W[1]-hard parameterized by |E(H)| by Marx [22,Corollary 6.3]. In fact, the authors show that there is no f (k) · n o(k/ log k) algorithm for PSI, where k = |E(H)| and n is the number of vertices in the input graph, unless the ETH fails.
Proof of Theorem 8.1. Let (G, H) be an instance of PSI where V (G) = i∈V (H) V i . Without loss of generality, let V (H) = {1, . . . , h}, let |V i | = |V j | = n for each i, j ∈ V (H) and assume that H has no isolated vertices. Let V i = {v i 1 , . . . , v i n }. Let k = |E(H)|, then |V (H)| ≤ 2k since H has no isolated vertices. We now construct an instance (D, (s i , t i ) i∈ [2] , wt, k , W ) of 2-Wt-DMC. Set k = 5k + h and W = M (2k(n + 1) + h) + k, where M = k + 1. : An illustration of the construction of the paths X i,j , Y i,j , X j,i , Y j,i and the grid P i,j , where i < j and n = 5. The brown vertices whose labels have subscript a have weight M a. The green vertices whose labels have subscript a have weight M (n + 1 − a). The black vertices have weight 1 and the white vertices are undeletable. The red, and the blue, highlighted paths are the s 1 t 1 -path, and s 2 t 2 -path respectively, that survive after deleting the solution vertices from X i,j , Y i,j , X j,i and Y j,i . The unique common intersection point of the two highlighted paths is p i,j a,b , which is picked by the solution. The vertices picked by the solution are encircled in red.
i,j aŷ i,j n t 1 s 1 Figure 5: The paths X i,j , Z i and Y i,j are shown. If the index of a vertex is a, then its weight is M if it the vertex is blue, M a if the vertex is brown, M (n + 1 − a) if the vertex is green and W +1 otherwise. This gadget together with the definition of the target weight W of the solution, ensures that a solution picks exactly one vertex from each of the three paths. Moreover, the three vertices chosen from these three paths have the same index.
Construction of D: For each i ∈ V (H), let Z i be the path (z i n ,ẑ i n , z i n−1 ,ẑ i n−1 , . . . , z i 1 ,ẑ i 1 , z i 0 ) on 2n + 1 vertices. These paths are called the Z-paths and are added to D. For each ordered pair n ,ŷ i,j n , y i,j n−1 ,ŷ i,j n−1 , . . . , y i,j 1 ,ŷ i,j 1 , y i,j 0 ) be paths on 2n + 1 vertices each. These paths are called X-paths and Y-paths, respectively, and are also added to D. Next, we describe the gadget that synchronizes the vertices that a solution for 2-Wt-DMC picks from the X-, Y-and Z-paths. For each ordered pair (i, j) ∈ V (H) × V (H) such that {i, j} ∈ E(H), and for every a ∈ {0, 1, . . . , n}, we add the edges (x i,j a , z i a ) and (z i a , y i,j a ) to D (see Figure 5 for an illustration). Further we add two terminal-pairs (s 1 , t 1 ) and (s 2 , t 2 ) together with the following incident edges. For each {i, j} ∈ E(H), such that i < j, the edges (s 1 , x i,j n ), (x i,j 0 , t 1 ), (s 1 , y i,j n ), (y i,j 0 , t 1 ) are added to D. Further the edges (s 2 , x j,i n ), (x j,i 0 , t 2 ), (s 2 , y j,i n ), (y j,i 0 , t 2 ) are added to D. The edges described here ensure that for each (i, j) ∈ V (H) × V (H) such that (i, j) ∈ E(H), there exists an a ∈ {0, 1, . . . , n} such that the solution for 2-Wt-DMC picksẑ i a ,x i,j a , andŷ i,j a The next gadget ensures that vertices of the 2-Wt-DMC solution in the paths described above are the map of a valid homomorphism. For every edge {i, j} ∈ E(H) such that i < j, we add a grid P i,j on the vertex set {p i,j a,b | a, b ∈ {1, . . . , n}} to D. The edge set contains the column edges {(p i,j a,b , p i,j a+1,b ) | a ∈ {1, . . . , n − 1}, b ∈ {1, . . . , n}}, and the row edges {(p i,j a,b , p i,j a,b+1 ) | a ∈ {1, . . . , n}, b ∈ {1, . . . , n − 1}}. The weight function of the vertices of this grid is defined as follows: , and wt(p i,j a,b ) = W otherwise. Further we add edges to D connecting the paths X i,j , Y i,j , X j,i and Y j,i to P i,j . For every a ∈ {1, . . . , n}, the following edges are added: (x i,j a , p i,j a,1 ), (p i,j a,n , y i,j a−1 ), (x j,i a , p i,j 1,a ), and (p i,j n,a , y j,i a−1 ). This finishes the construction of D. See Figure 4 for an illustration of the construction.
We next show that (G, H) is a Yes-instance of PSI if and only if (D, k , (s i , t i ) i∈ [2] , wt, W ) is a Yes-instance of 2-Wt-DMC.
H) and {i, j} ∈ E(H), i < j} and claim that it is a solution to the constructed 2-Wt-DMCinstance (D, k , (s i , t i ) i∈ [2] , wt, W ). Observe that the set S contains a vertex from Z i , X i,j , Y i,j and the grid P i,j for every (i, j) ∈ V (H) × V (H) with {i, j} ∈ E(H). Further observe that |S| = 5k + h and wt(S) = M (2k(n + 1) + h) + k since the weight of the vertices on the X-and Y-paths in S is 2kM (n + 1), the weight of the vertices of Z-paths in S is M h and the weight of the grid vertices in S is k.
We claim that D − S has no s 1 t 1 -path and no s 2 t 2 -path. Here, we show that D − S has no s 1 t 1 -path. That there is also no s 2 t 2 -path follows by symmetric arguments. Observe from the construction that every (s 1 , t 1 ) path contains x i,j n or y i,j n , for some i, j, as its first internal vertex. There are four kinds of s 1 t 1 -paths in D. The first one traverses X i,j fully until x i,j 0 (which is an in-neighbour of t 1 ). The second one traverses Y i,j fully. Both, paths of the first and the second kind, are hit by S as S contains a vertex from X i,j and a vertex from Y i,j .
The third kind of s 1 t 1 -path traverses some subpath of X i,j , say until the vertex x i,j a , jumps to Z i at vertex z i a , traverses Z i until say z i b where b ≤ a, jumps to Y i,j at vertex y i,j b , and then traverses Y i,j until y i,j 0 . Sincex i,j φ(i) ,ŷ i,j φ(i) ,ẑ i φ(i) ∈ S, if such a path exists then a ≥ φ(i) and b ≤ φ(i), thus the y i,j b y i,j 0 -subpath of Y i,j traversed by such an s 1 , t 1 -path contains a vertex of S, namelyŷ i,j φ(i) . The last kind of s 1 , t 1 -path passes through the grid P i,j . Such a path traverses X i,j until x i,j a , jumps to the first column of the grid at the vertex p i,j a,1 , traverses the grid P i,j to get to a vertex p i,j b,n (there are potentially many ways to reach this vertex inside the grid), for some b ≥ a, then jumps to Y i,j at the vertex y i,j b−1 , and then traverses Y i,j until y i,j 0 . Sincex i,j φ(i) ∈ S, if a < φ(i), the path is hit by S. Sinceŷ i,j φ(i) ∈ S, if φ(i) < b, the path is hit by S. Otherwise a = b = φ(i). In this case the s 1 t 1 -path under consideration uses exactly the vertices of the p i,j φ(i),i p i,j φ(i),n -subpath of the grid. Since p i,j φ(i),φ(j) ∈ S, this kind of s 1 t 1 -path is again hit by S. Thus, S is a solution of the 2-Wt-DMC-instance (D, k , (s i , t i ) i∈ [2] , wt, W ).
Reverse direction. Let S ⊆ V (D) be a solution for the 2-Wt-DMC-instance (D, k , (s i , t i ) i∈ [2] , wt, W, ). We construct a function φ : V (H) → {1, . . . , n} such that for each {i, j} ∈ E(H), (v i φ(i) , v j φ(j) ) ∈ E(G). Note that, since for every path X i,j and for every path Y i,j , there is an s 1 t 1 -path or an s 2 t 2 -path containing only this path, S contains at least one vertex from each X i,j and each Y i,j . Also, since the vertices x i,j n and y i,j 0 are undeletable, the set S contains a deletable vertex of Z i , as otherwise there is an s 1 t 1 -path or an s 2 t 2 -path starting from x i,j n and then jumping to the path Z i at the vertex z i n , traversing the path Z i until z i 0 , then jumping to y i,j 0 (which is an in-neighbour of t 1 ).
Fix (i, j) ∈ V (H) × V (H) such that {i, j} ∈ E(H) and i < j. The case when j > i is symmetric. We eventually show that S intersects X i,j , Y i,j and Z i , each at exactly one vertex. Towards this, let a ∈ {1, . . . , n} be the largest index such thatx i,j a ∈ S, and let b ∈ {1, . . . , n} be the smallest index such thatŷ i,j b ∈ S. We first claim that a ≥ b. Suppose a < b, then consider the following s 1 t 1 -path in G − S. The path first visits x i,j n , traverses X i,j until reaching x i,j a (note that none of the vertices on this subpath belong to S so far, either due to the choice of a or because they are undeletable), jumps to z i a (note that this vertex is undeletable), and then jumps to y i,j a and finally traverses Y i,j until reaching y i,j 0 (again, none of the vertices of this subpath belongs to S either due to the choice of b or because they are undeletable). This is a contradiction to the fact that S is a solution.
From the above paragraph, wt(S) ∩ (X i,j ∪ Y i,j ) ≥ M · a + M · (n + 1 − b) ≥ M · (n + 1). Note that if a > b, then wt(S) ∩ (X i,j ∪ Y i,j ) > M · (n + 1) + M . Thus, if S picks exactly one vertex from each X-, Y-and Z-paths, then the weight of S restricted to the vertices in these paths is 4kM · (n + 1) + M h. Since the total weight of S is 4kM · (n + 1) + M h + k, and the weight of each vertex on the paths X i,j , Y i,j or Z i is at least M = k + 1, we conclude that S indeed picks exactly one vertex from each of the X-, Y-and Z-paths. Moreover, a = b. That is, S ∩ X i,j =x i,j a and S ∩ Y i,j =ŷ i,j a . We now show that S ∩ Z i =ẑ i a . Suppose not, then consider the following s 1 t 1 -path in G − S. It first visits x i,j n , traverses X i,j until reaching x i,j a , jumps to Z i at the vertex z i a , traverses Z i until reaching z i a−1 (note that the only deletable vertex on this subpath isẑ i a , which by our assumption is not in S), jumps to the path Y i,j at the vertex y i,j a−1 , and then traverses Y i,j until reaching y i,j 0 . Again, this yields a contradiction to S being a solution. So far, we have concluded that S intersects each of the paths X i,j , Y i,j and Z i in exactly one vertex. In fact, there exists a ∈ {1, . . . , n} such that S ∩ X i,j =x i,j a , S ∩ Y i,j =ŷ i,j a and S ∩ Z i =ẑ i a . Hence, to construct φ, define φ(i) = a. Fix (i, j) ∈ V (H) × V (H) and i < j. Consider the s 1 t 1 -path, we call it P 1 , that first visits x i,j n ,then traverses X i,j until x i,j φ(i) , jumps to the first column of the grid P i,j at vertex p i,j φ(i),1 , traverses the path in the φ(i)-th row of P i,j , that is the subpath from (p i,j φ(i),1 to p i,j φ(i),n ), jumps to the path Y i,j at the vertex y i,j φ(i) and then traverses Y i,j until reaching y i,j 0 . Similarly, consider the s 2 t 2 -path, we call it P 2 , that first visits x j,i n , traverses the path X j,i until reaching x j,i φ(j) , jumps to the first row of the grid P i,j at the vertex p i,j 1,φ(j) traverses the path in the φ(j)-th column of P i,j , that is the subpath from p i,j 1,φ(j) to p i,j n,φ(j) , jumps to the path Y j,i at y j,i φ(j)−1 and then traverses Y j,i until reaching y j,i 0 . Observe that the paths P 1 and P 2 do not intersect any of the vertices of S that are on some X-, Y-or Z-path. Also, the paths P 1 and P 2 intersect at exactly one vertex of the grid P i,j , which is p i,j φ(i),φ(j) . Since S has at most k vertices that are in none of the X-, Y-or Z-path, S contains at most one vertex from each P i,j . Thus, p i,j φ(i),φ(j) ∈ S. As wt(S) ≤ W , we can deduce from the construction of D that (v i φ(i) , v j φ(j) ) ∈ E(G).

A Hardness of arbitrary CSPs with permutation constraints
In this section we explain in bigger detail the claim from the introduction that without any control on the complexity of permutation constraints, the obtained CSP instance is W[1]-hard when parameterized by the number of variables and permutation constraints.
Recall the classic W[1]-hard Multicolored Clique problem: the input consists of an integer k being the parameter, a graph G, and a partition of V (G) into k independent sets V 1 , V 2 , . . . , V k ; the goal is to find a k-clique in G, which necessarily needs to contain exactly one vertex from each set V i . By a padding argument, we can assume |V 1 | = |V 2 | = . . . = |V k | = n. For each 1 ≤ i ≤ k, enumerate the vertices of V i as v i,0 , v i,1 , . . . , v i,n−1 .
For every 1 ≤ i ≤ k, create a variable x i with domain {0, 1, . . . , n − 1}; setting the value x i = a corresponds to choosing a vertex v i,a to our clique. For every 1 ≤ i, j ≤ k, i = j, create a variable y i,j with domain {0, 1, . . . , n−1}×{0, 1, . . . , n−1} ordered lexicographically; setting the value y i,j = (a, b) corresponds to choosing vertices v i,a and v j,b to our clique. Bind the variables using the following constraints: • For every 1 ≤ i, j ≤ k, i = j, we express a constraint 0≤a,b<n y i,j = (a, b) =⇒ x i = a as the following conjunction: (y i,j ≤ (a − 1, n − 1)) ∨ (x i ≥ a) .
The above is an encoding of the input Multicolored Clique instance a CSP instance with k + k(k − 1) = k 2 variables and k 2 permutation constraints. Hence, we cannot hope for an FPT algorithm for our CSP instances, with only the number of variables and permutation constraints as parameters; we need some structural parameter of the obtained permutation constraints. Note that the permutation π used above has a grid minor of size n in its permutation matrix. B Twin-width to grid-rank Theorem B.1 (Marcus and Tardos [20]). For every integer k, there is some c k ≤ 2 O(k log k) such that every n × m 0-1 matrix A with at least c k max(n, m) 1-entries has a k-grid minor. Moreover, if it exists, such a grid minor can be found in 2 O(k log k) n O(1) time.
Proposition B.2. Let n ≥ 2 and a 1 , . . . , a n be non-negative integers, and let s = n i=1 a i /n. Then, there exists an i ∈ [n − 1] such that a i + a i+1 ≤ 4s − 1.
Proof. Suppose for a contradiction that for all i ∈ [n − 1], a i + a i+1 ≥ 4s. First suppose that n is even. Then, n i=1 a i = a 1 + a 2 + n i=3 a i ≥ 4s + n i=3 a i ≥ · · · ≥ n 2 4s > ns, a contradiction. Next suppose that n is odd which means that n ≥ 3. In this case, n i=1 a i = a 1 + n i=2 a i ≥ a 1 + n − 1 2 4s ≥ 2(n − 1)s = ns 2 − 2 n > ns, a contradiction since 2/n < 1.
Proposition B.3. Let A be a 0-1 matrix, let k be a positive integer, and let c k be the constant from Theorem B.1. One can in 2 O(k log k) n O(1) time find either • a k-grid minor in A, or • a 4c k -contraction sequence of A, respecting the order of the rows and columns of A.
Proof. We do the following greedily. Assume the number of rows in A is at least the number of its columns, otherwise we swap the roles of rows and columns. Let o be the average number of 1-entries in each row of A. If o > c k , then by Theorem B.1, we can find a k-grid minor of A in 2 O(k log k) n O(1) time and we are done. Otherwise, o ≤ c k , which implies by Proposition B.2 that A has two consecutive rows which together have at most 4c k ones. We contract these two rows and repeat. In the following iterations, the error, or red entries are treated like 1s by the Marcus Tardos theorem. This is because such entries point to the existence of a 1-entry in the original matrix A which could be used to form a k-grid minor. Note that no row or column ever exceeds 4c k red entries if the algorithm succeeds to give a contraction sequence.
Theorem 2.5. There is a computable function f with f (k) = 2 O(k log k) such that the following holds. There is an algorithm that, given a 0-1 matrix A, in f (k)n O(1) time either • finds a k-grid minor in A, or • certifies that gr(A) ≤ f (k).
Proof. If A does not have a k-grid minor, then by Proposition B.3 there is a 4c k -contraction sequence of A that respects the order of the rows and columns of A. In the words of [3], this means that A is 4c k -twin-ordered, and a theorem in [3] asserts that A cannot have a (8c k + 2)mixed minor, which in turn implies that gr(A) ≤ (8c k + 2) = 2 O(k log k) .