Potatoes and Onions

1. Introduction

• The result extends grid-theorem duality to directed immersions, alongside earlier directed treewidth results for topological minors and Wollan’s undirected immersion theorem.The classical Grid Minor Theorem relates graph treewidth to grid minors.Source: §1 · pp. 2–3
• For every digraph D, either D contains a cylindrical wall of order k as an immersion or its directed tree-cutwidth is at most f1.1(k); sufficiently large immersed walls also force large directed tree-cutwidth.Theorem 1.1 also supplies a fixed-parameter algorithm to find either a wall immersion model or a bounded-width decomposition.Source: §1 · p. 3
• Directed tree-cutwidth uses a tree decomposition with bounded bag sizes, porosity across tree-edge cuts, and onion-guarding sets at tree nodes.Porosity bounds the number of edges needed to hit every directed cycle crossing a cut; onion-guarding bounds edges hitting onions crossing a node.Source: §1 · pp. 3–4
• Porosity is symmetric and supports uncrossing cuts, but it is not submodular, so the proof sometimes uses traditional cut order instead.A cut of order k has porosity at most k, but the converse need not hold.Source: §1 · p. 4
• Every digraph has a k-flow-connected tree-partition of porosity at most f1.3(k), and a fixed-parameter algorithm finds one.Vertices in the same bag have k edge-disjoint paths in each direction between them.Source: §1 · pp. 4–5
• The Potato Theorem organizes digraphs into k-edge-connected pieces using porosity-bounded cuts, providing a cleaner tree-partition structure than prior tangle-separating decompositions.The cited prior result does not provide a single laminar family of separations for this purpose.Source: §1 · p. 5

2.1. Motivating examples and the definition of directed tree-cutwidth

• Directed tree-cutwidth bounds bag sizes, cut porosities, and node onion-guards that hit crossing onion models in a consistent orientation.The parameter is the minimum width over tree-partitions; width is the maximum size of a bag, edge-guard, or onion-guard.Source: §2.1 · pp. 7–8

2.2. Wall immersion forces large directed tree-cutwidth

• A cylindrical wall immersion forces large directed tree-cutwidth: monotonicity reduces the proof to walls, whose robust onion immersions conflict with small guards.A balanced tree node and a large subwall avoiding its onion-guard yield the contradiction.Source: §2.2 · p. 8

2.3. No wall immersion implies bounded directed tree-cutwidth

• The Potato Theorem supplies a bounded-porosity, k-flow-connected tree-partition, the coarse decomposition used to bound width when large wall immersions are excluded.The proof then analyzes torsos, applies the directed grid theorem to bounded cycle-degree parts, and uses tripod packing outcomes to reincorporate bag vertices.Source: §2.3 · pp. 9–10

2.4. Proof of the Potato Theorem

• The Potato Theorem is proved by refining k-flow-connected bags into (k+1)-flow-connected pieces, then uncrossing local cut families into a globally laminar family.Important cuts control the porosity increase during uncrossing.Source: §2.4 · p. 11

3.1. Basics

• The basics define flows as edge-disjoint paths, flow-connectivity through such flows, and cycle-degree as the maximum number of edge-disjoint cycles incident with a vertex.Menger’s theorem relates an s-t flow of order k to an edge set of fewer than k edges whose removal disconnects s from t.Source: §3.1 · pp. 12–13

3.2. Immersions and topological minors

• An immersion maps vertices and edges to host vertices and trails; a topological minor additionally requires the modelling paths to be pairwise vertex-disjoint apart from endpoints.The text notes that immersion trails may be shortcut to paths.Source: §3.2 · p. 14

3.3. Cylindrical grids and walls

• A cylindrical wall is formed from a cylindrical grid by splitting interior-cycle vertices into head and tail vertices joined by an edge.The grid has disjoint cycles and paths that intersect in specified orders.Source: §3.3 · p. 14

3.4. Onions and tripods

• An onion has two vertices joined by two parallel root-to-tip edges and one return edge; onion-stars combine in- and out-oriented onions around a shared centre.A sufficiently large onion-star immersion contains any digraph satisfying the stated degree conditions, including a cylindrical wall of order k when its order is 2k^2.Source: §3.4 · p. 15

3.5. Directed cuts

• A directed cut is a vertex bipartition whose order is bounded by the number of edges crossing in at least one direction; porosity counts the minimum edges hitting every crossing cycle.A cut splits a vertex set when both sides contain vertices from it.Source: §3.5 · pp. 16–17

Tree-partitions

• Onion guards replace a subcubic-degree restriction: bidirected stars need not support interesting immersions, whereas onion stars contain large cylindrical walls as immersions.The guards prevent high-degree decomposition nodes from harbouring many onions spread across their neighbours.Source: §4 · p. 17
• Every rooted tree-partition can be made coherent in polynomial time without enlarging bags or changing edge-guards.Coherence requires the union of bags below each non-root node to induce a strongly connected subgraph.Source: §4 · pp. 18, 20

Directed tree-cutwidth

• Directed tree-cut-decompositions enrich tree-partitions with node onion-guards that hit all out-onions or all in-onions; directed tree-cutwidth is the minimum width over such decompositions.An out-onion has its tip and root in bags separated by the node, with the tip outside that node’s bag; in-onions are defined analogously, requiring the root outside the node’s bag.Source: §4 · pp. 20–21

Torsos

• A torso containing a 2k cylindrical wall as an immersion yields a k cylindrical wall immersion in the digraph, provided each child-subtree’s bags induce a strongly connected subgraph.The resulting immersion model can be found in polynomial time.Source: §4 · p. 22

Directed treewidth and related notions

• Directed treewidth is the minimum width of a directed tree-decomposition, using the definition of Kawarabayashi and Kreutzer [KK22].The width is determined by the largest bag-plus-incident-guards set, Γ(x).Source: §4 · p. 23

4. Decompositions

• The original Kawarabayashi–Kreutzer formulation using cylindrical-grid butterfly minors is equivalent to the cylindrical-wall topological-minor formulation, with maximum sizes differing by at most a factor of 2.The original proof gives a non-elementary g4.7 bound, later improved to an elementary bound by Hatzel, Kreutzer, Milani, and Muzi.Source: §4 · p. 24
• Campos, Lopes, Maia, and Sau give a fixed-parameter algorithm that finds either a topological-minor model of k or a directed tree-cut decomposition of width at most g4.7(k).The passage says this algorithm follows from modifying the proof of the Directed Grid Theorem.Source: §4 · p. 24
• Directed branchwidth is the minimum, over valid branch-decompositions, of the maximum size of an edge’s minimum vertex guard [Wie19].A directed branch-decomposition assigns digraph vertices bijectively to the leaves of a subcubic tree.Source: §4 · p. 24
• For every digraph D, dbw(D) ≤ dtw(D) + 1 and dtw(D) ≤ 9dbw(D) + 1; a width-k directed tree-decomposition converts to branchwidth at most k + 1 in polynomial time [Wie19].The two parameters are therefore functionally equivalent, with the stated linear bounds.Source: §4 · pp. 24–25

5. Large cylindrical wall immersions force large tree-cutwidth

• Directed tree-cutwidth is monotone under immersions: if D contains D′ as an immersion, D′ has no greater directed tree-cutwidth.The proof transfers the decomposition to D′ without increasing its width.Source: §5 · pp. 25–26
• For every positive integer k, the directed tree-cutwidth of f5.2(k) is at least k, with f5.2(k) defined as k^2 + 1.For k ≥ 2, the proof assumes for contradiction a directed tree-cut decomposition of k^2 + 1 with width at most k − 1.Source: §5 · pp. 26, 28
• The wall lower bound is proved by finding onion immersion models whose roots and tips lie across components around a decomposition-tree node.The contradiction argument selects wall cycles and paths avoiding the node’s guard, then uses their common-neighbour structure to force too many vertices into a bounded-width region.Source: §5 · pp. 26, 28, 29
• Every digraph containing a cylindrical wall of order f1.2(k) as an immersion has directed tree-cutwidth at least k.The proof derives this from immersion monotonicity and the wall lower bound.Source: §5 · pp. 25, 26, 29

6. Harvesting onions

• The Congested Onion Harvesting Lemma finds an onion-star immersion model of order k centred at x from two sufficiently large trail families satisfying its conditions.The families are pairwise edge-disjoint within each family, and each trail in P visits x once and every other vertex at most c times.Source: §6 · p. 29
• The lemma extends the formulation from c = 1 to allowing each vertex other than x to be visited at most c times.The paper uses the result with c = 2 and also supplies a fixed-parameter algorithm.Source: §6 · pp. 29–30
• Large out-onion-star and in-onion-star models with the same centre yield an onion-star immersion model of order k.The proof combines the two model families, handling their edge overlaps to obtain the required immersion.Source: §6 · pp. 30–31
• The harvesting result is used with c = 2 to obtain an onion-star model of order k, and its algorithmic statement yields a fixed-parameter search algorithm.The construction applies the lemma after forming suitable trail families from the in- and out-onion-star models.Source: §6 · pp. 30–31

7. Potato Theorem

• Every digraph has a k-flow-connected tree-partition of porosity at most f1.3(k), and a fixed-parameter algorithm finds one.The bound and algorithm apply for every positive integer k.Source: §7 · p. 32

7.1. Auxiliary properties of cuts

• Cut uncrossing preserves cuts with porosity at most the sum of the original porosities; closure restriction does not increase porosity, and crossing minimum-order cuts yield uncrossed cuts of the same order.The latter property applies to cuts of order k that split a k-flow-connected set and each have outgoing order k.Source: §7.1 · pp. 32–33

7.2. Important cuts

• There are at most 4^k important X-Y cuts of outgoing order at most k, and at most 2 · 4^k distinct k-key X-Y cuts.The important-cut bound is attributed to Chen, Liu, Lu, O’Sullivan, and Razgon.Source: §7.2 · pp. 34–35

7.3. Partial tree-partitions

• Every k-flow-connected set admits a partial tree-partition whose bags are (k+1)-flow-connected and whose tree-edge cuts have order k.This decomposition is the step used to divide k-flow-connected parts into more highly connected pieces.Source: §7.3 · pp. 35–36
• Lemma 7.9 extends a partial tree-partition with order-k cuts to one whose cuts are globally laminar and have porosity at most k^2 · 4^(k+1) + 2k.The extension preserves the partial tree-partition's tree and bag function.Source: §7.3 · pp. 38, 42
• The laminarization uses sets μ(A) that are disjoint for incomparable cuts and nested for comparable cuts with the same order-k boundary direction.These relations support construction of the globally laminar family σ(F), which agrees with the original family on S.Source: §7.3 · pp. 39, 40, 42

7.4. Proof of the Potato Theorem

• Every digraph has a k-flow-connected tree-partition of porosity at most f1.3(k), and a fixed-parameter algorithm finds one.The guarantee holds for every positive integer k.Source: §7.4 · p. 42
• The proof proceeds by induction on k, refining each k-flow-connected bag and joining the resulting trees to form a tree-partition with (k+1)-flow-connected bags.The induction starts at k = 1, where the strongly connected components give a tree-partition of porosity 0.Source: §7.4 · pp. 42–43
• Coherence and pairwise-disjoint strongly connected regions bound |Amb(f)| by k^2 · 4^(k+1) + 2k.Each ambiguous child region contains a cycle crossing the cut, so these disjoint cycles give a lower bound on the cut’s porosity.Source: §7.4 · p. 46
• The final porosity bound yields f1.3(k + 1) := (f1.3(k) + 1) · (k^2 · 4^(k+1) + 4k + 1) − 1.Coherence bounds |Amb(f)| by k^2 · 4^(k+1) + 2k; together with the bounds on Wx and H, this bounds each final adhesion set.Source: §7.4 · pp. 45–46
• The algorithmic construction runs in fixed-parameter time, using important cuts and Directed Subset Feedback Vertex Set [CCHM15] to compute the minimum cycle-hitting set H.The latter step uses the line digraph, where vertices corresponding to arcs crossing the cut are the target set; the proof has at most k inductive steps.Source: §7.4 · p. 46

8. Bounded degree case

• The bounded-degree argument reduces the result to the Directed Grid Theorem and the equivalence of directed branchwidth and directed treewidth.The proof composes the resulting bounds as g8.2(d, k) := max{3d · h4.10(g4.7(k)), 1}.Source: §8 · pp. 47–48
• Maximum cycle-degree d and directed branchwidth at most w imply directed tree-cutwidth at most max{3d · w, 1}.The construction uses cycle-hitting edge sets from branch-decomposition guards; the resulting bags have size at most 1.Source: §8 · p. 47
• For maximum cycle-degree d, every digraph contains a k-immersion or has directed tree-cutwidth at most g8.2(d, k).When d depends only on k, a fixed-parameter algorithm finds an immersion model or a decomposition with the stated width bound.Source: §8 · pp. 47–48

9. Small councils

• If a digraph has no k-immersion, at most z vertices of cycle-degree at least d, and a size-x hitting set for all in-tripods or all out-tripods in its migration digraph, it has a directed tree-cut-decomposition of width at most h9.1(d, x, z, k).The construction partitions the remaining vertices into regions and uses the hitting set and boundary edges to guard cycles crossing those regions.Source: §9 · pp. 48, 50
• When d, x, and z depend only on k, Lemma 9.1 yields a fixed-parameter algorithm to find the bounded-width directed tree-cut-decomposition.Source: §9 · p. 48
• In a digraph excluding an onion-star immersion of order k, a sufficiently flow-connected set Z lets an out-onion-star of order h9.2(q, k) rooted at z be transported to one of order q rooted at any distinct z′ in Z.When q depends on k, the lemma also gives a fixed-parameter algorithm to find the transported model.Source: §9 · pp. 51–52
• If at most z vertices have cycle-degree at least d and they form a g9.3(k, d)-flow-connected set, then D contains a k-immersion or has directed tree-cutwidth at most f9.3(k, d, z).When d and z depend only on k, a fixed-parameter algorithm finds either the immersion model or a decomposition of the stated width.Source: §9 · p. 53

Proof of Lemma 9.3

• A common center for in- and out-onion-star immersion models yields an onion-star immersion of order 2k^2 by Lemma 6.2, and hence a k-immersion.Source: §9 · p. 56

Lemma 9.4 (Small council lemma)

• For a digraph with at most z vertices of cycle-degree at least d, either it contains a k-immersion or its directed tree-cutwidth is at most f9.4(k, d, z).Source: §9 · p. 56
• When d and z depend on k, a fixed-parameter algorithm finds either a k-immersion model or a directed tree-cut decomposition of width at most f9.4(k, d, z).Source: §9 · p. 56

Proof of Lemma 9.4

• The proof constructs W so each distinct high-cycle-degree vertex pair has no path in D−W or an ℓ-flow, then applies Lemma 9.3 within each strongly connected component and combines the decompositions.The resulting width bound is f9.3(k, d, z) + z(z − 1)(g9.3(k, d) − 1).Source: §9 · p. 57

Proof of Theorem 1.1

• A result of supplies the proof’s onion-star step: a sufficiently flow-connected set of 2p vertices yields an onion-star immersion of order p, found by a fixed-parameter algorithm.This step is used to obtain the theorem’s decomposition when a wall immersion is absent.Source: §10 · pp. 57–59

Quasi-onion Lemma

• Every minimal (F, (X, Y))-quasi-onion is an onion immersion when F is a matching and no edge of F crosses the bipartition (X, Y).Minimality ensures the three trails are paths; the proof establishes they are edge-disjoint.Source: §10 · pp. 58–59

Theorem 1.1

• A digraph either contains a cylindrical wall of order k as an immersion or has directed tree-cutwidth at most f1.1(k), and a fixed-parameter algorithm finds either outcome.The algorithm returns an immersion model or a directed tree-cut decomposition of width at most f1.1(k).Source: §10 · p. 59

Proof of Theorem 1.1

• The proof combines directed tree-cut decompositions of individual torsos into a decomposition of the whole digraph, arranging auxiliary-vertex pairs in the same bag at a factor-three width cost.The torso decomposition trees are connected along the tree-partition structure, and the resulting bags discard auxiliary vertices.Source: §10 · pp. 59, 61
• In the combined decomposition, edge-guards hit cycles crossing decomposition edges, while onion-guards hit all in-onions or all out-onions at each node.The proof uses the Quasi-onion Lemma to handle onions projected from the digraph into a torso.Source: §10 · pp. 62–63

• The constructed directed tree-cut-decomposition T has width at most f1.1(k), completing the combinatorial bound.Source: §10 · p. 63
• All construction steps run in fixed-parameter time parameterized by k, proving the algorithmic statement of Theorem 1.1.This conclusion combines with the algorithmic statements in Theorem 1.3 and Lemmas 9.4 and 10.1.Source: §10 · p. 64

11. Conclusions and open problems

• Directed tree-cutwidth is functionally equivalent to the largest order of a cylindrical wall found as an immersion.The paper presents this as a suitable Grid Theorem for directed immersions.Source: §11 · p. 64
• The general Edge-Disjoint Paths problem gains no advance: bounded directed tree-cutwidth yields an XP algorithm, while DAGs make FPT unlikely under [Sli10].The paper notes that DAGs have bounded directed tree-cutwidth.Source: §11 · p. 64
• An FPT algorithm either certifies directed tree-cutwidth greater than k with a cylindrical-wall immersion or outputs a decomposition of width at most f(k).The bound f(k) is non-elementary, leaving efficient construction of reasonably sized decompositions as an open need.Source: §11 · p. 64
• The paper gives no explicit bound for f1.1(k), and its sole bottleneck to an elementary bound is the Congested Onion Harvesting Lemma.Improving that lemma's bound, even for c = 2, would directly imply an elementary bound for f1.1.Source: §11 · p. 64
• A plane-digraph example shows that pairwise high flow-connectivity need not force a K3 immersion, leaving the structure of digraphs excluding Kt unclear.The authors conjecture that sufficiently large minimum cycle-degree forces a Kt immersion.Source: §11 · pp. 65–66

A. Proof of Theorem 6.1

• Theorem 6.1 strengthens the Onion Harvesting Lemma by allowing trails, with each vertex except x repeating a fixed number of times.The proof sketch identifies the auxiliary Lemma 3.2 from as the place where the original path assumption was used.Source: A. Proof of Theorem 6.1 · p. 69
• A well-crossing pair of size fc(k) in each family yields an onion immersion and a well-crossing pair of size k in each family.The pair has congestion c and is rooted at x, as is the resulting pair.Source: A. Proof of Theorem 6.1 · p. 69
• With at least two dangerous paths, arc-disjoint trails formed from two paths and a suffix of Q yield an onion immersion.The construction uses a dangerous crossing to choose the tip y.Source: A. Proof of Theorem 6.1 · p. 70
• In that case, more than |Q|/3 trails remain available in Q◦, and the proof selects k-trail subfamilies to retain a well-crossing pair.The argument uses the dangerous-crossing bounds and chooses Q∗ to avoid arcs with tail y.Source: A. Proof of Theorem 6.1 · p. 70
• With at most one dangerous path, trimming safe-crossing paths produces subfamilies of size gc(k) that form a well-crossing pair.Claim 1 supplies the corresponding subfamilies from the trimmed family and Q−{Q}.Source: A. Proof of Theorem 6.1 · p. 70
• The second case extracts families of (c + 1)k trails, uses their crossings to form an onion immersion, then reduces them to k-trail families.Claim 2 gives the well-crossing families; the proof constructs arc-disjoint trails to the tip y and selects subfamilies avoiding crossings with tail y.Source: A. Proof of Theorem 6.1 · p. 71