1 Introduction↩︎

A guiding principle in algorithmic graph theory is that the tractability of a graph problem on a class of graphs is governed by the substructures the class is allowed to contain. Hamiltonian Cycle is the textbook example. On any class of bounded treewidth it is solvable in linear time by Courcelle’s theorem [1], while on planar graphs it is already NP-complete [2]. Writing \(\mathrm{\small HC}(\mathcal{C})\) for the restriction of Hamiltonian Cycle to a minor-closed class \(\mathcal{C}\), these two facts, together with the Grid Theorem [3], yield a clean dichotomy: \(\mathrm{\small HC}(\mathcal{C})\) is polynomial-time solvable if and only if \(\mathcal{C}\) excludes some grid as a minor, equivalently, if and only if \(\mathcal{C}\) has bounded treewidth [3]. Grids are thus the precise dichotomy delimiters, under minors, of polynomial solvability for Hamiltonian Cycle. The same mechanism – tractability below a treewidth threshold via Courcelle’s theorem plus hardness above it via NP-hardness in planar graphs – delineates the complexity of a large family of graph problems. Many algorithmic results that extend beyond bounded treewidth exploit this structural picture through the Irrelevant Vertex Technique, which repeatedly reduces instances of large treewidth to equivalent instances of bounded treewidth before applying dynamic programming. This paradigm underlies Robertson and Seymour’s algorithm for Disjoint Paths [4] and many subsequent developments in algorithmic graph minors. Despite its remarkable generality, surprisingly little is understood about the precise conditions under which the technique itself applies. Rather than seeking a dichotomy in the sense of classical complexity theory, in this paper we ask the following fundamental question: \[\begin{align} \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/uavbscwr.png}\tag{1}\end{figure}\tag{2} \end{align}\]

The search for such limitations naturally leads to annotated graphs, where a distinguished set of vertices forms part of the input. An annotated graph is a pair \((G,R)\) where \(G\) is a graph and \(R\subseteq V(G)\), depicted in red, is a set of annotated vertices. In the Terminal Cyclability problem the input is an annotated graph \((G,R)\) and the question is whether \(G\) contains a simple cycle passing through every red vertex. When \(R=V(G)\), this is exactly Hamiltonian Cycle. Given a class \(\mathcal{A}\) of annotated graphs, we write \(\mathrm{\small TC}(\mathcal{A})\) for the restriction of Terminal Cyclability to the annotated graphs in \(\mathcal{A}\). Passing from graphs to annotated graphs sharpens the lens: the natural containment relation is no longer the minor relation but its annotated refinement, the red-minor relation [5], [6]. Here, each branch set representing a red vertex is required to contain at least one red vertex [5], [7] of the host graph. If the Irrelevant Vertex Technique admits an exact structural characterisation in this setting, it should therefore be governed not by excluded minors, but by excluded red-minors.

Cycles through prescribed vertices are a classical theme in graph theory, studied since the 1960s [8]–[11]. The flavour of the problem is older than its complexity. In Lewis Carroll’s word game Doublets, first published in Vanity Fair in 1879, one transforms one word into another through intermediate words while being required to visit prescribed words along the way [12]. Viewed graph-theoretically, Carroll’s puzzle asks for a path through a distinguished set of vertices, making it a charming historical precursor of Terminal Cyclability(see also the related discussion by Björklund, Husfeldt, and Taslaman in [13]).

From the algorithmic point of view, however, the problem has been always studied under the assumption that the prescribed set is small. Robertson and Seymour’s algorithm for Disjoint Paths implies polynomial-time solvability for every fixed number \(k=|R|\) of prescribed vertices [4]. Since then, a long line of work has focused on improving the dependence on \(k\), leading to algebraic algorithms [13], kernelization results [14], and, most recently, an almost-optimal \(2^{\mathbf{O}(\sqrt{k}\log k)}\cdot n\)-time algorithm – again relying on the Irrelevant Vertex Technique – together with a near-linear kernel for planar graphs [15]. Throughout this line of work, the parameter governing tractability is the size of the prescribed set.

The present paper departs from this regime entirely. We place no restriction on the size of \(R\); indeed, it may be even linear in \(|V(G)|\). Instead, we show that, for spanning routing problems, the structural quantity governing the applicability of the Irrelevant Vertex Technique is not the number of annotated vertices, but the way they are distributed throughout the graph.

The difficulty is not that spanning routing appears algorithmically harder than classical routing. Rather, it is that one of the central paradigms of algorithmic graph theory – the Irrelevant Vertex Technique – suddenly ceases to behave in the way we have come to expect. To better understand this phenomenon, we briefly recall the reduction paradigm itself.

The Irrelevant Vertex Technique repeatedly replaces an instance by an equivalent induced sub-instance of bounded treewidth on which dynamic programming becomes applicable. Thus it may be viewed as a structural data-reduction scheme whose combinatorial guarantee is the following.

We say that a problem \(\Pi\), whose instances are graphs \(G\) or annotated graphs \((G,R)\), has the irrelevant vertex property if every instance is equivalent to an induced sub-instance of bounded treewidth: an induced subgraph \(G'\) of \(G\) – with \(R\subseteq V(G')\) in the annotated case – of bounded treewidth that is a yes-instance if and only if the original is. The reduction proceeds by repeatedly identifying a vertex whose deletion preserves the answer – an irrelevant vertex – until bounded treewidth is reached. Whenever such irrelevant vertices can be found efficiently, the reduction yields a polynomial-time preprocessing algorithm with a provable structural guarantee. Once the treewidth is bounded, dynamic programming solves the problem in time linear in \(n\), with the treewidth bound absorbed into the constant factor. The quantity controlled by this data-reduction is the treewidth of the reduced instance rather than its size and it is this bounded width that renders the instance tractable. A central question in algorithmic graph theory is therefore to identify the conditions under which a problem enjoys the irrelevant vertex property.

For problems on graphs, this paradigm is remarkably robust. Indeed, it often seems almost unconditional: with no restriction on the input, the irrelevant vertex property holds for the Disjoint Paths and the Minor Checking problem, as well as their common generalisation, the Folio problem [4] (see also [16]). For many further problems, excluding a minor is enough to recover it: recently, Sau, Stamoulis, and Thilikos [17] extended the paradigm to a broad family of graph problems definable in a certain fragment of monadic second-order logic.

For annotated problems this behaviour breaks down.

The obstacle is no longer the graph structure alone, but also the interaction between the graph and its annotation. Excluding any non-planar pattern – regardless of the annotation – still permits every planar annotated graph and, on fully annotated planar instances Terminal Cyclability, is exactly Hamiltonian Cycle, hence NP-hard. This brings us to the question driving this paper. For a red-minor-closed class \(\mathcal{A}\) of annotated graphs, we arrive at a more precise formulation of (2 ): \[\begin{align} \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/nrfmqjcs.png}\tag{3}\end{figure}\tag{4} \end{align}\] Typically, a precise answer to such a question amounts to finding an annotated graph parameter whose boundedness across \(\mathcal{A}\) is both necessary and sufficient for the desired property. Since Terminal Cyclability specialises to Hamiltonian Cycle on fully annotated graphs, where the governing parameter is treewidth, it is natural to search for the answer among annotated analogues of treewidth. As treewidth is characterised by the largest grid minor, such analogues arise by prescribing how the grid interacts with the annotation, ie. the red vertices.

This yields an infinite hierarchy of parameters as illustrated in . For each fixed integer \(r\geq 0\), the \(r\)-outer-annotated \((k\times k)\)-grid is obtained from the \((k\times k)\)-grid by colouring the \(r\) leftmost columns red. The parameter \(\mathsf{depth}_r(G,R)\) is then defined as the maximum \(k\) for which an \(r\)-outer-annotated \((k\times k)\)-grid is a red-minor of \((G,R)\). In the limit, we set \(\mathsf{depth}_\infty(G,R)\) by requiring all vertices of the grid to be red. Notice that the case \(r=0\) simply asks for the largest grid-minor in the graph while disregarding annotation entirely. Hence \(\mathsf{depth}_0\) is functionally equivalent to treewidth itself. As illustrated in , reddening additional columns only makes the pattern harder to realize. Consequently, the parameters form a genuine hierarchy – the depth-hierarchy – extending treewidth to annotated graphs, whose all levels collapse to treewidth whenever \(R=V(G)\).

The two extremes of this hierarchy were already understood and carry various names. The parameter \(\mathsf{depth}_1\) appears as monodimensionality in the work of Sau, Schirrmacher, Siebertz, Stamoulis, Thilikos, and Vigny [18] while \(\mathsf{depth}_{\infty}\) was introduced by Thilikos and Wiederrecht [7] as bidimensionality and was also used in the definition of the fragment \(\mathsf{CMSO/tw+dp}\) of Counting Monadic Second Order Logic, introduced in [17]. Both names are inspired by the distribution of the red vertices within the grid. One may therefore view the parameters \(\mathsf{depth}_r\) as successive levels of monodimensionality: the red vertices remain essentially one-dimensional inside the grid, but occupy an increasingly thick band.

From the perspective of the irrelevant vertex property, the two extremes already determine the landscape. We have already observed \(\mathsf{depth}_0\) to be the same as treewidth. Moreover, bounded \(\mathsf{depth}_1\) –equivalently bounded torso treewidth (see [19], [20]), or monodimensionality – is sufficient for Terminal Cyclability to enjoy the irrelevant vertex property [5]. At the other end, unbounded \(\mathsf{depth}_{\infty}\) – known as bidimensionality (see [5], [7]) – already contains every planar annotated graph and therefore exhibits NP-hardness which renders bounded \(\mathsf{depth}_{\infty}\) a necessary condition for Terminal Cyclability to enjoy the irrelevant vertex property. Thus bounded \(\mathsf{depth}_1\) is sufficient, bounded \(\mathsf{depth}_{\infty}\) is necessary, and the exact boundary must lie somewhere between them.

Our main result shows that the exact boundary is reached just one step beyond monodimensionality.

is merely the visible face of a more general phenomenon. The underlying combinatorial dichotomy concerns spanning routing in its full generality.

1.0.0.1 From cycles to linkages.

An annotated graph \((G,R)\) records a distinguished set \(R\); instead of asking that a single cycle covers \(R\), we may prescribe a pattern of connections and ask that the routing realising it covers \(R\). A natural generalisation of Terminal Cyclability is the following spanning routing problem: In Spanning Disjoint Paths (SDP) the input is an annotated graph \((G,R)\) together with terminal pairs \(\mathcal{T}=\{(s_1,t_1),\dots,(s_k,t_k)\}\) and the task is to find pairwise vertex-disjoint paths \(P_1,\dots,P_k\), forming a linkage of \(G\), such that \(P_i\) joins \(s_i\) to \(t_i\) for every \(i\in[k]\) and, moreover, \(R\subseteq V(P_1\cup\cdots\cup P_k)\). A solution is thus a linkage that realises the prescribed pattern and spans the annotation. If \(R=\varnothing\) this is the classical Disjoint Paths problem; if \(R=V(G)\) and \(k=1\) it asks for a Hamiltonian path between two prescribed vertices and both Terminal Cyclability and Hamiltonian Cycle reduce to it. In particular SDP is NP-complete already in restricted forms [2], [21], so the question is not whether unrestricted SDP is tractable, but whether the treewidth-reduction machinery behind Disjoint Paths survives the spanning requirement.

1.0.0.2 Disjoint Paths and the Irrelevant Vertex Technique.

The Disjoint Paths problem is one of the cornerstones of algorithmic graph theory. For \(k=2\) its tractability is already classical [22]–[24] and in Graph Minors XIII Robertson and Seymour proved that, for every fixed \(k\), it is solvable in time \(f(k)\cdot n^{3}\) [4]. This theorem is a basic primitive behind minor testing, rooted minor detection, folio computation, and a large part of the algorithmic theory of graph minors [25]; its running time was later improved to quadratic [26], i.e., one running in \(f(k)\cdot n^2\) time for some (huge) function \(f\). The latter was recently improved in two different ways. The one is the almost-linear, for fixed \(k\), algorithm of Korhonen, Pilipczuk, and Stamoulis in [27] and the other is the \(2^{2^{\mathbf{poly}(b)}\cdot \mathbf{poly}(k)}n^2\) time algorithm of Cavallaro, Gorsky, Kreutzer, Thilikos, and Wiederrecht in [16], where \(b\) is the bidimensionlity of the terminals. Moreover, the planar case of Disjoint Paths has been a perennial testing ground for sharper techniques [28]–[33].

The structural engine behind all of these results is precisely the irrelevant vertex technique described above, which for Disjoint Paths applies unconditionally: above a treewidth threshold depending only on \(k\), some non-terminal vertex is always irrelevant. Establishing the existence of that vertex is among the deepest parts of the series: the Vital Linkage Theorem of Graph Minors XXI [34] and the Irrelevant Vertex Lemma of Graph Minors XXII [35], later given a shorter proof by Kawarabayashi and Wollan [36], are what justify the algorithm of Graph Minors XIII. Since then, irrelevant vertices have become a standard interface between structural graph theory and algorithms [16], [17], [25], [27], [30].

For the spanning variant, the obstacle is that \(R\) is not assumed to be small and its size alone is too crude a measure: the intuition is that a large red set is harmless when it can be confined to the outer interface of a grid, yet a red set reaching only two columns into a large grid already compels every spanning linkage to thread the grid’s deep interior. What is needed is a structural criterion on \((G,R)\) that captures exactly when large treewidth still forces an irrelevant vertex outside the terminals and outside \(R\) – and the parameter that does so is \(\mathsf{depth}_2\), the same parameter that governs 1.

1.0.0.3 The dichotomy.

The irrelevant vertex property of the first part specialises to \(\mathrm{\small SDP}(\mathcal{A})\), the restriction of Spanning Disjoint Paths to instances where \((G,R)\in\mathcal{A}\), with irrelevance understood in the following concrete sense, the spanning analogue of the classical notion.

Our main result determines exactly when \(\mathrm{\small SDP}(\mathcal{A})\) has the irrelevant vertex property. The criterion is the same as the one of 1.

identifies when a natural spanning variant of Disjoint Paths has the irrelevant vertex property and the contrast with the unannotated world is the substance of the statement. There, the property is in effect always present: for Disjoint Paths and its relatives large treewidth alone exposes an irrelevant vertex, while this is also the case, under the exclusion of a minor, for \(\mathsf{CMSO/tw+dp}\)-definable problems [17] (in fact \(\mathsf{CMSO/tw+dp}\) is defined using disjoint paths as a core predicate). For the spanning annotated problem that we consider no such blanket guarantee holds: even under the exclusion of a red-minor the property may fail, and \(\mathsf{depth}_2\) marks the exact line between the two cases. The spanning requirement is, as far as we know, the first natural setting in which the Irrelevant Vertex Technique meets a precise non-trivial combinatorial limit.

1.0.0.4 The positive side.

On a red-minor-closed class of bounded \(\mathsf{depth}_2\), the Robertson–Seymour paradigm is fully restored for a genuinely spanning problem: an instance of SDP can be reduced, by deleting irrelevant vertices, to an equivalent instance of bounded treewidth. The resulting algorithm is summarised by the following.

As Terminal Cyclability can be seen as a special case of SDP, where \(k=3\), 3 also implies an \(2^{2^{\mathbf{poly}(d)}}\cdot n^{2}\) time algorithm for Terminal Cyclability. Also, Carroll’s puzzle, being SDP with \(k=1\), can be solved in the same running time where \(G\) expresses the “graph of words” and \(R\) are the prescribed words in it.

The decisive feature of 3 is that the dependence is on the number \(k\) of paths and on \(d\) and not on \(|R|\): the algorithm applies even when the set to be spanned is arbitrarily large, so that what governs the complexity is the placement of \(R\) (measured by \(d\mathrel{\vcenter{:}}=\mathsf{depth}_2(G,R)\)) rather than its size. To our knowledge this is the first parametrization of SDP – and, through 1, of Terminal Cyclability– that does not charge for the distinguished set; the bounded-distinguished-set regime is recovered as the special case in which \(d\) is automatically small. At the technical heart of the positive direction is a spanning analogue of the Vital Linkage Theorem: a vital instance of SDP of \(\mathsf{depth}_2\) at most \(d\) has treewidth \(2^{\mathbf{poly}(k+d)}\) where vitality asks the spanning linkage realising \(\mathcal{T}\) to be unique and to span the entire vertex set of the graph (see 9).

1.0.0.5 The negative side.

The \(\mathsf{depth}_2\) criterion is tight in the strongest sense we could ask for. If \(\mathcal{A}\) has unbounded \(\mathsf{depth}_2\) then arbitrarily large \(2\)-outer-annotated grids occur and no irrelevant-vertex rule of the above form can exist – already for a single terminal pair and already on planar graphs. The obstruction is best seen through \(R\)-spanning vital linkages. A classical vital linkage spans all of \(V(G)\) and is the unique linkage with its pattern and the unique-linkage theorem forces its host to have bounded treewidth [34]; an \(R\)-spanning vital linkage is required to be unique only subject to spanning \(R\). We construct, for \(k=1\), planar annotated graphs of arbitrarily large treewidth carrying an \(R\)-spanning vital linkage. Hence the bounded-treewidth phenomenon for vital linkages does not survive the replacement of \(V(G)\) by \(R\) and no treewidth threshold can guarantee an irrelevant vertex. Returning to Terminal Cyclability, the same construction applies already to cycles through a prescribed set: the irrelevant-vertex method provably breaks down once \(R\) carries arbitrarily large \(2\)-outer-annotated grids, so the dichotomy of 1 is tight in the same strong sense. Already for Terminal Cyclability, the situation of the prescribed set, rather than its size, decides whether the technique applies. Taken together, these results identify \(\mathsf{depth}_2\) as the exact combinatorial boundary of the Irrelevant Vertex Technique for spanning routing problems.

1.0.0.6 Why \(\mathsf{depth}_2\)?

Before proceeding, we briefly explain why \(\mathsf{depth}_2\) turns out to be the correct parameter and why, in retrospect, one should expect it to appear.

The central obstacle in extending the Irrelevant Vertex Technique to spanning routing is no longer the topology of the graph alone, but the interaction between topology and annotation. In the Graph Minor Structure Theorem, every graph of sufficiently large treewidth is described in terms of pieces that are almost embeddable into a surface. The only genuinely complicated parts of such a decomposition are the vortices: regions where the graph may exhibit arbitrary non-planar behaviour while remaining attached to the embedded part through a controlled interface. For spanning problems, these vortices acquire a second role. Besides carrying the topological complexity of the graph, they may also contain the annotated vertices that every solution is required to visit. Understanding how these two sources of complexity interact is precisely the difficulty addressed in this paper.

Our local structure theorem reveals that excluding a \(2\)-outer-annotated grid as a red-minor forces these two phenomena to separate. On the one hand, bounded \(\mathsf{depth}_2\) implies bounded bidimensionality, and therefore every annotated vertex must already lie either in the apex set or inside a vortex [5], [7]. On the other hand, and this is the new structural insight, each vortex itself admits a decomposition into two qualitatively different types of regions. Some regions may contain the full non-planar complexity of typical vortices but are guaranteed to contain no red vertices. The remaining regions are essentially planar and, moreover, all red vertices contained in such a region are confined to a single face. Thus the topology and the annotation become disentangled inside every vortex: non-planar behaviour occurs where there are no annotated vertices, while red vertices occur only in regions that are topologically simple.

This phenomenon is not accidental. The \(2\)-outer-annotated grid is precisely the annotated analogue of the shallow-vortex grid introduced by Thilikos and Wiederrecht [37], which characterises when vortices can no longer be simplified inside the Graph Minor Structure Theorem. Viewed from this perspective, \(\mathsf{depth}_2\) is not merely another member of the depth hierarchy but the first parameter that detects whether topology and annotation can still be separated inside vortices.

This separation is ultimately what makes our positive result possible. Once every annotated vertex lies on a bounded collection of facial regions, spanning linkages can be analysed using topological arguments that are impossible in general. See for an illustration. Conversely, the \(2\)-outer-annotated grid is exactly the first configuration in which annotated vertices can no longer be confined to a bounded number of faces. The additional freedom created by this failure is precisely what enables the construction underlying our lower bound. In this sense, the dichotomy of is already encoded in the local geometry of vortices: bounded \(\mathsf{depth}_2\) is exactly the point where topology and annotation cease to interfere with one another.

1.0.0.7 Beyond the Irrelevant Vertex Technique.

settles the applicability of the Irrelevant Vertex Technique for SDP. It does not, however, settle the complexity of the problem itself. Our dichotomy concerns the boundary of a fundamental algorithmic paradigm rather than the boundary of polynomial-time solvability.

In particular, it remains open whether SDP is already NP-hard for some fixed value of \(k\) on annotated graphs of unbounded \(\mathsf{depth}_2\). A positive answer would establish \(\mathsf{depth}_2\) not only as the exact boundary of the Irrelevant Vertex Technique, but also as the exact structural boundary of polynomial-time solvability.

There are, however, reasons to believe that the picture may be more subtle. One possibility is that algorithmic paradigms fundamentally different from the Irrelevant Vertex Technique – for example algebraic methods in the spirit of Björklund, Husfeldt, and Taslaman [13] – may succeed beyond classes of bounded \(\mathsf{depth}_2\). Another is that \(\mathsf{depth}_2\) already marks the boundary of fixed-parameter tractability, so that algorithms beyond it necessarily leave the FPT regime and require genuinely different techniques. Recent progress on XP algorithms exploiting the structure of vortices [38] may provide a promising starting point for such an approach.

Whether either of these possibilities can be realised remains, in our view, one of the most intriguing questions raised by this work.

1.0.0.8 Related work.

2 should be compared with recent quantitative work on irrelevant vertices. Cavallaro, Gorsky, Kreutzer, Thilikos, and Wiederrecht prove a general irrelevant-vertex theorem for the \((k,d)\)-Folio problem [16]: if the terminals are drawn from a set \(R\) of bidimensionality \(b\), the irrelevant-vertex threshold has the form \(2^{\mathbf{poly}(b+d)}\cdot\mathbf{poly}(k)\), so the distribution of the distinguished set controls the quantitative cost of the machinery. Our result is aligned with this viewpoint but goes one step further for the spanning problem: \(\mathsf{depth}_2\) is not only a quantitative parameter in the running time, but the qualitative sharp barrier for the applicability of the technique itself. More broadly, the paper fits into the developing theory of rooted, annotated, and colorful graph parameters: rooted grid minors show how a distinguished set can be forced onto a grid [39]; torso-type parameters measure the contribution of the annotation to treewidth after annotation-free parts are compressed [19], [20], [40]; annotated treewidth and bidimensionality measure grid minors controlled by the annotation [6], [7], [17]; and colorful minors provide the structural language for several possibly overlapping annotated sets [5].

1.1 Proof outline and organisation↩︎

The positive direction rests on three ingredients. A local structure theorem for annotated graphs of bounded \(\mathsf{depth}_2\) (3) shows that, away from large clique minors, the annotation can be combed onto a few layers of a flat wall. This feeds the spanning unique-linkage theorem (4), which bounds the treewidth of vital instances of bounded \(\mathsf{depth}_2\), building on the vital-linkage bounds of [16] and the flat-wall machinery of [5], [6], [41]. Together they yield the irrelevant vertex (5) and the algorithm (6). The matching lower bound, including its planarity, is given in 7. Below, we give a slightly more in-depth overview of our proof and the techniques used.

1.1.0.1 The local structure of annotated graphs of small \(\mathsf{depth}_2\).

The main structural contribution of this paper is a “local” structure theorem for annotated graphs with bounded \(\mathsf{depth}_2\). Here the term “local” means “with respect to a large wall” – or tangle if one prefers the language of Robertson and Seymour’s Graph Minors Series. The difference to typical structure theorems from the realm of graph minors is that, instead of describing the structure of the entire graphs in terms of clique sums or a tree-decomposition, we only describe the structure of the part of the graph which is highly connected to a given wall which is part of the input. Historically, such local structure theorems have turned out to be the more important and powerful counterpart of global theorems – see for example the introduction of [42]. Our structure theorem describes the local structure of annotated graphs of small \(\mathsf{depth}_2\) in terms of a so-called almost embedding on a surface of bounded Euler-genus under the deletion of a bounded size apex set and with the exception of a bounded number of vortices – each of bounded depth. What sets the theorem apart from comparable structure theorems [5], [6] is a more refined treatment of the red vertices: All red vertices must be confined to the vortices and into the apex set. Moreover, we show that each vortex can be partitioned into non-planar areas which are void of red vertices, and (essentially) planar areas, each with a single face that hosts all red vertices contained in the area. This “facial” behaviour is key for our algorithmic applications and the most technical part in our structural result.

Our local structure theorem is substantially stronger than a refinement of the Flat Wall Theorem. Its proof genuinely requires the full machinery of Robertson and Seymour’s structure theory, combining almost embeddings with the recently developed theory of colorful minors. Although in this paper we use the theorem only as an ingredient in the irrelevant-vertex algorithm, we expect it to have independent applications beyond the present work.

To be able to find this structure, we, in particular, require an annotated refinement of the so-called Two Paths Theorem which may be of independent interest (see for example ). We base our proof on recent structure theorems for annotated graphs of bounded bidimensionality – since bounded \(\mathsf{depth}_2\) implies bounded \(\mathsf{depth}_{\infty}\). Indeed, we use the structure theorem with polynomial bounds due to Gorsky, Protopapas, and Wiederrecht [6]. From here, we start analysing the structure of the vortices with respect to the red vertices inside. In order to reach the final state we show that a technique introduced by Thilikos and Wiederrecht [37] known as “vortex killing” can be applied to either find a large \(2\)-outer-annotated grid as a red-minor, or we may increase the apex set slightly in order to remove a certain substructure we call a “candle” from the vortices. The absence of candles is then the core property that enables us to push the red vertices remaining onto a single facial boundary.

A conceptual difficulty is, that we are working with almost embeddings and not real embeddings. This is unavoidable whenever one tries to prove a local structure theorem in the context of graph minors. However, this also makes it hard to properly define the notion of a face. Therefore, we introduce a property we call “facial” for annotated graphs in almost embeddings and make use of a special kind of curve to express the property we need.

1.1.0.2 A Vital Spanning Linkage Function.

The fundamental engine behind Robertson and Seymour’s algorithm for the \(k\)-Disjoint Paths problem is the so-called unique linkage function [34]. Let us denote this function by \(\beta\). We say that an instance of the \(k\)-Disjoint Paths problem is vital if it has a unique solution and this solution uses all vertices in the graph. The Vital Linkage Theorem of Robertson and Seymour [34] (see [16] for a more recent proof with better bounds) says that any vital instance of the \(k\)-Disjoint Paths Problem has treewidth at most \(\beta(k)\). The Irrelevant Vertex Technique itself is then a non-trivial and technical consequence of the Vital Linkage Theorem. The route we are taking is that we show on vital instances of \(k\)-Spanning Disjoint Paths that, if \(\mathsf{depth}_2\) is bounded, one can reduce the instance to an equivalent vital instance of \(k\)-Disjoint Paths where the Vital Linkage Theorem bounds the treewidth. This allows us to prove that vital instances of \(k\)-Spanning Disjoint Paths of small \(\mathsf{depth}_2\) have small treewidth.

In order to implement this reduction, we show that – under the assumption of bounded \(\mathsf{depth}_2\) – any part of the solution that interacts with the red vertices in a meaningful way must be radically limited. At their core, most of our arguments amount to the observation that the order in which the red vertices are visited, as well as the distribution of the red vertices onto the paths, are mostly irrelevant to the feasibility of the solution. This, in particular, means that even a surprisingly small amount of bidimensional infrastructure is often enough to reroute a solution to avoid some vertex and thereby contradict the vitality assumption.

1.1.0.3 Irrelevant vertices.

With a spanning version of the Vital Linkage Function established, we are now able to proceed with the design of the actual algorithm. The final algorithm will only make use of the so-called Flat Wall Theorem (see for example [4], [43]) and does not require the full power of our local structure theorem for annotated graphs of bounded \(\mathsf{depth}_2\). To prove the existence of an irrelevant vertex – always under the assumption that \(\mathsf{depth}_2\) is bounded – we follow a well-established route. We prove a variant of the so-called “Annulus Combing Lemma” of Golovach, Stamoulis, and Thilikos [44] for the setting of spanning linkages. Roughly speaking the Annulus Combing Lemma says that, given a large enough cylindrical grid which is “almost embedded” into an annulus such that most of the remaining graph – including the terminals – can be confined into the two holes of the annulus, then any solution to the \(k\)-Disjoint Paths problem can be transformed to one that intersects the embedded part in the columns of the cylindrical grid only. The main advantage of this piece of technology is, that it allows to decompose any given solution into two independent instances of the \(f(k)\)-Disjoint Paths problem. Establishing a variant for the \(k\)-Spanning Disjoint Paths problem allows us to implement the following strategy:

Once we have found a large flat wall – one may think of a flat wall as a big grid-like subgraph \(W\) of a graph \(G\) such that \(W\) itself together with all attachments of \(G-W\) to the interior parts of \(W\) can be drawn⁵ in a disc. Since \(\mathsf{depth}_2\) is bounded, there must exist a large subwall \(W'\) of \(W\) whose interior attachments do not contain any red vertices. Another application of pigeonhole yields a still huge subwall \(W''\) of \(W'\) such that now also no terminal attaches to the interior. Notice now that the inner part of \(W''\) is surrounded by a large cylindrical grid which allows for the application of the Annulus Combing Lemma. See for an illustration. To prove the spanning version of the Annulus Combing Lemma, we adapt the recent proof due to Cavallaro, Gorsky, Kreutzer, Thilikos, and Wiederrecht [16] to our setting. A key observation is that this is the only part where the Spanning Vital Linkage Function is explicitly applied. Once the Spanning Annulus Combing Lemma is proven, we have reached a point where neither our structure theorem nor the Spanning Vital Linkage Function are explicitly necessary any more.

1.1.0.4 The lower bound.

To prove the lower bound we give a recursive construction of gadgets which contain vital instances of \(k\)-Spanning Disjoint Paths for \(k \in \{ 1,2\}\) while having increasing treewidth and being red-minors of sufficiently large \(2\)-outer annotated grids. The idea follows more or less from the way the existence of the Spanning Unique Linkage function is proven: A crucial part of the upper bound is to consider a vital solution and then decompose the paths in this solution into families of homotopic subpaths in a surface which have all of their endpoints on certain parts of the boundary – this is really why we require the structure theorem for annotated graphs of bounded \(\mathsf{depth}_2\). Here, we encounter the same thing. However, while bounded \(\mathsf{depth}_2\) implies that all red vertices sit – essentially – on the boundary of faces, if \(\mathsf{depth}_2\) is unbounded, there are ways to “skip over” some of the red vertices with additional paths. The ability to skip over can be exploited to push parts of the solution deeper and deeper into a family of concentric cycles without generating any chance to reroute.

shows an example of one of our gadgets. The two yellow vertices are the terminals and the black path is the unique solution. The arrows in the figure indicate in which direction the solution must traverse the edges drawn above the top blue line when going from left to right. Notice that there are indeed \(2\) levels above the top blue line and those \(2\) levels can be used to skip forward and backward. The red vertices along these oriented edges are precisely what forces the entire solution to be unique: Each red vertex has degree \(2\), which means that all of these “subdivided edges” must be used by any solution. Moreover, every second one of the vertices on the top blue line is incident with two of these forced edges while every other vertex along that line is incident to one of the black paths intruding deeper into the lower levels. The construction in is of a “forward” type and has a relatively simple recursive structure.

In fact, we can divide the gadget in into four parts: The black path that goes all the way down to the bottom blue line, the part that is drawn to the left of it, to its right, and inside of it. The left and the right most parts are themselves smaller gadgets of the forward type, while the one in the middle is being entered from the right and also leaves to the right again. This is a gadget of the “backward” type. In we give a schematic illustration of the recursive construction of both types of gadgets. Due to the simple inductive construction, proving that these gadgets possess the desired properties is surprisingly straightforward.

2 Preliminaries↩︎

We introduce basic concepts as well as more advanced ideas from the toolkit of graph minors.

2.1 Basics↩︎

We open with a short array of definitions for commonly used concepts and notation. By \(\mathbb{N}\) we denote the set of non-negative integers. Given any two integers \(a,b\in\mathbb{N}\), we write \([a,b]\) for the set \(\{z\in\mathbb{N} ~\!\colon\!~ a\leq z\leq b\}.\) Notice that the set \([a,b]\) is empty whenever \(a>b.\) For any positive integer \(c\) we set \([c]\mathrel{\vcenter{:}}= [1,c].\)

2.1.0.1 Treewidth.

A tree-decomposition for a graph \(G\) is a pair \((T,\beta)\) such that \(T\) is a tree, \(\beta\colon V(T)\to 2^{V(G)}\) assigns to each node of \(T\) a subset of the vertices of \(G\) known as a bag, \(\bigcup_{t\in V(T)}G[\beta(t)] = G\), and for each \(v\in V(G)\), the set \(\{ t\in V(T) \mid v\in\beta(t) \}\) is connected. The width of \((T,\beta)\) is defined as \(\max_{t\in V(T)} |\beta(t)|-1\).

The treewidth of a graph \(G\), denoted by \(\mathsf{tw}(G)\), is the smallest integer \(k\) such that \(G\) has a tree-decomposition of width at most \(k\).

2.1.0.2 Red-minors and bidimensionality.

Let \(H\) and \(G\) be graphs. A minor model of \(H\) in \(G\) is a family of connected subgraphs \(\{ G_v\}_{v \in V(H)} \cup \{ G_e\}_{e \in E(H)}\) of \(G\) such that

1. \(V(G_v) \cap V(G_u) = \emptyset\) for all \(u \neq v \in V(H)\),

2. \(|V(G_u) \cap V(G_{uv})| = 1\) for all \(uv \in E(G)\),

3. \(V(G_u) \cap V(G_{e}) = \emptyset\) if \(u \notin e\) for all \(u \in V(G)\) and \(e \in E(G)\),

4. \(G_e\) is a path in \(G\) for every \(e \in E(G)\), and

5. \(G_{e}\) and \(G_{e'}\) are internally vertex-disjoint for all \(e \neq e' \in E(G)\).

In case \(G_e\) is isomorphic to \(K_2\) we do note require \(G_e\) to be part of the model explicitly. This also means that \(\{ G_v\}_{v \in V(H)}\) may be a minor model of \(H\) in \(G\) if for all \(uv \in E(G)\), there is an edge in \(G\) between \(V(G_u)\) and \(V(G_v)\). Most of the time we will be working with this simpler version of a model, but sometimes it will be convenient to provide explicit models for edges.

An annotated graph \((H,R_H)\) is a red-minor of an annotated graph \((G,R_G)\) if there exists a minor-model \(\{ G_v\}_{v\in V(H)}\) of \(H\) in \(G\) such that \(R_G \cap V(G_v) \neq \emptyset\) for all \(v\in R_H\).

The bidimensionality of an annotated graph \((G,R)\), denoted by \(\mathsf{bidim}(G,R)\), is the largest integer \(k\) such that there exists \((\Gamma_k,V(\Gamma_k))\) as a red-minor in \((G,R)\) where \(\Gamma_k\) denotes the \((k \times k)\)-grid.

2.1.0.3 Paths, linkages, and vitality.

A linkage \(\mathcal{L}\) in a graph \(G\) is a set of pairwise vertex-disjoint paths. Given the set \(T \subseteq V(G)\) of endpoints the endpoints of the paths in \(\mathcal{L}\), we say that \(\mathcal{L}\) a \(T\)-linkage. Based on \(T\), we define the pattern of \(\mathcal{L}\) as \(\tau(\mathcal{L}) \mathrel{\vcenter{:}}= \{\{s,t\} \mid \text{ there is }L\in \mathcal{L}\text{ with endpoints } s \text{ and } t\}\). In some cases, we are already given a set \(\mathcal{T} = \{ (s_i,t_i) \mid i\in[k]\}\) of terminal pairs. In such a situation, we say that a linkage \(\mathcal{L}\) is a \(\mathcal{T}\)-linkage if \(|\mathcal{L}| = k\) and for every \(i\in[k]\) there is a path \(L \in \mathcal{L}\) with endpoints \(s_i\) and \(t_i\).

A linkage \(\mathcal{L}\) in a graph \(G\) is said to be vital if \(V(\mathcal{L}) = V(G)\) and there does not exist a linkage \(\mathcal{L}' \neq \mathcal{L}\) in \(G\) with the same pattern.

We say that a path \(P\) in \(G\) is internally disjoint from a set \(X \subseteq V(G)\) if \(V(P) \cap X\) does not contain any vertex of \(P\) that is not an endpoint vertex. Given a graph \(G\) and two subsets \(A, B \subseteq V(G)\), an \(A\)-path in \(G\) is a path with both endpoints in \(A\) and internally disjoint from \(A\), and an \(A\)-\(B\)-path is a path with one endpoint in \(A\), the other in \(B\), and internally disjoint from \(A \cup B\). An \(A\)-\(B\)-linkage in \(G\) is a linkage consisting of \(A\)-\(B\) paths. If \(H\) is a subgraph of \(G\), an \(H\)-path is a \(V(H)\)-path of length at least one with no edge in \(E(H)\).

A core result on graphs with vital linkages is the main theorem of Graph Minors XXI by Robertson and Seymour [34] stating that a graph with a vital linkage \(\mathcal{L}\) must have treewidth bounded in some function depending only on \(|\mathcal{L}|\). We state here the recent result of Cavallaro, Gorsky, Kreutzer, Thilikos, and Wiederrecht [16] which provides almost optimal bounds for the treewidth of a graph with a vital linkage.

2.1.0.4 Surfaces.

By a surface we mean a compact \(2\)-dimensional manifold \(\Sigma\) with or without boundary. Let \(X \subseteq \Sigma\). The boundary and interior of \(X\) will be denoted \(\mathsf{bd}(X)\) and \(\mathsf{int}(X)\), respectively. The topological closure of \(X\) is denoted by \(\mathsf{cl}(X)\). If \(\Sigma\) is a surface with boundary then we refer to the connected components of \(\mathsf{bd}(\Sigma)\) as its cuffs.

Let \(\gamma \mathrel : [0,1]_{\mathbb{R}}\to \Sigma\) be continuous and injective on \([0,1[_{\mathbb{R}}\). We say that the image \(\gamma([0,1]_{\mathbb{R}})\) of \(\gamma\) is a curve in \(\Sigma\) and \(\gamma(0),\gamma(1)\) are its endpoints. A curve is closed if its endpoints agree. A curve with both endpoints on the boundary of \(\Sigma\) is called a boundary curve.

Two curves \(C, C' \subseteq \Sigma\) are homeomorphic if there is a homeomorphism \(h \mathrel : \Sigma \rightarrow \Sigma\) which maps \(C\) to \(C'\). \(C\) and \(C'\) are homotopic if there is a continuous function \(f \mathrel : \Sigma \times [0,1]_{\mathbb{R}} \rightarrow \Sigma\) such that \(f(x, 0) = C(x)\) and \(f(x, 1) = C'(x)\) and for every \(t\in [0,1]_{\mathbb{R}}\) the function \(f_t(x)\mathrel{\vcenter{:}}= f(x,t)\) maps the boundary of \(\Sigma\) to the boundary of \(\Sigma\). We call \(f\) a homotopy. Homotopy induces an equivalence relation on the set of curves on a surface \(\Sigma\). We refer to the equivalence classes of homotopy as homotopy classes and to the class containing a curve \(C \subseteq \Sigma\) as its homotopy type.

We will require the following lemma on the number of homotopy types.

Let \(\Sigma\) be a connected surface. A curve \(C \subseteq \Sigma\) is contractible if one of the components of \(\Sigma - C\) is homeomorphic to an open disc. Otherwise it is non-contractible.

2.2 Tools more specific to graph minor structure theory↩︎

We continue by briefly introducing some key concepts for handling the general structure of \(H\)-minor-free graphs. The definitions we introduce here originate fromt he work of Robertson and Seymour [45]. They were later refined by Kawarabayashi, Thomas, and Wollan [46] and then adopted and reiterated by several authors (see for example [47]–[50]).

2.2.0.1 Brambles.

Let \(G\) be a graph. A bramble in \(G\) is a collection of connected subgraphs \(\mathcal{B}\) of \(G\) such that for all \(B_1,B_2 \in \mathcal{B}\) either \(V(B_1) \cap V(B_2) \neq \emptyset\) or there exists an edge with one end in \(B_1\) and the other in \(B_2\). A hitting set for a bramble \(\mathcal{B}\) is a set \(S \subseteq V(G)\) such that \(S \cap V(B) \neq \emptyset\) for all \(B \in \mathcal{B}\). The order of a bramble \(\mathcal{B}\) is the minimum size of a hitting set for \(\mathcal{B}\).

2.2.0.2 Separations and tangles.

Let \(G\) be a graph and \(k\) be a positive integer. A separation of \(G\) is a pair \((A,B)\) such that \(A,B \subseteq V(G)\), \(A -\cup B = V(G)\), and there is no edge with one end in \(A \setminus B\) and the other in \(B \setminus A\). The order of a separation \((A,B)\) of \(G\) is defined as \(|A \cap B|\). We denote by \(\mathcal{S}_k(G)\) the collection of all separations \((A,B)\) of order less than \(k\) in \(G\).

An orientation of \(\mathcal{S}_k(G)\) is a set \(\mathcal{O}\) such that for all \((A,B)\in\mathcal{S}_k(G)\) exactly one of \((A,B)\) and \((B,A)\) belongs to \(\mathcal{O}\). A tangle of order \(k\) in \(G\) is an orientation \(\mathcal{T}\) of \(\mathcal{S}_k(G)\) such that for all \((A_1,B_1),(A_2,B_2),(A_3,B_3)\in\mathcal{T}\), it holds that \(G[A_1]\cup G[A_2]\cup G[A_3]\neq G\). If \(\mathcal{T}\) is a tangle and \((A,B)\in\mathcal{T}\) we call \(A\) the small side and \(B\) the big side of \((A,B)\).

Let \(G\) be a graph and \(\mathcal{T}\) and \(\mathcal{D}\) be tangles of \(G\). We say that \(\mathcal{D}\) is a truncation of \(\mathcal{T}\) if \(\mathcal{D}\subseteq\mathcal{T}\).

Let \(G\) and \(H\) be graphs as well as \(\mathcal{T}\) be a tangle in \(G\). We say that a minor-model \(\mu\) of \(H\) in \(G\) is controlled by \(\mathcal{T}\) if there does not exist a separation \((A,B)\in\mathcal{T}\) of order less than \(|V(H)|\) and an \(x \in V(H)\) such that \(\mu(x)\subseteq A\setminus B\).

Let \(\mathcal{T}\) be a tangle of order at least \(1\) in \(G\). The \(\mathcal{T}\)-big component of \(G\) is the unique component \(J\) of \(G\) such that \(V(J) \subseteq B\) for all \((A,B) \in \mathcal{T}\). where \(A \cap B = \emptyset\).

2.2.0.3 Meshes.

Let \(n,m\) be integers with \(n,m\geq 2\). A \((n\times m)\)-mesh is a graph \(M\) which is the union of paths \(M=P_1\cup\cdots\cup P_n\cup Q_1\cup \cdots \cup Q_m\) where

• \(P_1,\cdots,P_n\) are pairwise vertex-disjoint, and \(Q_1,\cdots,Q_m\) are pairwise vertex-disjoint.

• for every \(i\in [n]\) and \(j\in [m]\), the intersection \(P_i\cap Q_j\) induces a path,

• each \(P_i\) is a \(V(Q_1)\)-\(V(Q_m)\)-path intersecting the paths \(Q_1,\cdots Q_m\) in the given order, and each \(Q_j\) is a \(V(P_1)\)-\(V(P_m)\)-path intersecting the paths \(P_1,\cdots, P_h\) in the given order.

We say that the paths \(P_1,\cdots,P_n\) are the horizontal paths, and the paths \(Q_1,\cdots,Q_m\) are the vertical paths. The union \(P_{1} \cup P_{n} \cup Q_{1} \cup Q_{m}\) is a cycle called the perimeter of \(M\). The unique cycle in the union \(P_{i} \cup P_{i+1} \cup Q_{j} \cup Q_{j+1}\), where \(i \in [n - 1]\) and \(j \in [m - 1]\), is called a brick of \(M\). A mesh \(M'\) is a submesh of a mesh \(M\) if every horizontal (vertical) path of \(M'\) is a subpath of a horizontal (vertical) path \(M\), respectively. We write \(n\)-mesh as a shorthand for an \((n \times n)\)-mesh.

Let \(r \in \mathbb{N}\) with \(r\geq 3\), let \(G\) be a graph, and \(M\) be an \(r\)-mesh in \(G\). Let \(\mathcal{T}_M\) be the orientation of \(\mathcal{S}_r\) such that for every \((A,B)\in\mathcal{T}_M\), the set \(B\setminus A\) contains the vertex set of both a horizontal and a vertical path of \(M\), we call \(B\) the \(M\)-majority side of \((A,B)\). Then \(\mathcal{T}_M\) is the tangle induced by \(M\). If \(\mathcal{T}\) is a tangle in \(G\), we say that \(\mathcal{T}\) controls the mesh \(M\) if \(\mathcal{T}_M\) is a truncation of \(\mathcal{T}\).

The significance of meshes lies in the fact that every mesh has large treewidth and, reversely, every graph of large treewidth must contain a big mesh. This theorem is originally due to Robertson and Seymour [3] but we state here the polynomial version of Chuzhoy and Tan [52].

2.2.0.4 Paintings in surfaces.

A painting in a surface \(\Sigma\) is a pair \(\Gamma = (U,N)\), where \(N \subseteq U \subseteq \Sigma\), \(N\) is finite, \(U \setminus N\) has a finite number of arcwise-connected components, called cells of \(\Gamma\), and for every cell \(c\), the closure of \(c\), denoted by \(\overline{c}\), is a closed disc where \(N_\Gamma(c) \mathrel{\vcenter{:}}= \overline{c} \cap N \subseteq \mathsf{bd}(\overline{c})\). If \(|N_\Gamma(c)| \geq 4\), the cell \(c\) is called a vortex. We further let \(N(\Gamma) \mathrel{\vcenter{:}}= N\), let \(U(\Gamma) \mathrel{\vcenter{:}}= U\), and let \(C(\Gamma)\) be the set of all cells of \(\Gamma\).

Any given painting \(\Gamma = (U,N)\) defines a hypergraph with \(N\) as its vertices and the set of closures of the cells of \(\Gamma\) as its edges. Accordingly, we call \(N\) the nodes of \(\Gamma\).

2.2.0.5 \(\Sigma\)-renditions.

Let \(G\) be a graph and \(\Sigma\) be a surface. A \(\Sigma\)-rendition of \(G\) is a triple \(\rho = (\Gamma, \sigma, \pi)\), where

• \(\Gamma\) is a painting in \(\Sigma\),

• for each cell \(c \in C(\Gamma)\), \(\sigma(c)\) is a subgraph of \(G\), and

• \(\pi \colon N(\Gamma) \to V(G)\) is an injection,

such that

R1

\(G = \bigcup_{c \in C(\Gamma)}\sigma(c)\),

R2

for all distinct \(c,c' \in C(\Gamma)\), the graphs \(\sigma(c)\) and \(\sigma(c')\) are edge-disjoint,

R3

\(\pi(N_\Gamma(c)) \subseteq V(\sigma(c))\) for every cell \(c \in C(\Gamma)\), and

R4

for every cell \(c \in C(\Gamma)\), we have \(V(\sigma(c) \cap \bigcup_{c' \in C(\Gamma) \setminus \{ c \}} (\sigma(c'))) \subseteq \pi(N_\Gamma(c))\).

We write \(N(\rho)\) for the set \(N(\Gamma)\), let \(N_\rho(c) = N_\Gamma(c)\) for all \(c \in C(\Gamma)\), and similarly, we lift the set of cells from \(C(\Gamma)\) to \(C(\rho)\). If it is clear from the context which \(\rho\) is meant, we will sometimes simply write \(N(c)\) instead of \(N_\rho(c)\), and if the \(\Sigma\)-rendition \(\rho\) for \(G\) is understood from the context, we usually identify the sets \(\pi(N(\rho))\) and \(N(\rho)\) along \(\pi\) for ease of notation.

2.2.0.6 Blank renditions.

Let \(\rho\) be a \(\Sigma\)-rendition of an annotated graph \((G,R)\). If \[\pi(N(\rho)) \cup \bigcup \{ V(\sigma(c)) \colon c \in C(\rho) \text{ and } c \text{ is not a vortex}\}\] is disjoint from \(R\), we call \(\rho\) a blank rendition (of \((G,R)\)).

2.2.0.7 Societies.

Let \(\Omega\) be a cyclic ordering of the elements of some set which we denote by \(V(\Omega)\). A society is a pair \((G,\Omega)\), where \(G\) is a graph and \(\Omega\) is a cyclic ordering with \(V(\Omega)\subseteq V(G)\). For a given set \(S \subseteq V(\Omega)\) a vertex \(s \in S\) is an endpoint of \(S\) if there exists a vertex \(t \in V(\Omega) \setminus S\) that immediately precedes or succeeds \(s\) in \(\Omega\). We call \(S\) a segment of \(\Omega\) if \(S\) has two or less endpoints.

Let \((G,\Omega)\) be a society and let \(\Sigma\) be a surface with one boundary component \(B\) homeomorphic to the unit circle. A rendition of \((G,\Omega)\) in \(\Sigma\) is a \(\Sigma\)-rendition \(\rho\) of \(G\) such that the image under \(\pi_{\rho}\) of \(N(\rho) \cap B\) is \(V(\Omega)\) and \(\Omega\) is one of the two cyclic orderings of \(V(\Omega)\) defined by the way the points of \(\pi_{\rho}(V(\Omega))\) are arranged in the boundary \(B\).

2.2.0.8 Traces of paths and cycles.

Let \(\rho\) be a \(\Sigma\)-rendition of a graph \(G\). For every cell \(c \in C(\rho)\) with \(|N_\rho(c)| = 2\), we select one of the components of \(\mathsf{bd}(c) - N_\rho(c)\). This selection will be called a tie-breaker in \(\rho\), and we assume that every rendition comes equipped with a tie-breaker.

Let \(G\) be a graph and \(\rho\) be a \(\Sigma\)-rendition of \(G\). Let \(Q\) be a cycle or path in \(G\) that uses no edge of \(\sigma(c)\) for every vortex \(c \in C(\rho)\). We say that \(Q\) is grounded if either \(P\) is a path with both endpoints in \(N(\rho)\), or \(Q\) is a cycle that uses edges of \(\sigma(c_{1})\) and \(\sigma(c_{2})\) for two distinct cells \(c_{1}, c_{2} \in C(\rho).\) If \(Q\) is grounded we define the trace of \(Q\) as follows. Let \(P_1,\dots,P_k\) be distinct maximal subpaths of \(Q\) such that \(P_i\) is a subgraph of \(\sigma(c)\) for some cell \(c\). Fix \(i \in [k]\). The maximality of \(P_i\) implies that its endpoints are \(\pi(n_1)\) and \(\pi(n_2)\) for distinct nodes \(n_1,n_2 \in N(\rho)\). If \(|N_\rho(c)| = 2\), let \(L_i\) be the component of \(\mathsf{bd}(c) - \{ n_1,n_2 \}\) selected by the tie-breaker, and if \(|N_\rho(c)| = 3\), let \(L_i\) be the component of \(\mathsf{bd}(c) - \{ n_1,n_2 \}\) that is disjoint from \(N_\rho(c)\). We define \(L_i'\) by pushing \(L_i\) slightly so that it is disjoint from all cells in \(C(\rho)\), while maintaining that the resulting curves intersect only at a common endpoint. The trace of \(Q\) is defined to be the curve \(\gamma\) obtained from \(\bigcup_{i\in[k]} L_i'\) by slightly pushing it in order to ensure that \(\gamma\) intersects the painting of \(\rho\) in nodes only. If \(Q\) is a cycle, its trace thus the homeomorphic image of the unit circle, and otherwise, it is an arc in \(\Sigma\) with both endpoints in \(N(\rho)\).

2.2.0.9 Aligned discs and grounded subgraphs.

Let \(G\) be a graph and let \(\rho = (\Gamma, \sigma, \pi)\) be a \(\Sigma\)-rendition of \(G\). We say that a 2-connected subgraph \(H\) of \(G\) is grounded (in \(\rho\)) if every cycle in \(H\) is grounded and no vertex of \(H\) is drawn by \(\Gamma\) in a vortex of \(\rho\). A disc in \(\Sigma\) is called \(\rho\)-aligned if its boundary only intersects \(\Gamma\) in nodes. If \(H\) is planar, we say that it is flat in \(\rho\) if there exists a \(\rho\)-aligned disc \(\Delta \subseteq \Sigma\) which contains all cells \(c \in C(\rho)\) with \(E(\sigma(c)) \cap E(H) \neq \emptyset\) and \(\Delta\) does not contain any vortices of \(\Gamma\).

For any \(\rho\)-aligned disc \(\Delta\), we call the subgraph of \(G\) that is drawn by \(\Gamma\) onto \(\Delta\) the crop of \(G\) by \(\Delta\) (in \(\rho\)). Furthermore, the restriction \(\delta'\) of \(\rho\) by \(\Delta\) is defined as the \(\Delta\)-rendition that consists of the restriction of both \(\Gamma\), \(\sigma\), and \(\pi\) to \(\Delta\).

This allows to define a society associated to \(\Delta\) as follows. Let \(V(\Omega_{\Delta})\) be the set of all vertices whose corresponding nodes are drawn in the boundary of \(\Delta\) and let \(\Omega_{\Delta}\) be the cyclic ordering of \(V(\Omega_{\Delta})\) obtained by traversing along the boundary of \(\Delta\) in the anticlockwise direction. Now, let \(G_{\Delta}\) be the crop of \(G\) by \(\Delta\). We call the society \((G_{\Delta}, \Omega_{\Delta})\) the \(\Delta\)-society (in \(\rho\)). If \(\rho\) is clear from the context, we do not mention it. We also call the restriction of \(\rho\) by \(\Delta\), the restriction of \(\rho\) to \((G_{\Delta}, \Omega_{\Delta})\).

Let \(\mathcal{P}\) be an \(X\)-\(Y\)-linkage in \(G\) such that \(X \cap V(G_{\Delta}) \subseteq V(\Omega_{\Delta})\) and \(Y \subseteq V(G_{\Delta})\) and assume that each path in \(\mathcal{P}\) is grounded in \(\rho\). Then we define the \(\Delta\)-truncation (in \(\rho\)) of \(\mathcal{P}\) to be the \(V(\Omega_{\Delta})\)-\(Y\)-linkage in \(G_{\Delta}\) which consists of the minimal \(V(\Omega_{\Delta})\)-\(Y\)-subpaths of the paths in \(\mathcal{P}.\)

Let \(\rho\) be a rendition of a society \((G, \Omega)\) in the disc \(\Delta.\) Given a cycle \(C \subseteq G\) that is grounded in \(\rho\) we define the \(C\)-disc (in \(\rho\)) as the unique \(\rho\)-aligned disc \(\Delta' \subseteq \Delta\) bounded by the trace of \(C\) in \(\rho.\) We also use the terms \(C\)-society (in \(\rho\)) to denote the \(\Delta'\)-society in \(\rho\) and \(C\)-truncation (in \(\rho\)) to denote the \(\Delta'\)-truncation in \(\rho\) of an appropriately defined linkage in \(G.\)

2.2.0.10 Inner and outer graphs of cycles and aligned curves.

Let \(G\) be a graph with a \(\Sigma\) -rendition \(\rho\) and let \(\gamma\) be a (closed) curve in \(\Sigma\), We say that \(\gamma\) is \(\rho\)-aligned if it intersects \(\rho\) in nodes only. That is, \(\gamma\) must be disjoint from all cells of \(\rho\).

Let \((G, \Omega)\) be a society with a \(\Sigma\)-rendition \(\rho.\) Further, let \(C\) be a grounded cycle or a \(\rho\)-aligned closed curve whose trace bounds a disc \(\Delta_C\) and the \(\Delta_C\)-society \((G', \Omega').\) We call \(G' \cup C\) the inner graph of \(C\) (in \(\rho\)) and call \(G'\) itself the proper inner graph of \(C\) (in \(\rho\)). Let \(B = \pi(N(\rho) \cap \mathsf{bd}(\Delta_C)).\) We define the proper outer graph of \(C\) (in \(\rho\)) as \(G'' \mathrel{\vcenter{:}}= G[B \cup (V(G) \setminus V(G'))]\) and call \(G'' \cup C\) the outer graph of \(C\) (in \(\rho\)).

2.2.0.11 Transactions in societies.

Let \((G, \Omega)\) be a society. A transaction in \((G, \Omega)\) is an \(A\)-\(B\)-linkage for disjoint segments \(A, B\) of \(\Omega\) consisting of \(V(\Omega)\)-paths. The inclusion-wise minimal segments \(X\) and \(Y\) of \(\Omega\) for which \(\mathcal{P}\) is an \(X\)-\(Y\)-linkage are called the end segments of \(\mathcal{P}\) in \((G, \Omega)\).

2.2.0.12 Cylindrical renditions.

A rendition of a society \((G, \Omega)\) in the disc with a unique vortex \(c_{0}\) is called a cylindrical rendition of \((G, \Omega)\) around \(c_{0}\).

If \((G, \Omega)\) is a society with a cylindrical rendition \(\rho\) around a vortex \(c_{0}\) and \(\mathcal{P}\) is a transaction in \((G, \Omega)\), we call \(\mathcal{P}\) exposed if for every path \(p \in \mathcal{P}\) there exists an edge \(e \in E(P) \cap \sigma(c_{0})\).

2.2.0.13 Nests and radial linkages.

Let \(\rho\) be a rendition of a society \((G, \Omega)\) in a disc \(\Delta\). A nest (in \(\rho\)) is a set of disjoint cycles \(\mathcal{C} = \{ C_{1}, \ldots, C_{s} \}\) in \(G\) such that each of them is grounded in \(\rho\), and if \(\Delta_{i}\) is the \(C_{i}\)-disc for \(i \in [s]\), then every vortex of \(\rho\) is contained in \(\Delta_{1}\) and \(\Delta_{1} \subseteq \ldots \subseteq \Delta_{s} \subseteq \Delta\). We call \(C_{1}\) the inner cycle of \(\mathcal{C}\) and \(C_{s}\) the outer cycle of \(\mathcal{C}\) respectively. Moreover, we call a \(V(\Omega)\)-\(V(C_{1})\)-linkage \(\mathcal{R}\) a radial linkage (in \(\rho\)) for \(\mathcal{C}\) if all paths in \(\mathcal{R}\) are grounded in \(\rho\) and internally disjoint from \(V(\Omega).\)

If \((G, \Omega)\) is a society with a nest \(\mathcal{C}\) in a rendition \(\rho\) of \((G, \Omega)\) in a disc, we say that a radial linkage \(\mathcal{R}\) for \(\mathcal{C}\) is orthogonal to \(\mathcal{C}\) if for all \(C \in \mathcal{C}\) and all \(R \in \mathcal{R}\) the graph \(C \cap R\) is a path. Similarly, we say that a transaction \(\mathcal{P}\) in \((G, \Omega)\) is orthogonal to \(\mathcal{C}\) if for all \(C \in \mathcal{C}\) and all \(P \in \mathcal{P}\) the graph \(C \cap P\) consists of exactly two paths.

2.2.0.14 Depth of vortices.

Let \(G\) be a graph and \(\rho\) be a \(\Sigma\)-rendition of \(G\) with a vortex cell \(c_0.\) Notice that \(c_0\) defines a society \((\sigma(c_0), \Omega_{c_0})\), where \(V(\Omega_{c_0})\) is the set of vertices of \(G\) corresponding \(N_\rho(c_0).\) The ordering \(\Omega_{c_{0}}\) is obtained by traversing along the boundary of the closure of \(c_0\) in anti-clockwise direction. We call \((\sigma(c_0),\Omega_{c_0})\) as obtained above the vortex society of \(c_0.\)

We define the depth of a society \((G, \Omega)\) as the maximum cardinality of a transaction in \((G, \Omega).\) The depth of the vortex \(c_{0}\) is thereby defined as the depth of its vortex society.

Given a \(\Sigma\)-rendition \(\rho\) with vortices, we define the breadth of \(\rho\) as the number of vortex cells of \(\rho\) and the depth of \(\rho\) as the maximum depth of its vortex societies.

2.3 The structure of annotated graphs of small bidimensionality↩︎

Next, we introduce the structure theorem of Gorsky, Protopapas, and Wiederrecht [6] establishing polynomial bounds for the structure of annotated graphs of small bidimensionality. We slightly modify the original statement by removing some amount of information that will not be necessary for the purpose of this paper.

3 The local structure of annotated graphs with small depth\(_2\)↩︎

The goal of this section is a further refinement of towards a local structure theorem for annotated graphs of small \(\mathsf{depth}_2\). To fully express our structural main theorem, we introduce some additional concepts as it is now necessary to further analyse the structure of vortices.

3.0.0.1 Linear societies.

In the following we consider a slightly different concept of societies. Let \((G,\Omega)\) be a society and \(x \in V(\Omega)\). The \(x\)-linearisation of \(\Omega\) is the linear order \(\Lambda_{\Omega,x}\) of \(V(\Omega)\) where \(x\) is the minimum, the maximum is \(z \in V(\Omega)\) which is the predecessor of \(x\) in \(\Omega\) and \(a,b \in V(\Omega)\) satisfy \(a \leq_{\Lambda_{\Omega,x}} b\) if and only if there exists a segment \(S\) of \(\Omega\) with ends \(a\) and \(b\) that does not contain \(x\) in its interior. A linearisation of \(\Omega\) is a linear order \(\Lambda\) of \(V(\Omega)\) such that there is \(x \in \Omega\) for which \(\Lambda = \Lambda_{\Omega,x}\).

It turns out that in most situations, it does not make a huge difference when considering a cyclic order or a linearisation of it for the sake of structure theory. See [48] for some discussion on the topic. Thus, in the following a linear society is a pair \((G,\Lambda)\) where \((G,\Omega)\) is a society and \(\Lambda\) is a linearisation of \(\Omega\). We will drop the suffix “linear” in most cases and only stress the linearity of our societies where necessary. However, we strive to use \(\Lambda\) for linear societies and \(\Omega\) for regular societies. We also lift the notion of segments from cyclic orders to linear orders in the natural way.

A linear society \((G,\Lambda)\) has a rendition in a disc if the society \((G,\Omega)\) such that \((G,\Lambda)\) is a linearisation of \((G,\Omega)\) has a rendition in a disc. Similarly, we lift all other notions relating to societies and renditions to linear societies by simply requiring the property to hold for \((G,\Omega)\) where \((G,\Lambda)\) is a linearisation.

3.0.0.2 Candles and cropped societies.

Let \((G,\Lambda)\) be a linear society.

Let \(R \subseteq V(G)\). An \(R\)-candle is a pair \(P,Q\) of vertex-disjoint paths where the endpoints of \(P\) are \(x_1, x_2 \in V(\Lambda)\), \(Q\) has an endpoint \(y_1 \in V(\Lambda)\) and one endpoint in \(R\) – we allow those endpoints to coincide – and where \(x_1 , y_1\), and \(x_2\) occur in \(\Lambda\) in the order listed. See for an example. We call the vertices \(x_1,y_1\), and \(x_2\) the roots of the candle and the endpoint of \(Q\) in \(R\) its flame. Moreover, \(Q\) is referred to as the candle stick and we usually write \(\mathcal{X} = \{ P,Q\}\) for an \(R\)-candle. In slight abuse of notation, we sometimes identify \(\mathcal{X}\) and the graph \(P \cup Q\).

Let \(S\) be a segment of \(\Lambda\). We denote by \(\Lambda(S)\) the restriction of \(\Lambda\) to \(S\) where all vertices of \(S\) have the same order in \(\Lambda(S)\) as in \(\Lambda\). The linear society \((G_S,\Lambda(S))\) is the \(S\)-crop of \((G,\Lambda)\) where \(G_S\) is the graph obtained from \(G-(V(\Lambda)\setminus S)\) by deleting all components that do not contain at least one vertex of \(S\).

3.0.0.3 Rooted \(\rho\)-aligned curves.

Let \((G,\Lambda)\) be a society and \(\rho\) be a cylindrical rendition of \((G,\Lambda)\) in a disc \(\Delta\) with vortex \(c_0\). We say that a \(\rho\)-aligned curve \(\gamma\) is rooted if both ends of \(\gamma\) belong to \(V(\Lambda)\) and \(\gamma\) is otherwise disjoint from \(V(\Lambda)\).

If \(\gamma\) is a rooted \(\rho\)-aligned curve, then \(\gamma\) partitions \(\Lambda\) into three possibly empty segments where precisely one of those three segments contains both ends of \(\gamma\). We call this segment the base of \(\gamma\).

Notice that a rooted \(\rho\)-aligned curve together with the boundary of \(\Delta\) decomposes \(\Delta\) into two discs which intersect precisely in \(\gamma\). The base of \(\gamma\) is contained fully in precisely one of those two discs and we refer to this disc as the inner disc of \(\gamma\) while the other disc is the outer disc of \(\gamma\). See for an illustration. The inner graph of a rooted \(\rho\)-aligned curve is the inner graph of the boundary of its inner disc and its outer graph is the inner graph of the boundary of its outer disc.

Let \(\gamma\) be a \(\rho\)-aligned curve. We say that \(\gamma\) is a frontier if:

1. The curve \(\gamma\) can be decomposed into rooted \(\rho\)-aligned curves \(\gamma_1,\dots,\gamma_k\) such that \(\bigcup_{i \in [k]}\gamma_i = \gamma\) and for any two \(i \neq j\), \(\gamma_i \cap \gamma_j\) is either empty or \(|i - j|=1\) and the intersection is a common endpoint.

2. For each \(i\in[k]\), the inner disc of \(\gamma_i\) does not contain any of the \(\gamma_j\), \(j \in [k] \setminus \{ i\}\).

The inner graph of a frontier \(\gamma\) is the union of the inner graphs of the \(\gamma_i\) and the outer graph of \(\gamma\) is the common intersection of all outer graphs of all the \(\gamma_i\). See for an illustration.

3.0.0.4 Candle-free societies.

A set \(R \subseteq V(G)\) is candle-free in \((G,\Lambda)\) if there exists a vortex-free rendition of \((G,\Lambda)\) in a disc and there is no \(R\)-candle in \((G,\Lambda)\).

3.0.0.5 Facial sets in societies.

Let \((G,\Lambda)\) be a linear society where \((G,R)\) is an annotated graph and \(\rho\) be a vortex-free rendition of \((G,\Lambda)\). We say that \(\rho\) is facial if there exists a frontier \(\gamma\) such that

• \(R\) is contained entirely in the outer graph of \(\gamma\), and

• there does not exist a \(V(\gamma)\)-candle in \((G,\Lambda)\).

We say that \(\gamma\) is an ultimate frontier of \((G,\Lambda)\).

3.0.0.6 Shallow renditions.

Let \(k\) be a non-negative integer, \((G,R)\) be an annotated graph and \(\Sigma\) be a surface. We say that a \(\Sigma\)-rendition \(\rho\) of \(G\) is \(k\)-shallow if

1. \(\rho\) is blank, and

2. for each vortex \(v\) of \(\rho\) there exists a linearisation \((\sigma(v),\Lambda_v)\) of its vortex society such that there exists a partition of \(\Lambda_v\) into at most \(k\) segments \(S_1,\dots,S_k\) such that, if we denote by \((G_{S_i},\Lambda_{S_i})\) is the \(S_i\)-crop of \((\sigma(v),\Lambda_v)\) for each \(i \in [k]\),

   • for all \(i \neq j \in[k]\), \(G_{S_i}\) and \(G_{S_j}\), and

   • for all \(i \in [k]\) either \(V(G_{S_i}) \cap R = \emptyset\) – and we call \(S_i\) a deep segment, or \(R \cap V(G_{S_i})\) is facial in \((G_{S_i},\Lambda_{S_i})\) – and we call \(S_i\) a facial segment.

With these definitions, we have everything in place to state our local structure theorem for annotated graphs of small \(\mathsf{depth}_2\).

Notice that the main difference between and is the addition of the condition on \(\rho\) in the third outcome to be shallow. This shallowness is precisely the distinguishing factor between annotated graphs of small \(\mathsf{depth}_2\) and those of bounded bidimensionality: It provides further control about the interaction of the annotation with the vortices.

Our proof for is divided into two major parts.

In Part 1 we investigate the behaviour of candles in societies and establish general structure theorems for situations where candles occur versus situations where candles are absent. We also show that, in the case where we have a society containing a large nest around a single vortex and we sequentially find many disjoint candles, then these candles together with the nest give rise to a large candle mesh which implies that the annotated graph underlying the society has large \(\mathsf{depth}_2\). This is a core observation that will later allow us to bound the number of disjoint candles we can find.

In Part 2, we adapt ideas from the work of Thilikos and Wiederrecht [37] on handling structures rooted at the boundaries of bounded depth vortices to show that each vortex in the outcome of either contains many disjoint candles – implying that the annotated graph has large \(\mathsf{depth}_2\) by using the tools developed in Part 1 – or there exists a small set of vertices whose deletion removes all candles from all vortices. The later outcome will then imply the final structure required to prove .

3.1 Part 1: Placing candles↩︎

We begin with Part 1. Our goal is to establish a sequence of general structural observations on candles in linear societies with underlying annotated graphs. There are several core lemmas we need to extract in this first part, those include:

• establishing a link between the absence of candles and the property of being facial in societies with vortex-free renditions in a disc,

• showing that many candles rooted at the top of a large mesh give rise to a big \(2\)-outer-annotated grid,

• a toolset for routing and redrawing candles under certain conditions, and finally

• proving that any linear society is either facial, has a candle, or is blank, where the last outcome is distinct from the first in the case where the society does not have a vortex-free rendition in a disc.

3.1.0.1 Facial societies.

We start with a somewhat independent result describing the structure of linear societies without \(R\)-candles.

Our main concern towards proving is to understand what the absence of an \(R\)-candle in a society implies if we already know that the society has a vortex-free rendition in a disc. Here, a fundamental theorem from Graph Minors becomes relevant: the Two Paths Theorem.

We will later require the following subroutine for the \(2\)-Disjoint Paths problem.

Let \((G,\Omega)\) be a society. We say that \((G,\Omega)\) has a cross if there exist four distinct vertices \(s_1,s_2,t_1,t_2\) appearing in \(\Omega\) in the order listed together with two vertex-disjoint paths \(P_1\) and \(P_2\) in \(G\) where \(P_i\) joins \(s_i\) and \(t_i\) for each \(i\in[2]\). We also refer to the two paths \(P_1\) and \(P_2\) as a cross of \((G,\Omega)\).

The Two Paths Theorem can be seen as a structural variant of and it is the engine underlying the algorithm.

Indeed, the algorithm from actually finds either a vortex-free rendition in a disc for \((G,\Omega)\) or a cross in \((G,\Omega)\) in linear time.

3.1.0.2 From candles to two red columns.

Before we proceed looking for candles in a vortex, we need to show that these candles ultimately yield want we want. What do we want though? Our goal is to show that whenever \(\mathsf{depth}_2\) is bounded, we can “clean” any vortex by deleting a small set of vertices. Here “cleaning” essentially means the removal of all candles in the vortex. If however, we find many candles, we should be able to find a witness that \(\mathsf{depth}_2\) is large.

To this end, let \(k \geq 1\) be an integer. A \(k\)-candle mesh is an annotated graph obtained from a \((3k \times 3k)\)-mesh \(M\) as follows. Let the vertical paths of \(M\) be \(Q_1,\dots,Q_{3k}\) and the horizontal paths of \(M\) be \(P_1,\dots,P_{3k}\). For each \(i \in [3k]\), let us denote by \(x_i\) the endpoint of \(Q_i\) on \(P_1\). For each \(j\in[k]\) we now add a path \(L_j\) with endpoints \(x_{3(j-1)+1}\) and \(3j\) whose internal vertices are do not belong to \(M\) or any of the other paths added to the graph. Then, for each \(j\in[k]\) we add a path \(B_j\) which is vertex-disjoint from the entire graph as constructed so far except for one of its endpoints – this endpoint is \(x_{3(j-1) + 2}\). For each \(j \in[k]\) let \(r_j\) be the endpoint of \(B_j\) that is not \(x_{3(j-1) + 2}\) and let \(R \mathrel{\vcenter{:}}= \{ r_j \mid j \in [k] \}\). If we let \(H\) be the graph constructed above, then \((H,R)\) is now an annotated graph we call a \(k\)-candle mesh. See for an illustration. We refer to the vertices \(r_j\) as the flames and the paths \(B_j\) as the candle sticks.

3.1.0.3 Taming candles.

With we have enough justification why candles are the correct object to be looking for. Next we require a way to tame the way candles may appear inside of a vortex.

In later stages of our proof we will be confronted with the following situation. We start with a cylindrical rendition \(\rho\) in a disc \(\Delta\) of some society \((G,\Lambda)\) containing a big nest \(\mathcal{C} = \{ C_1,\dots,C_s \}\) around a vortex \(c_0\) of bounded depth. We then select – in a later stage – a rooted \(\rho\)-align curve \(\gamma\) with the goal to capture an \(R\)-candle in the inner graph of \(\gamma\). However, \(\gamma\) does not have to be well behaved with respect to the nest. Let \(\Delta_{\gamma} \subseteq \Delta\) be the inner disc of \(\gamma\) and let \(\rho_{\gamma}\) be the rendition of the inner graph \(G_{\gamma}\) of \(\gamma\) into \(\Delta_{\gamma}\) inherited from \(\rho\). For each \(i\in[n]\), \(C_i \cap G_{\gamma}\) is now either still a cycle, or a collection of disjoint subpaths \(Q\) of \(C_i\) where each such \(Q\) has both endpoints in \(V(\gamma)\) – where \(V(\gamma)\) denotes the set of vertices corresponding to the nodes of \(\rho\) contained in \(\gamma\). Let us call such a subpath \(Q \subseteq C_i\) an arc of \(C_i\).

In a later part of the proof we aim to prove that there is a constant \(x\) such that no subpath of an \(R\)-candle caught in a rooted \(\rho\)-aligned curve starts on the vortex boundary, touches \(C_x\), and then returns to the vortex.

Let \((G,\Lambda)\) be a society and \((G,R)\) be an annotated graph. Moreover, let \(\rho\) be a blank cylindrical rendition of \((G,\Lambda)\) in a disc \(\Delta\) with a nest \(\mathcal{C} = \{ C_1,\dots,C_s \}\) around the vortex \(c_0\). Finally, let \(\gamma\) be a rooted \(\rho\)-aligned curve with base \(S\) and let \((G_{\gamma},\Lambda_{\gamma})\) denote the restriction of \((G,\Lambda)\) to the inner graph of \(\gamma\).

Consider an \(R\)-candle \(\mathcal{X} = \{ P,Q\}\) in \((G_{\gamma},\Lambda_{\gamma})\). We say that such an \(R\)-candle \(\mathcal{X}\) is caught by \(\gamma\). A path \(L \subseteq P \cup Q\) is a \(\mathcal{X}\)-loop if it is grounded and both of its endpoints belong to \(N(c_0)\).

Our next goal is to prove the following lemma.

In order to prove this lemma, we require a first intermediate result on the behaviour of \(\mathcal{X}\)-loops. In the situation of , we say that an \(R\)-candle \(\mathcal{X}\) caught by \(\gamma\) is exhaustive if for every \(\mathcal{X}\)-loop \(L\), if \(i \in [2,s]\) is the largest integer such that \(L \cap C_i \neq \emptyset\), then there exists an \(\mathcal{X}\)-loop \(L'\) which intersects \(C_{i-1}\) and which is contained in the inner graph of the unique closed curve \(\varphi_{L}\) defined by the trace of \(L\) and the boundary of the vortex \(c_0\) that does not contain \(c_0\). See for an illustration. We refer to the disk bounded by \(\varphi_L\) as the \(L\)-centre. We say that any \(\mathcal{X}\)-loop \(L''\) which is contained in the \(L\)-centre is an inner loop of \(L\).

Notice that the proof can actually be turned into an algorithm. This algorithm will touch each of the at most \(||G||\) loops at most \(s\) times – that is once for each cycle of the nest where the loop has its peak. A naive implementation of the “pushing” procedure for a single loop takes \(|G|\) time, so in total we get the following corollary towards our algorithmic application.

We are now ready to proceed with the proof of .

Notice that we have used a non-constructive version of in the proof of . There exists a constructive variant of in the work of Cavallaro, Gorsky, Kreutzer, Thilikos, and Wiederrecht [16]. In order to save on notation, we will not state the full theorem but rather provide a specialisation of this theorem to the \(k\)-Disjoint Paths Problem.

In this context, given an annotated graph \((G,R)\) and an integer \(k\), we say that a vertex \(v \in V(G) \setminus R\) is strongly \((k,R)\)-irrelevant if for every choice of at most \(k\) terminals pairs \(\mathcal{T} = \{(s_1,t_1),\dots,(s_{k'},t_{k'})\}\) where \(s_i,t_i \in R\) for all \(i\in[k']\), \((G,\mathcal{T})\) is a yes-instance of the \(k\)-Disjoint Paths problem if and only if \((G-v,\mathcal{T})\) is a yes-instance of the \(k\)-Disjoint Paths problem. The original version of the theorem gives an even stronger conclusion, allowing for up to \(d\) additional terminals that are “floating”, that is unspecified. This problem is known as the \((k,d)\)-Folio problem and here we only state the version where \(d=0\). See [16] for more information.

With and , the proof of can be made constructive and thus, such candles can be found efficiently.

3.1.0.4 Arranging candles into a mesh.

In the previous steps we have shown how to find candles and how to enforce some additional structure. Before we are able to move on to the next step, we need to show that in the case where we have many consecutive candles rooted on a society with a large nest, there exists a large candle mesh.

Let \((G,\Lambda)\) be a society with a cylindrical rendition \(\rho\) and vortex \(c_0\). We say that a curve \(\gamma\) is semi \(\rho\)-aligned if it can be divided into three – possibly empty – pieces: Two of them are \(\rho\)-aligned curves with one end in \(\Lambda\), while the last starts and ends on points of \(N(c_0)\) and is otherwise entirely contained in the interior of \(c_0\). This last part is called the inner piece of \(\gamma\).

For a semi \(\rho\)-aligned curve, the vortex society \(\Lambda_{c_0}\) can be partitioned into two segments:

1. \(S_1\subseteq V(\Lambda_{c_0})\) such that, if \(\gamma'\) is the rooted \(\rho\)-aligned curve obtained from \(\gamma\) by replacing the inner piece of \(\gamma\) with any \(\rho\)-aligned curve \(\gamma''\) that intersects \(\rho\) precisely in \(S_1\), then the inner disc of \(\gamma'\) does not contain \(c_0\), and

2. \(S_2 \mathrel{\vcenter{:}}= V(\Lambda_{c_0}) \setminus S_1\).

We call the curve \(\gamma'\) the projection of \(\gamma\) and \(S_1\) the inner segment of \(\gamma\). If there does not exist a path in \(\sigma(c_0)\) from \(S_1\) to \(S_2\) we say that \(\gamma\) is a proper semi \(\rho\)-aligned curve. The inner graph of a proper semi \(\rho\)-aligned curve \(\gamma\) is defined as the union of the inner graph of \(\gamma'\) together with all components of \(\sigma(c_0)\) that contain a vertex from \(S_1\).

Notice that whenever we consider a proper semi \(\rho\)-aligned curve \(\gamma\), we may delete everything in \(\sigma(c_0)\) that does not belong to the inner graph of \(\gamma\), resulting in the society \((G',\Lambda)\). If we then shrink the vortex \(c_0\) in order to be entirely in the interior of \(\gamma\), we obtain a cylindrical rendition \(\rho'\) of \((G',\Lambda)\) from \(\rho\) where \(\gamma\) is a rooted \(\rho'\)-aligned curve whose inner disc contains the vortex \(c_0'\) of \(\rho'\). Notice further that any nest in \(G\) and \(\rho\) around \(c_0\) remains a nest around the vortex of \(\rho'\) in \(G'\). This gives us the right to treat proper semi \(\rho\)-aligned curves as rooted \(\rho\)-aligned curves by implicitly referring to the graph \(G'\) and the rendition \(\rho'\). Hence, any definition and result for rooted \(\rho\)-aligned curves referring only to their inner graphs can be lifted to also apply to proper semi \(\rho\)-aligned curves.

3.2 Part 2: Cleaning a vortex↩︎

We are now ready to move on to the second step. Our goal is to prove that, whenever we are given a society with a large nest in a cylindrical rendition around some vertex, we either find a large candle mesh – which by implies that the \(\mathsf{depth}_2\) is big – or are able to delete a small set of vertices to remove all candles from the vortex. Moreover, we wish to further strengthen this in order to be able to apply to say that those parts of the vortex which do not allow for a cross are entirely facial while those which do contain a cross must be blank.

3.2.0.1 Two types of candle-free societies.

Towards this goal, we first start by proving a companion lemma to that allows to distinguish candle-free societies into two types.

Given a society \((G,\Lambda)\) where \((G,R)\) is an annotated graph, we say that \((G,\Omega)\) has access to a red vertex if there exists an \(R\)-\(V(\Lambda)\)-path in \(G\). The core observation is that, in the presence of a non-empty nest, a cross together with access to a red vertex imply the existence of a candle.

A core feature of the proof of is that we actually do not need access to the entire nest to make it work. At its core the main argument we use is that the three paths \(P_1\) and \(P_2\) of the cross as well as the path \(Q''\) connecting \(R\) to \(V(\Lambda)\) are all connected by a subpath of \(C_1\). This means that we may use the same proof to derive a slightly stronger variant of which is the key tool we are after. We state the stronger variant below but omit its almost identical but slightly more tedious proof.

Notice that the running time of \(\mathbf{O}(|G|^5)\) in is really due to our greedy way to find an \(R\)-candle by guessing all four endpoints of the two paths. The running time can actually be sped up by a lot simply through using and the insights gained through the proof of . Given a society with a nest around a vortex, we can check for the existence of a cross in linear time. If there is a cross and the society has access to red, then we easily create an \(R\)-candle out of the cross. Otherwise either the society does not have access to red, or it has a vortex-free rendition in a disc. In the later case, the proof of shows that in order to check for the existence of an \(R\)-candle we can use a simple auxiliary graph and another call to to either find the candle of a witness that the society is facial.

3.2.0.2 Snuggling into a nest.

So far we have been almost entirely focussed on handling candles in societies. However, in order to progress, we also require some strengthening of the structure given by a nest in a cylindrical rendition. This is, because later on we will work with societies whose vortex has bounded depth, but we also require the society itself to be of bounded depth. By pushing a nest of order \(s\) as close as possible towards the vortex of depth \(d\), it is possible to restrict to the society defined by the inner graph of the outer-most cycle of the nest and to observe that the depth of this society is now at most \(\mathbf{O}( s + d)\). Towards this observation we require some preparation.

Let \((G,\Lambda)\) be a society with a cylindrical rendition \(\rho\) in a disc \(\Delta\) together with a nest \(\mathcal{C}\) around the vortex \(c_0\). We say that \(\mathcal{C}\) is snug if there does not exist a cycle \(C \in \mathcal{C}\) together with a grounded path \(P \subseteq G\) of length at least one such that \(P\) has both endpoints on \(C\), is otherwise disjoint from \(\mathcal{C}\), and \(P\) is contained in the inner graph of \(C\). In particular, \(P\) cannot share edges with any cycle in \(\mathcal{C}\).

The following is a variation of the “cozy nest lemma” from the work of Gorsky, Seweryn, and Wiederrecht [50]. The main difference is that in their work, Gorsky, Seweryn, and Wiederrecht want the nest to be as far away from the vortex as possible instead of it being as close to the vortex as possible. Since any disc becomes an annulus when the interior of the unique vortex is removed, this is simply a matter of perspective which does not add any further complications. Thus, we omit the nearly identical proof here and refer the interested reader to the original paper.

With this, we are now able to proceed to showing that the society defined by the inner graph of the outer-most cycle of a snug nest has an upper bound on its depth depending only on the depth of the vortex and the size of the nest.

3.2.0.3 Cleaning a vortex.

We are finally ready to actually clean a vortex of bounded depth. That is, we wish to show that for any vortex of bounded depth surrounded by a big enough nest in a blank rendition, we can either find a \(k\)-candle mesh or delete a small set of vertices such that the remaining society is \(k'\)-shallow for some \(k' \leq k\). That is, our next goal is to prove the following theorem.

3.2.0.4 Isolating a vortex segment.

Let \((G,\Lambda)\) be a society of depth at most \(d\) and let \(S\) be a segment of \(\Omega\). By definition of depth, there cannot be \(d+1\) disjoint paths starting on \(S\) and ending on \(V(\Lambda) \setminus S\). Hence, by Menger’s Theorem, there exists a set \(X_S\) of size at most \(d\) such that in \(G-X_S\) there does not exist an \(S\)-\((V(\Lambda) \setminus S)\)-path in \(G-X_S\). We say that any minimum size set \(X_S \subseteq V(G)\) such that there is no \(S\)-\((V(\Lambda)\setminus S)\)-path in \(G-X_S\) is an \(S\)-isolator and note that such a set can be found in time \(\mathbf{O}(d \cdot ||G||)\).

Let now \((G,\Lambda)\) be a society of depth at most \(d\) where \((G,R)\) is an annotated graph. Our goal is to iteratively separate segments \(S_1,\dots,S_{\ell}\) of \(\Lambda\) from their complement. By doing so, we will be collecting an increasing set \(A_i \subseteq V(G)\) where \(i\) keeps track of the number of iterations. Moreover, we are going to maintain a second increasing set \(B_i\) which will “guard” the “attachments” inside each of the \(A_i\) as follows: For all \(i \leq j \in[\ell]\), if we consider the \(S_i\)-crop \((G_i,\Lambda_i)\) of \((G - A_j,\Lambda)\), then there exists an \(R\)-candle in \((G_i,\Lambda_i)\). However, \((G_i - B_j,\Lambda_i)\) does not have any \(R\)-candles.

Let \((G,\Lambda)\) be a society of depth at most \(d\) where \((G,R)\) is an annotated graph. A \(h\)-segmentation of \((G,\Lambda)\) is iteratively defined as follows: Let \(\Lambda = \langle v_1,\dots,v_n \rangle\).

We define \(S_1\) to be the shortest segment of \(\Lambda\) containing \(v_1\) such that there is a set \(Y_1 \subseteq V(G)\) of size at most \(d\) for which

• there is no \(S_1\)-\(V(\Lambda)\setminus S_1\)-path in \(G-Y_1\), and

• the \(S_1\)-crop \((G_1^1,\Lambda_1^1)\) of \((G-Y_1,\Lambda)\) has an \(R\)-candle.

Now let \(S_1'\) be the segment of \(\Lambda\) obtained from \(S_1\) by removing the very last vertex and let \(Z_1\) be any \(S_1'\)-isolator of order at most \(d\). Then, by choice of \(S_1\) we know that the \((S_1')\)-crop of \((G-(Y_1 \cup Z_1),\Lambda)\) does not contain an \(R\)-candle.

We set \(A_1 \mathrel{\vcenter{:}}= Y_1\) and \(B_1 \mathrel{\vcenter{:}}= Y_1 \cup Z_1\).

Now suppose the first \(i \in [h-1]\) segments \(S_1,\dots,S_i\) have already been defined together with the sets \(Y_j,Z_j,A_j\), and \(B_j\) for \(j \in[i]\). We describe how the next iteration is constructed.

Let \(S_{i+1}\) be the shortest segment of \(\Lambda\) disjoint from \(S \mathrel{\vcenter{:}}= \bigcup_{j \in [i]}S_j\) starting with the smallest vertex in \(\Lambda\) not in \(S\) such that there is an \(S_{i+1}\)-isolator \(Y_{i+1}\) in \((G-A_i,\Lambda)\) of size at most \(d\) for which the \(S_{i+1}\)-crop of \((G-(A_i \cup Y_{i+1}),\Lambda)\) contains an \(R\)-candle. Let further \(S_{i+1}'\) be the segment obtained from \(S_{i+1}\) by removing its last vertex. Then for any \(S_{i+1}'\)-isolator \(Z_{i+1}\) in \((G-A_i,\Lambda)\) of size at most \(d\) it holds that the \(S_{i+1}'\)-crop of \((G-(A_i \cup Y_{i+1} \cup Z_{i+1}),\Lambda)\) contains no \(R\)-candle. We set \(A_{i+1} \mathrel{\vcenter{:}}= A_i \cup Y_{i+1}\) and \(B_{i+1} \mathrel{\vcenter{:}}= B_i \cup Y_{i+1} \cup Z_{i+1}\).

The \(h\)-segmentation is now the list \(S_1,\dots,S_h\) together with the sets \(A_h\) and \(B_h\). Moreover, a segmentation of \((G,\Lambda)\) is an \(h\)-segmentation \(S_1,\dots,S_h\) together with the sets \(A_h\) and \(B_h\) such that \(\bigcup_{i\in[h]} S_i = V(\Lambda)\).

Since – as it is well known – Menger’s Theorem for finding either \(d\) disjoint paths or a separator of size at most \(d\) in time \(\mathbf{O}( d\cdot |G|)\), and by we can decide whether there exists an \(R\)-candle in any fixed society \((G',\Lambda')\) in time \(\mathbf{O}(|G'|^5)\), we can find an \(h\)-segmentation for any society \((G,\Lambda)\) of depth at most \(d\) in time \(\mathbf{O}(h \cdot d \cdot |G|^5)\).

Finally, we combine all of the above results into a proof of .

3.2.0.5 The proof of .

The proof of is now relatively straightforward. We simply call upon where we ask the nests of the vortices to be at least of order \(f_{\ref{thm95CleanVortex}}(k)\) each. Then we apply to each vortex together with its nest in the resulting \(\Sigma\)-rendition \(\rho\). Each such application to a vortex \(v\) yields a set \(B_v\) of size at most \(g_{\ref{thm95CleanVortex}}(\mathsf{depth}_{\ref{prop:localstructure}}(f_{\ref{thm95CleanVortex}}(k), t, r),k) \in \mathbf{poly}(k + t + r)\) which we add to the apex set. Since there are only \(\mathbf{O}(t^2 + r^2)\) vortices, this increases the size of the apex set by only a polynomial amount. Adjusting \(\rho\) by inserting the new renditions for the societies of the inner graphs of the outer-most cycles from the nests of vortices that were created by finally yields the desired \(k\)-shallow \(\Sigma\)-rendition.

4 Annotated graphs with vital solutions↩︎

The goal of this section is to prove a variant of the Vital Linkage Function function for the \(k\)-Spanning Disjoint Paths problem. That is, we want to show that instances of \(k\)-SDP with a unique solution that uses all vertices must either have large \(\mathsf{depth}_2\) or bounded treewidth.

We say that an instance \((G,R,\mathcal{T} = \{ (s_1,t_1),\dots,(s_k,t_k) \})\) of the \(k\)-Spanning Disjoint Paths problem is vital if there exists a unique linkage \(\mathcal{L} = \{ L_1,\dots,L_k\}\) where \(L_i\) joins \(s_i\) and \(t_i\) for each \(i \in[k]\) and \(R \subseteq V(\bigcup \mathcal{L})\) in \(G\) and \(V(G) = V(\mathcal{L})\).

The strategy to prove follows along three main steps. The first two of these steps are precisely the same as already established by Robertson and Seymour: Let \((G,R,\mathcal{T})\) be a vital instance of \(k\)-SDP with \(\mathsf{depth}_2\) at most \(r\), then

Step 1:

We use a result of Protopapas, Thilikos, and Wiederrecht [5] together with a result of Robertson and Seymour [4] in order to prove that \(G\) cannot contain a clique minor of size \(\Omega(r)\) as otherwise there would be an irrelevant vertex.

Step 2:

In the absence of big clique minors, but when the graph has large treewidth, we may apply . Moreover, the assumption of vitality allows us to completely remove all apices.

Step 3:

Finally, we arrive in an apex-free situation. Here, we now proceed in two substeps: First, we show that we only need to care about a set \(R' \subseteq R\) of size \(\mathbf{poly}( r + k )\) and may remove all other red vertices. Second: This will then allow us to interpret \((G',R',\mathcal{T})\) as a vital instance \((G',\mathcal{T}')\) of \(\mathbf{poly}( r + k )\)-Disjoint Paths. Here \(G'\) is obtained through a series of small operations in order to reduce \(R\) to \(R'\). Hence, in this last step, shows that \(G\) must have small treewidth as desired.

Notice that the most technical part of this roadmap by far is Step 3. In this step we need to introduce new tools to deal with spanning linkages and also implement several technical statements from the work on vital linkages by Cavallaro, Gorsky, Kreutzer, Thilikos, and Wiederrecht [16] in our setting. In most cases, we will actually make much stronger assumptions on our instance and in a fourth and final step we will argue why these assumptions were justified. Indeed, during Step 3 we will assume that the entire graph consists only of the linkage \(\mathcal{L}\) itself and a collection of cycles embedded in a concentric way in some disk in the surface. Our main goal will be to show that the inner-most cycle of this collection is disjoint from \(\mathcal{L}\) which will then be the final contradiction to the assumption of vitality.

4.1 What to do with a clique↩︎

As mentioned before, the original statements for irrelevant vertices and the \(k\)-Disjoint Paths problem are often given for a more general problem known as the \((k,d)\)-Folio problem. In essence, \((k,d)\)-Folio is a common generalisation of Minor Containment and \(k\)-Disjoint Paths that allows for the minors to be partially rooted at fixed vertices. Since \((k,d)\)-Folio is much more general than what is necessary for our purposes, we simplify the statements sightly. In this sense we provide a slight weakening of the folio definition in order to state the statements required to handle the case of large clique minors.

Let \(G\) be a graph and \(Z \subseteq V(G)\) be a set of vertices. The weak \(k\)-folio relative to \(Z\), denoted by \(k\text{-}\mathsf{WFolio}_G(Z)\), is the collection of all sets \(\{ s_1,\dots,s_{k'},t_1,\dots,t_{k'} \} \subseteq Z\) of at most \(k\) vertex pairs \(\{ (s_1,t_1),\dots,(s_{k'},t_{k'}) \}\), \(k' \leq k\), such that \((G,\mathcal{T})\) is a yes-instance of \(k\)-Disjoint Paths for every \(\mathcal{T} \in k\text{-}\mathsf{WFolio}_G(Z)\) .

A vertex \(v \in V(G)\) is said to be irrelevant for the weak \(k\)-folio relative to \(Z\) if and only if \(k\text{-}\mathsf{WFplio}_{G-v}(Z) = k\text{-}\mathsf{WFplio}_{G}(Z)\). In in particular, it is worthwhile pointing out that the weak \(k\)-folio relative to \(Z\) defined above is essentially the special case where the detail \(d = 0\) in the original statement.

Under these definitions, the following theorem of Robertson and Seymour acts as the backbone of our engine for handling clique minors.

We will also require the following result from [5] which refines some of the tools from [4].

With this, we are ready to state the main lemma of this subsection.

4.2 Desolate instances and their loci↩︎

From here on, we are mostly interested in a special kind of instances for the \(k\)-Spanning Disjoint Paths problem. These are instances that adhere to while meeting additional requirements. We refer to such instances as “desolate” and we will later on see, that any vital instance can be transformed into a desolate one. Before we introduce the full definition, we require some additional terminology.

4.2.0.1 Snug cycles.

Let \((G,\Omega)\) be a society with a vortex-free rendition \(\rho\) in a disc \(\Delta\) and let \(\mathcal{C} = \{ C_1,\dots,C_s\}\) be a collection of cycles in \(G\). We say that \(\mathcal{C}\) is concentric in \(\rho\) if

1. \(C_i\) is grounded in \(\rho\) for each \(i\in[s]\), and

2. if \(\Delta_i\) denotes the disc bounded by the trace of \(C_i\) for each \(i\in[s]\), then \(\Delta_1 \subsetneq \Delta_2 \subseteq \dots \subsetneq \Delta_s\).

We say that a set \(\mathcal{C} = \{ C_1,\dots,C_s\}\) of concentric cycles in \(\rho\) is snug, if

1. the inner graph of \(C_1\) has no grounded cycle apart from \(C_1\) itself, and

2. if \(\rho'\) is the cylindrical rendition of \((G,\Omega)\) obtained by removing all cells in \(\Delta_1\), and declaring \(\Delta_1 \setminus N(C_1)\) a vortex, then \(\{ C_2,\dots,C_s\}\) is snug in \(\rho'\).

Notice that, due to , we know that, starting with any set of concentric cycles \(\mathcal{C} = \{ C_1,\dots,C_s\}\) where \(\Delta_s\) denotes the disc bounded by the trace of \(C_s\), we can find a snug set \(\mathcal{C'_1,\dots,C'_s}\) of concentric cycles where, if \(\Delta'_s\) denotes the disc bounded by the trace of \(C'_s\), then \(\Delta'_s \subseteq \Delta_s\).

Let now \((G,R,\mathcal{T})\) be an instance of the \(k\)-Spanning Disjoint Paths problem and \(\rho\) be a blank \(\Sigma\)-rendition of \(G\). We say that a collection \(\mathcal{C} = \{ C_1,\dots,C_s\}\) is snug in \(\rho\) if

1. \(C_s\) is grounded in \(\rho\) and its trace bounds the disc \(\Delta_s\),

2. \(\Delta_s\) contains no vortex of \(\rho\), and the inner graph of \(\Delta_s\) is disjoint from \(\mathcal{T}\), and

3. if \(\rho'\) is the restriction of \(\rho\) to \(\Delta_s\) and \((G',\Omega')\) is the society where \(G'\) is the inner graph of \(\Delta_s\) and \(\Omega'\) is the cyclic ordering of the nodes of \(C_s\) obtained by tracing along the boundary of \(\Delta_s\) in clockwise direction, then \(\mathcal{C}\) is snug in \(\rho'\).

4.2.0.2 Dry wells.

Let \(s\) be a positive integer. An \(s\)-well \(\mathcal{W} = (G, \Omega, \rho, \mathcal{C}, \mathcal{P})\) is a society \((G,\Omega)\) with a vortex-free, cylindrical rendition \(\rho\) in a disc \(\Delta\) such that \(G = \bigcup \mathcal{C} \cup \bigcup \mathcal{P}\) for a set of pairwise internally disjoint \(V(\Omega)\)-paths \(\mathcal{P}\) and \(\mathcal{C} = \{ C_1, \ldots, C_s \}\) is a snug set of cycles.

Since \(\mathcal{C}\) is snug, we know that for each \(P \in \mathcal{P}\), we may let \(T_P\) be the trace of \(P\) in \(\rho\) and there exists a unique component \(\Delta_P\) of \(\Delta - T_P\) such that the intersection of \(\Delta_P\) and the trace of \(C_1\) is empty. We call the closure of \(\Delta_P\) the interior of \(P\). See for an illustration of a well.

We say that an \(s\)-well \(\mathcal{W} = (G, \Omega, \rho, \mathcal{C}, \mathcal{P})\) is drained if either \(|\mathcal{P}| \leq 1\) or

• for each \(P \in \mathcal{P}\) we have that for all \(i \in [s-1]\), if \(P \cap C_i\) is non-empty, then there exists \(Q \in \mathcal{P} \setminus \{ P \}\) such that the trace of \(Q \cap C_{i+1}\) is non-empty and found in \(\Delta_P\), and

• for all \(i \in [s]\), no \(C_i\)-path \(P'\) in \(P\) that is disjoint from \(V(\mathcal{C} \setminus \{ C_i \})\) is contained in a cell \(c \in C(\rho)\) such that \(\sigma(c)\) contains an edge of \(C_i\).

The core property of drained wells is, that we know for any path \(P\) of \(\mathcal{P}\) that enters deeply into the well, it cannot be pushed closer to the part of the boundary of the well contained in \(\Delta_P\) because it is blocked by an entire sequence of paths that exhaust the cycles of the well that lie further outside.

Indeed, simply draining a well is not strong enough for our purposes, we require a well to entirely “dry”. Indeed, the fact that the cycles of a well form a snug family allows us to deduce a set of very strong properties for the interaction between the paths in \(\mathcal{P}\) and the cycles in \(\mathcal{C}\).

We say that a well \(\mathcal{W} = (G, \Omega, \rho, \mathcal{C} = \{ C_1, \ldots, C_s\}, \mathcal{P})\) is dry if \(\mathcal{W}\) is drained and for all \(P \in \mathcal{P}\) we have that

1. the graph \(C_1 \cap P\) is either empty or a single path,

2. there exists a unique \(i \in [s]\) such that \(C_i \cap P\) is a single path,

3. for all \(j \in [i-1]\) the graph \(C_j \cap P\) is empty, and

4. for all \(j \in [i+1,s]\) the graph \(C_j \cap P\) consists of exactly two paths.

4.2.0.3 Desolate instances.

We are now ready to give a full list of the properties we wish to assume for Step 2 the first part of Step 3.

Let \(G\) be a graph \(\mathcal{L}\) be a linkage in \(G\), and \(H \subseteq G\) be a subgraph of \(G\). We denote by \(\mathcal{L}[H]\) the linkage \(\mathcal{L}'\) consisting of the collection of all maximal subpaths \(L'\) of paths in \(\mathcal{L}\) that are entirely contained in \(L\).

Let \(g,s,d\), and \(b\) be non-negative integers. Let \(\mathcal{G} = (G,R,\mathcal{T})\) be a vital instance of \(k\)-Spanning Disjoint Paths. We say that \(\mathcal{G}\) is \((g,s,d,b,w)\)-desolate if there exist

• a surface \(\Sigma\) of Euler-genus at most \(g\),

• an \(s\)-shallow \(\Sigma\)-rendition \(\rho\) of \(G\) with at most \(b\) vortices, all of which have depth at most \(d\), and

• a collection \(\mathcal{C} = \{ C_1,\dots,C_w\}\) of vertex-disjoint cycles in \(G\)

such that, if \(\mathcal{L}\) denotes the unique solution of the vital instance \(\mathcal{G}\),

1. \(G = \bigcup \mathcal{C} \cup \bigcup \mathcal{L}\)

2. \(\mathcal{C}\) is snug in \(\rho\),

3. no two vortices of \(\rho\) intersect on their boundaries,

4. every terminal vertex is either contained in \(\sigma(c)\) for some vortex \(c\) of \(\rho\) or belongs to \(N(\rho)\), and

5. if \(\Delta_w\) denotes the disc bounded by the trace of \(C_w\) and \((G_w,\Omega_w)\) is the society obtained from the inner graph \(G_w\) of \(C_w\) where \(\rho_w\) denotes the restriction of \(\rho\) to \(\Delta_w\) and \(G_w\), then \((G_w,\Omega_w,\rho_w,\mathcal{C},\mathcal{L}[G_w])\) is a dry \(w\)-well.

We say that the rendition \(\rho\) witnesses the desolation of \((G,R,\mathcal{T})\).

With this, we finally have the correct terminology to talk about the type of instances we are interested in. The intermediate goal is now to show that and \((g,s,d,b,w)\)-desolate instance \((G,R,\mathcal{T})\) of \(k\)-Spanning Disjoint Paths can be transformed into a \((g,s,d,b,w)\)-desolate instance \((G',R',\mathcal{T}')\) of \(\mathbf{poly}(g + b + k)\)-Spanning Disjoint Paths where every vertex of \(R'\) is also a terminal. Since this will imply an upper bound on \(|R'|\) it means that we may completely ignore the “spanning” aspect of the problem. We will use this observation to deduce that, in this case, \(w\) must be bounded by \(2^{\mathbf{poly}(g + b + k)}\).

4.3 Bringing desolation to a vital instance↩︎

We start by showing that any vital instance of large enough treewidth can be reduced to one that is desolate. This is, in some sense, the most crucial part of the proof and it is also where we get rid of apices, which is a fundamental step that allows our future arguments.

4.4 Entering the wasteland↩︎

With we now know that any vital instance of large enough treewidth can be transformed into a desolate one at the cost of increasing the number of terminals but without changing the Euler-genus of the surface. Moreover, it is worth pointing out that the parameter \(w\) in which dictates the size of the well does not appear in \(\mathsf{terminals}_{\ref{lemma95theDesolationOfAnInstance}}(r,k)\) and also does not have any influence on the number or depth of the vortices, or on the Euler-genus of the surface. This means, vital instances of larger and larger treewidth can be transformed into desolate instances with deeper and deeper wells without introducing any additional cost on any of the other parameters involved. Thus, ultimately, all we have to do towards proving is to show that desolate instances cannot have arbitrarily deep wells.

Towards this goal, we next want to prove that any desolate instance of \(k\)-Spanning Disjoint Paths can be transformed into a vital instance of \(\mathbf{poly}(r + k)\)-Disjoint Paths with a large dry well. It will then easily follow from that such an instance cannot exist, thereby completing the proof of .

We say that a pair \((G,\mathcal{T})\) where \(G\) is a graph and \(\mathcal{T} = \{ (s_i,t_i) \mid i \in [k] \}\) is a set of \(k\)-terminal pairs is a vital instance of \(k\)-Disjoint Paths if there exists a unique \(\mathcal{T}\)-linkage \(\mathcal{L}\) in \(G\) and \(V(\mathcal{L}) = V(G)\).

Let \(g,d\), and \(b\) be non-negative integers. Let \(\mathcal{G} = (G,\mathcal{T})\) be a vital instance of \(k\)-Disjoint Paths. We say that \(\mathcal{G}\) is \((g,d,b,w)\)-barren if there exist

• a surface \(\Sigma\) of Euler-genus at most \(g\),

• a \(\Sigma\)-rendition \(\rho\) of \(G\) with at most \(b\) vortices, all of which have depth at most \(d\), and

• a collection \(\mathcal{C} = \{ C_1,\dots,C_w\}\) of vertex-disjoint cycles in \(G\)

such that, if \(\mathcal{L}\) denotes the unique solution of the vital instance \(\mathcal{G}\),

1. \(G = \bigcup \mathcal{C} \cup \bigcup \mathcal{L}\)

2. \(\mathcal{C}\) is snug in \(\rho\),

3. no two vortices of \(\rho\) intersect on their boundaries,

4. every terminal vertex is either contained in \(\sigma(c)\) for some vortex \(c\) of \(\rho\) or belongs to \(N(\rho)\), and

5. if \(\Delta_w\) denotes the disc bounded by the trace of \(C_w\) and \((G_w,\Omega_w)\) is the society obtained from the inner graph \(G_w\) of \(C_w\) where \(\rho_w\) denotes the restriction of \(\rho\) to \(\Delta_w\) and \(G_w\), then \((G_w,\Omega_w,\rho_w,\mathcal{C},\mathcal{L}[G_w])\) is a dry \(w\)-well.

We say that the \(\Sigma\)-rendition \(\rho\) witnesses that \(\mathcal{G}\) is barren. Moreover, we refer to \((G_w,\Omega_w,\rho_w,\mathcal{C},\mathcal{L}[G_w])\) as the well of \(\rho\).

Our next goal is to prove the following lemma.

To proceed with the proof of , we require some additional terminology.

4.4.0.1 More on shallow renditions.

Let \((G,R,\mathcal{T})\) be a \((g,s,d,b,w)\)-desolate instance of \(k\)-Spanning Disjoint Paths and let \(\rho\) be a \(\Sigma\)-rendition witnessing the desolation of \((G,R,\mathcal{T})\). Let \(\mathcal{V}\) denote the set of all vortices of \(\rho\) and for each vortex \(v \in \mathcal{V}\) let \(S^v_1,\dots,S^v_{s_v}\) be a partition of the vortex society \((\sigma(v),\Lambda^v)\) into deep and facial segments. For each \(i \in [s_v]\), we denote by \((G^v_i,\Lambda^v_i)\) the \(S^v_i\)-crop of \((\sigma(v),\Lambda^v)\) and, in case \(S^v_i\) is facial, we denote by \(\gamma^v_i\) an ultimate frontier of \((G^v_i,\Lambda^v_i)\) in the facial rendition \(\rho^v_i\) of \((G^v_i,\Lambda^v_i)\).

Notice that there exists a \(\Sigma\)-rendition \(\rho^{\star}\) with at most \(b \cdot \frac{s}{2}\) vortices, each of depth at most \(d\), such that \(\rho\) is a restriction of \(\rho^{\star}\) and for each \(v \in \mathcal{V}\) and \(i \in [s_v]\) where \(S^v_i\) is a facial segment, \(\rho^v_i\) is the restriction of \(\rho^{\star}\) to \((G^v_i,\Lambda^v_i)\). Indeed, note that we may also assume that every terminal which belongs to some \(G^v_i\) where \(S^v_i\) is a facial segment is a node of \(\rho^{\star}\). This is, because here we may perform the same reduction as before in the last part of the proof of while possibly removing some vertices of \(R\). We refer to \(\rho^{\star}\) as a true rendition of \((G,R,\mathcal{T})\) obtained from \(\rho\). The vortices of \(\rho^{\star}\) can be seen to correspond precisely to the deep segments of the vortices of \(\rho\).

4.4.0.2 Links and loops.

The most technical part of the proof of will be to show that the number of maximal grounded subpaths of the unique solution \(\mathcal{L}\) that interact with the ultimate frontiers of some facial segments of some vortices while also entering the well is bounded by a polynomial function only depending on the Euler-genus of the surface, the number and depth of the vortices, and the number of facial and deep segments in the shallow rendition. Indeed, in order to show this it suffices to control only those subpaths start have at least one end on the ultimate frontier of some facial segment, and those that enclose discs which contain neither other vortices, nor terminals, nor other segments. This is, because once these subpaths are controlled, all other subpaths are guaranteed to contain only terminals but no vertices of \(R\). This means that, once we reach this state, we have found an instance where all of \(R\) has been reduced to occur only as endpoints of a bounded number of paths, meaning that we are now allowed to forgo the “spanning condition” of our Spanning Disjoint Paths problem entirely and focus only on the underlying Disjoint Paths problem.

To this end let \(\mathcal{G}=(G,R,\mathcal{T})\) be a \((g,s,d,b,w)\)-desolate instance of \(k\)Spanning Disjoint Paths whose desolation is witnessed by the \(\Sigma\)-rendition \(\rho\). Let also \(\rho^{\star}\) be a true rendition of \(\mathcal{G}\) obtained from \(\rho\). Let \(G'\) be obtained from \(G\) by deleting \(\sigma_{\rho^{\star}}(v) - N(v)\) for every vortex of \(\rho^{\star}\). Let \(X\) denote the set of all vertices of \(N(\rho^{\star})\) that are either terminals, belong to the boundary of some vortex, or to some ultimate frontier of one of the facial segments of \(\rho\). and let \(\mathcal{L}^{\star}\) denote the set of all maximal \(\rho\)-grounded subpaths of paths in \(\mathcal{L}\) with both endpoints \(X\) but with no interior vertices in \(X\). We call the paths in \(\mathcal{L}^{\star}\) the arcs of \(\mathcal{L}\). It follows that every path in \(\mathcal{L}^{\star}\) is grounded in \(\rho^{\star}\). We are now going to classify the paths in \(\mathcal{L}^{\star}\) into different types. For this, we slightly modify \(\Sigma\) by removing the interiors of all closures of the vortices of \(\rho^{\star}\) as well as the interiors of \(\rho^{\star}\)-aligned discs \(\Delta_x\) of radius \(\varepsilon > 0\) for some small \(\varepsilon\) such that, for every terminal \(x \in N(\rho^{\star})\) where \(x\) is not on the boundary of a vortex, \(x\) is the only intersection of \(\Delta_x\) with \(\rho^{\star}\). Finally, for every ultimate frontier \(\gamma^v_i\) of \(\rho^{\star}\), we remove the interior of a \(\rho^{\star}\)-aligned disk \(\Delta^i_v\) which intersects \(\rho^{\star}\) precisely in \(N(\gamma^v_i)\). Let \(\Sigma^{\star}\) be the resulting surface. As a consequence, we now have that every path in \(\mathcal{L}^{\star}\) now has both endpoints on the boundary of \(\Sigma^{\star}\). Moreover, the number of boundary components of \(\Sigma^{\star}\) is at most \(2k + sb\). We refer to \(\Sigma^{\star}\) as the true surface under \(\rho^{\star}\).

A path \(L \in \mathcal{L}^{\star}\) is a loop if both of its endpoints belong to the boundary of the same boundary component of \(\Sigma^{\star}\). Otherwise we say that \(L\) is a link. See for an illustration.

Loops. We say that a loop \(L\) of \(\mathcal{L}^{\star}\) is simple if both of its endpoints belong to the boundary of one of the original vortices of \(\rho^{\star}\) and, if we were to identify the boundary containing the endpoints of \(L\) into a single point, its trace bounds a disc in \(\Sigma^{\star}\) which contains no boundary component.

A loop \(L\) of \(\mathcal{L}\) is called red if there exists an ultimate frontier \(\gamma^v_i\) such that both endpoints of \(L\) belong to \(N(\gamma^v_i)\) and the trace of \(L\) together with some segment of \(\gamma^v_i\) bound a disc in \(\Sigma^{\star}\) which contains no other boundary component of \(\Sigma^{\star}\) nor a terminal.

A loop \(L\) that has both ends on an ultimate frontier \(\gamma^v_i\), and the closed curve obtained from the union of \(\gamma^v_i\) and the segment \(\varphi\) of \(\gamma^v_i\) between the endpoints of \(L\) is contractible in \(\Sigma^{\star}\), but \(\varphi\) contains a terminal is called splitting.

A loop \(L\) is complex if it has both endpoints on an ultimate frontier of \(\rho^{\star}\) and is neither red nor splitting. Any other loop that is neither simple, red, splitting, or complex is called common.

Notice that every loop of \(\mathcal{L}^{\star}\) is either simple, red, complex, or common. Moreover, a loop is complex or common if and only if it forms – possibly together with a vortex boundary or a segment of some ultimate frontier – a non-contractible curve in \(\Sigma^{\star}\) See for an illustration of different types of loops.

Links. Any path \(L\) in \(\mathcal{L}^{\star}\) that is not a loop is a link. However, there are still several types of links. A link is simple if it runs between two terminal vertices both of which do not belong to a vortex boundary or an ultimate frontier or between one terminal vertex that does not belong to a vortex boundary or an ultimate frontier and some node on a vortex boundary or an ultimate frontier. Notice that the number of simple links is at most \(k\) and every link with an endpoint on the boundary of one of the discs \(\Delta_x\) is simple.

A link is red if both of its endpoints belong to ultimate frontiers of \(\rho^{\star}\). Notice that a red link might even have both endpoints on the same ultimate frontier if it forms a non-contractible curve.

A link is mixed if one of its endpoints belongs to an ultimate frontier of \(\rho^{\star}\) and the other endpoint belongs to the boundary of some vortex of \(\rho^{\star}\).

Any link that is neither simple, red, or mixed is common.

We now have everything in place for the proof of . To give another brief overview: Our strategy is to first show that, by sacrificing some amount of cycles from the well, we may assume that no simple or red loop intersects any of the remaining cycles of the well. This will then imply that we may as well assume that no simple or red loops exist. In a second and third step, we then show that the total number of red and mixed links as well as complex loops are bounded. When this is establish it will finally imply that we may assume that \(|R|\) is bounded and thus, we have reached a point where we are looking at a regular instance of Disjoint Paths instead of its spanning variant.

4.4.0.11 Proof of the Vital Linkage Theorem for Spanning Linkages.

We are finally ready for the proof of .

5 Irrelevant vertices for spanning linkages↩︎

With we have completed the core theoretical part of our algorithm. However, in order to compute an irrelevant vertex, we need to make one more step. Due to we know how to find an irrelevant vertex in the presence of a large clique minor. Next, we require a similar technique if we find a large wall, but no large clique minor associated with it. In such a situation, the so-called Flat Wall Theorem is usually applied to find an area where the graph can be split into two: One part which contains the majority of the graph and the other which allows for a vortex-free rendition in a disc while hosting a large grounded wall. The goal is to show that the centre of such a wall can always be avoided by a solution.

The way we achieve this is by proving an analogue of the “Annulus Combing Lemma” due to Golovach, Stamoulis, and Thilikos [44]. To be more precise, we follow the proof of the same lemma due to Cavallaro, Gorsky, Kreutzer, Thilikos, and Wiederrecht [16].

The Annulus Combing Lemma says, roughly, that, given a graph with a rendition into the sphere with precisely two vortices, such that there is a large number of disjoint and grounded cycles separating the two vortices and a big flow connecting the two boundary cycles of this “annulus”, then any (spanning) linkage can be forced to traverse through this annulus by using only the paths of this flow. The advantage of this viewpoint is, that it allows for the linkage to be “split” along the flow, which allows us to decompose the linkage into two new linkages, each with a bounded number of terminals. In a later step, we will show that in case one of the two vortices contains a large wall and has a vortex-free rendition into a disc itself, then the centre of this wall is irrelevant.

5.1 Combing spanning linkages↩︎

We begin with the proof of the annulus combing lemma for spanning linkages. The proof is almost identical to the original proof of Theorem 10.1 from [16] and we include it here only for the sake of completeness since we do need to alter the statement slightly. Before we get there, we need some additional terminology – note that these definitions are taken directly from [16].

5.1.0.1 Flat Meshes.

Let \(n \ge 2\) be an integer. Let \(G\) be a graph, and let \(M \subseteq G\) be an \(n\)-mesh. We say that \(M\) is a flat mesh in \(G\) if there exists a rendition \(\rho\) of \(G\) on the sphere with a single vortex \(c_0\) such that \(M\) is flat in \(\rho\) and the trace of the perimeter of \(M\) in \(\rho\) separates all vertices in \(N(\rho) \cap V(M)\) from \(c_0\). We say that \(\rho\) witnesses the flatness of \(M.\)

5.1.0.2 Cylindrical meshes.

In the context of the Annulus Combing Lemma we require a cylindrical variant of meshes.

Let \(m,n\) be positive integers, let \(M\) be a graph, and let \(C_1, \ldots, C_m\) be cycles and \(P_1, \ldots, P_n\) be paths in \(M\) such that the following holds for all \(i \in [m]\) and \(j \in [n]\):

• \(C_1, \ldots, C_m\) are pairwise vertex-disjoint, \(P_1, \ldots, P_n\) are pairwise vertex-disjoint, and \(M = C_1 \cup \cdots \cup C_m \cup P_1 \cup \cdots \cup P_n\).

• \(C_i \cap P_j\) is a path, and if \(i \in \{ 1, m \}\) or \(j \in \{ 1, n \}\), then \(C_i \cap P_j\) has exactly one vertex,

• when traversing \(C_i\) starting from an endpoint of \(P_1\cap C_i\), then either the paths \(P_1, \ldots, P_n\) are encountered in the order listed or the next \(P_j\) one encounters is \(P_n\) and from here the paths are encountered in the order \(P_n,\dots,P_1\), and

• \(P_j\) has one end in \(C_1\) and the other in \(C_m\), and when traversing \(P_j\) starting from its endpoint on \(C_1\), the cycles \(C_1, \ldots, C_m\) are encountered in the order listed.

If the above conditions hold for \(M\), we call \(M\) an \((n \times m)\)-cylindrical mesh. The cycles \(C_1, \ldots, C_m\) are called the concentric cycles, or cycles, of \(M\) and the paths \(P_1, \ldots, P_n\) are called the radial paths, or rails, of \(M\). We also call \((n \times n)\)-cylindrical meshes \(n\)-cylindrical meshes.

5.1.0.3 The compass of a (cylindrical) mesh.

Let \(M\) be a flat mesh in a graph \(G\) where \(\rho\) is a sphere rendition of \(G\) witnessing the flatness of \(M\). The compass of \(M\) is the inner graph of its perimeter.

Let now \(G\) be a graph and \(\rho\) be a \(\Sigma\)-rendition of \(G\) for some surface \(\Sigma\). The compass of a cylindrical mesh \(M\) grounded in \(\rho\) is the union of all graphs \(\sigma(c)\) over the cells \(c\) contained in the annulus defined by the traces of the outer- and inner-most cycle of \(M\).

5.1.0.4 A partially embedded railed annulus.

Let \(w,r \geq 0\) be two integers. A \((w,r)\)-railed annulus is a graph \(A_{w,r}\) such that there exist pairwise vertex-disjoint cycles \(C_1,\dots, C_w\), called the circles, and pairwise vertex-disjoint paths \(R_1,\dots R_r\), called the rails, such that

1. \(A_{w,r} = \bigcup_{i\in [w]} C_i \cup \bigcup_{i \in [r]} R_i\) is a planar graph,

2. \(R_i\) has one endpoint on \(C_1\), the other on \(C_w\) for all \(i\in[r]\), and is otherwise disjoint from \(C_1\cup C_w\),

3. for all \(i\in[r]\), \(j\in[w]\), \(R_i \cap C_j\) is a path, and

4. for each \(i\in[r]\), \(R_i\) visits the cycles \(C_1, \dots,C_w\) in the order listed when traversing along \(R_i\) starting from its endpoint on \(C_1\).

We call \(C_1\) and \(C_w\) the boundary circles of \(A_{w,r}\). We say that a graph \(A\) is a railed annulus if there exist \(r\) and \(w\) such that \(A\) is a \((w,r)\)-railed annulus.

Now let \(\Sigma\) be a surface and \(G\) be a graph with a \(\Sigma\)-rendition \(\rho\). We say that a railed annulus \(A \subseteq G\) is separating in \(\rho\) if

1. \(A\) is grounded in \(\rho\),

2. if \(A\) has at least two circles and at least two rails, then there exists an annulus \(\circledcirc \subseteq \Sigma\) such that the traces of the boundary circles of \(A\) coincide with the two boundary components of \(\circledcirc\), and the trace of every rail of \(A\) is contained in \(\circledcirc\),

3. \(\circledcirc\) is disjoint from the closures of the vortices of \(\rho\), and

4. for every circle \(C\) of \(A\), the trace of \(C\) is a separating curve in \(\Sigma\).

We call the annulus \(\circledcirc\) above the domain of \(A\) in \(\rho\). The crop of \(G\) by \(\circledcirc\) is the union of all graphs \(\sigma(c)\) whose cell \(c\) of \(\rho\) is contained in \(\circledcirc\). Finally, if \((G,R)\) is an annotated graph with a \(\Sigma\)-rendition \(\rho\) and a separating railed annulus \(A\) with domain \(\circledcirc\), we say that \(A\) is blank if the crop of \(G\) by \(\circledcirc\) does not contain any vertices from \(R\). In case \((G,R,\mathcal{T})\) is an instance of \(k\)-Spanning Disjoint Paths for some \(k\), we also say that \(A\) is terminal-free of the crop of \(G\) by \(\circledcirc\) does not contain any terminals.

Let \(p\geq 0\) and \(q\geq 2\) be integers. Let \(A = A_{2p+q,r}\) be a railed annulus. The \(p\)-trimming of \(A\) is the railed annulus \(A_{q,r}\) obtained from \(A\) by removing the first and last \(p\) circles and restricting the rails to their minimal \(C_{p+1}\)-\(C_{p+q}\)-subpaths.

5.1.0.5 Combed linkages.

Let \(\Sigma\) be a surface, \(G\) be a graph with a \(\Sigma\)-rendition \(\rho\), and let \(A \subseteq G\) be a separating railed annulus in \(G\) with domain \(\circledcirc\) in \(\rho\). Let \(H\) be the crop of \(G\) by \(\circledcirc\). A linkage \(\mathcal{L}\) in \(G\) is combed in \(A\) if the intersection of \(\bigcup\mathcal{L}\) and \(H\) is a subgraph of the union of the rails of \(A\).

With this, we are ready to state the spanning version of the Annulus Combing Lemma.

Before we dive into the proof, we require another small lemma form the work of Cavallaro et al.

Let \(\Sigma\) be a surface. A topological linkage \(\mathcal{T}\) in \(\Sigma\) with pattern \(\tau\) is a set of pairwise disjoint simple curves such that \(\mathcal{T}\) contains for each pair \(\{a,b\} \in \tau\) a curve with endpoints \(a\) and \(b\). We denote the pattern of \(\mathcal{T}\) by \(\tau(\mathcal{T})\).

A pattern \(\tau\) is realisable (in \(G\)) if there is a linkage \(\mathcal{L}\) in \(G\) with \(\tau(\mathcal{L}) = \tau\) and it is topologically feasible (in \(\Sigma\)) if there is a topological linkage \(\mathcal{T}\) in \(\Sigma\) with \(\tau(\mathcal{T}) = \tau\).

5.2 Avoiding an insulated vertex↩︎

With we are now able to control the interaction of the graph enclosed by some flat wall with the outside and, in particular, with solutions to spanning linkage problems. That is, when we are given a large enough flat wall, we know that – apart from the apex set – we only need to consider a bounded number of additional paths that enter the inner regions of the wall. The next step is to turn this intuition into an actual algorithm, thereby proving that the centre of a large enough wall can always be avoided by a solution for \(k\)-Spanning Disjoint Paths, given that \(\mathsf{depth}_2\) is bounded.

Before we continue, we require some more definitions.

5.2.0.1 Layers and central submeshes.

Let \(r \geq 3\) be an integer and \(M\) be an \((r \times r)\)-mesh. We define the layers of \(M\) recursively as follows: The first layer of \(M\) is its perimeter. For \(i \in [2,\lfloor \frac{r}{2} \rfloor]\), the \(i\)th layer of \(M\) is the \((i-1)\)th layer of the \(((r-1) \times (r-1))\)-mesh obtained from \(M\) by removing its perimeter and iteratively removing vertices of degree \(1\).

Given an integer \(q \in [3,r]\) such that \(r-q\) is even, the \(q\)-central submesh of \(M\) is the \((q \times q)\)-mesh obtained from \(M\) by removing the first \(\frac{r-q}{2}\) layers of \(M\) and then iteratively deleting vertices of degree at most \(1\).

5.2.0.2 Bridges and attachments.

Let \(H\) be a subgraph of a graph \(G\). An \(H\)-bridge in \(G\) is a connected subgraph \(J\) of \(G\) such that \(E(J) \cap E(H) = \emptyset\) and either \(E(J)\) consists of a unique edge with both ends in \(H\), or \(J\) is constructed from a component \(C\) of \(G - V(H)\) and the non-empty set of edges \(F \subseteq E(G)\) with one end in \(V(C)\) and the other in \(V(H)\), by taking the union of \(C\), the endpoints of the edges in \(F\), and \(F\) itself. Notice that the \(H\)-bridges induce a partition of \(E(G)\setminus E(H)\). The vertices in \(V(J) \cap V(H)\) are called the attachments of \(B\) and the set \(V(J)\setminus V(H)\) is called the interior of \(J\).

5.2.0.3 Homogeneous meshes.

The following definitions are due to Gorsky, Seweryn, and Wiederrecht [56] who recently showed that homogeneity of flat meshes with respect to a set of \(q\) colours can be achieved within polynomial bounds.

Let \(r\geq 3\) be an integer, \(M\) be an \((r \times r)\)-mesh in \(G\) and let \(C_P\) be the perimeter of \(M\). Let \(C\subseteq M\) be any cycle of \(M\). The compass of \(C\) is the union of \(C\) together with all \(C\)-bridges in \(G\) that are entirely contained in the compass of \(M\). We denote the compass of \(C\) with respect to \(\rho\) by \(\mathsf{compass}_M(C)\) and we drop the \(\rho\) in the subscript if it is understood from the context. The interior of a cycle \(C\subseteq M\), denoted by \(\mathsf{int}_M(C)\) is the graph \(\mathsf{compass}_{\rho}(C)-C\). We also drop the \(M\) in the subscript if the wall is understood from the context.

A \(q\)-colorful graph is a pair \((G,\chi)\) where \(G\) is a graph and \(\chi\colon V(G) \to 2^{[q]}\) assigns to each vertex a, possibly empty, set of at most \(q\) colours. Notice that the case \(q=1\) is precisely the case of annotated graphs. We explicitly allow for \(q\) to be \(0\).

Given an arbitrary \(q\)-colorful graph \((G,\chi)\), a set \(X\subseteq V(G)\) and a subgraph \(H\subseteq G\), we define \[\begin{align} \chi(X) \coloneq \bigcup_{v\in X} \chi(v), \end{align}\] as well as \(\chi(H) \mathrel{\vcenter{:}}= \chi (V(H))\). Note that this should not be confused with the chromatic number of \(H\), which is of no concern to us. Finally, we write \((H,\chi)\) for the \(q\)-colorful subgraph of \(G\), where we implicitly restrict \(\chi\) to the vertex set of \(H\).

Let \(q\) be a non-negative integer and \((G,\chi)\) be a \(q\)-colorful graph. Let \(r\geq 3\) be an integer and \(M\) be an \((r \times r)\)-mesh in \(G\) such that \(M\) is flat in \(G\) witnessed by a sphere-rendition \(\rho\). We say that \(M\) is homogeneous in \((G,\chi)\) if for every cycle \(C\subseteq M\) it holds that \[\begin{align} \chi( \mathsf{int} (C) ) = \chi( \mathsf{compass} (M) ). \end{align}\]

We stress that the definition for homogeneity above, as well as the following definitions, are slightly more general than they would need to be for our purposes. However, the results we will be using from the literature have been proven in this general setting and to adapt them to simpler variants sufficient for our setting appears tedious. While such an adaptation is clearly possible, it would not provide any substantial improvement for the involved functions as the general bound of \(2^{\mathbf{poly}(k + r)}\) is already best possible up to the degree of the polynomial. Therefore, we opt for a minimisation in technical proofs in exchange for slightly overloaded definitions. The one simplification we are going to take, however, is the same we have done for our statement of . That is, we are not taking full advantage of the Folio problem and instead constrain ourselves to the definition of strong \((k,R)\)-irrelevancy as given right before the statement of .

The main problem now is to provide a definition for the colours we assign to our vertices in order to model the properties required for our case. The definitions below are much more general than necessary as they provide enough additional information to extend from Spanning Disjoint Paths to a folio variant. It might well be possible to remove any dependencies on the respective collections of rooted minors inside the cells, but as mentioned before, to remove these dependencies one would need to open the black box of the Graph Minors Algorithm further.

5.2.0.4 Rooted graphs.

Let \(k\geq 0\) be an integer. A \(k\)-rooted graph is a pair \((G,\mathcal{R})\) where \(\mathcal{R} = \{ r_1,r_2,\dots,r_k \} \subseteq V(G)\) is a multiset of \(k\) not necessarily distinct vertices. We sometimes write \((G,r_1,\dots,r_k)\) instead of \((G,\mathcal{R})\). The \(r_i\) are called the roots of \((G,\mathcal{R})\). A pair \((G,\mathcal{R})\) is a rooted graph if it is a \(k\)-rooted graph for some \(k\).

We stress that there is a huge difference between rooted graphs and annotated graphs. While at first glance both concepts might look fairly similar, in an annotated graph, all annotated vertices are – essentially – interchangeable. In some sense one may interpret a \(k\)-rooted graph \((G,\mathcal{R})\) as a \(k\)-colorful graph where for each \(i\in[k]\) there is a unique vertex of \(G\) that carries colour \(i\). In this sense, the idea of rooted minors is fairly similar to the idea of red-minors, or more general of colorful minors of \(k\)-colorful graphs. There is one key difference though and that is that we are no longer allowed to forget that some vertices were annotated – or carried a colour. This means, for rooted minors, all roots are required to be preserved in some way.

5.2.0.5 The \(d\)-folio of a rooted graph.

A rooted graph \((H,q_1,\dots,q_k)\) is a rooted minor of another rooted graph \((G,r_1,\dots,r_k)\) if there exists a minor model \(\varphi\) of \(H\) in \(G\) such that for every \(i\in[k]\) it holds that \(r_i \in \varphi(q_i)\).

Given an integer \(d\geq 0\) and a rooted graph \((G,\mathcal{R})\), the \(d\)-folio of \(G\), denoted as \(d\text{-}\mathsf{folio}(G,\mathcal{R})\), is the set of all rooted graphs \((H,\mathcal{Q})\) of detail at most \(d\) that are rooted minors of \((G,\mathcal{R})\).

5.2.0.6 Augmenting cells.

Let \(a,r \in \mathbb{N}\) with \(r \geq 3\). Let \(G\) be a graph, \(A \subseteq V(G)\) be a set of at most \(a\) vertices, and let \(M\) be an \((r \times r)\)-mesh in \(G\) that is flat in \(G-A\) witnessed by the sphere rendition \(\rho\). We denote by \(C(M)\) the collection of all cells contained in the disc defined by the trace of the perimeter of \(M\) which contains all non-perimeter vertices of \(M\) of degree \(3\).

For each cell \(c \in C(M)\) we consider a labelling \(\lambda_c \colon N(c) \to [3]\) such that the set of labels assigned by \(\lambda_c\) to \(N(c)\) is one of \([1]\), \([2]\), or \([3]\). In addition, we consider a bijection \(\alpha_A \colon A \to [a]\).

The labellings \(\lambda_c\) and \(\alpha_A\) will be used to fix labels for the boundaries of the annotated graphs \((G[V(\sigma(c)) \cup A],N(c) \cup A)\) to translate them into rooted graphs.

Let \(c \in C(M)\), we define the ordering \(\Omega_c \mathrel{\vcenter{:}}= \langle x_1,\dots,x_{\ell}\rangle\) with \(\ell \leq 3\) of the vertices of \(N(c)\) such that the following holds:

1. \(\langle x_1,\dots,x_q\rangle\) is a counter clockwise cyclic ordering of the vertices of \(N(c)\) as they appear on the boundary of \(c\) in \(\rho\) and

2. for each \(i\in[q]\) we have that \(\lambda_c(x_i) = i\).

For each cell \(c \in C(W)\) we fix \(\pi_c \colon A \cup N(c) \to [a + |N(c)|]\) such that \(\pi_c(x) = \alpha_A(x)\) for all \(x \in A\) and \(\pi_c(x) - a = \lambda_c(x)\) for all \(x \in N(c)\). Finally, the augmented cell \(c\) is defined as the rooted graph \[\begin{align} \mathbf{R}_c \mathrel{\vcenter{:}}= (G[V(\sigma(c) \cup A)],r_1,\dots,r_{a + |N(c)|}) \end{align}\] where \(r_i = \pi_c^{-1}(i)\) for all \(i \in [ a + |N(c)| ]\). We denote the graph \(G[V(\sigma(c) \cup A)]\) by \(R_c\).

5.2.0.7 Palettes of augmented cells.

With each \(c \in C(M)\) we associate a set of graphs as follows.

Let \(d \geq 0\) be an integer. We denote by \(d\text{-}\mathsf{palette}(c)\) the set \(d\text{-}\mathsf{folio}(\mathbf{R}_c)\) which is referred to as the \(d\)-palette of \(c\).

Notice that \(| d\text{-}\mathsf{palette}(c) | \in 2^{\mathbf{O}((a + d)^2)}\). In the following, the set of all rooted graphs of detail at most \(d\) with at most \(a + 3\)  roots is treated as the set of colours for our colorful graph. This means, in particular, that \(q \in 2^{(a + d)^2}\).

5.2.0.8 A \(d\)-folio homogeneous wall.

Let \(a,r \in \mathbb{N}\) with \(r \geq 3\). Let \(G\) be a graph \(A \subseteq V(G)\) a set of at most \(a\) vertices and let \(M\) be an \((r \times r)\)-mesh in \(G\) that is flat in \(G-A\) witnessed by the sphere rendition \(\rho\). We define the \((d,A,M,\rho)\)-folio augmentation of \(G\), denoted by \((G^{(d,A,M,\rho)},\phi)\), as the colorful graph obtained from \(G\) by introducing, for each \(c \in C(M)\), a vertex \(x_c\) adjacent to exactly the vertices of \(N(c)\), setting \(\phi(v) \mathrel{\vcenter{:}}= \emptyset\) for all \(v\in V(G)\) and \(\phi(c) \mathrel{\vcenter{:}}= d\text{-}\mathsf{palette}(c)\) for every \(c \in C(M)\). Notice that \(\rho\) may be extended to a sphere rendition \(\rho'\) of \(G^{(d,A,M,\rho)} - A\) such that \(\rho\) is the restriction of \(\rho'\) to \(G - A \subseteq G^{(d,A,M,\rho)} - A\) simply by setting \(\sigma_{\rho'} \mathrel{\vcenter{:}}= \sigma(c) + x_c\) for all \(c\in C(M)\) and \(\sigma_{\rho'}(c) \mathrel{\vcenter{:}}= \sigma(c)\) for all \(c \in C(\rho) \setminus C(M)\). We call \(\rho'\) the \(\rho\)-augmentation for \(G^{(d,A,M,\rho)}\).

In particular, \(M\) is still flat in \(G^{(d,A,M,\rho)} - A\) as witnessed by \(\rho'\).

Now, \(M\) is said to be \((d,A)\)-folio homogeneous in \(G\) if \(M\) is homogeneous in \((G^{(d,A,W,\rho)} - A,\phi)\).

5.2.0.9 Suspended meshes.

Let \(r\geq 4\). Given a flat mesh \(M\) in a graph \(G\) witnessed by a sphere rendition \(\rho\), we say that a cell \(c\in C(M)\) is an inner cell of \(M\) if the second and third layer of \(M\) separate \(N(c)\) from the perimeter of \(M\) in \(G\).

Let \(r \geq 4\) be an integer. Let \(G\) be a graph and \(M \subseteq G\) be an \((r \times r)\)-mesh in \(G\). We say that \(M\) is a suspended \((r\times r)\)-mesh – or simply a suspended mesh – in \(G\) if there exists a sphere-rendition \(\rho\) of \(G-A\) such that \(M\) is flat in \(\rho\) and for every cell \(c\in C(M)\) the following two properties hold:

1. for every non-empty set \(S \subseteq N(c)\) there exists a connected subgraph of \(\sigma(c)\) containing all vertices from \(S\) and avoiding all vertices from \(N(c)\setminus S\) and

2. there exist \(|N(c)|\) vertex-disjoint paths from \(N(c)\) to the perimeter of \(M\).

We say that \(\rho\) witnesses that \(M\) is suspended in \(G\).

5.2.0.10 Finding an irrelevant vertex.

We are now ready to combine all of the imported technology above with to prove that the centre of any large enough suspended flat and blank mesh is irrelevant for the Spanning Disjoint Paths problem.

6 The Spanning Linkage Algorithm↩︎

We now have everything in place to finalise the algorithmic part of our main theorems. Indeed, and provide the foundation for finding the irrelevant vertex. All we need to do is to ensure that, in any graph of large treewidth we can either find a large clique minor or a large suspended and homogeneous flat mesh efficiently. Once this is done, the data reduction part of our algorithm is established. Finally, we require a routine that solves \(k\)-Spanning Disjoint Paths in the regime of bounded treewidth.

We begin by describing the algorithm overall and then, in the subsequent subsections, fill in the two missing steps outlined above. We describe the algorithm in slightly more detail, elaborating on some crucial subroutines as we go. One addition we are making is the use of a theorem due to Reed and Wood [57] which allows us to quickly find a large clique minor or to determine that the number of edges in our instance is linear in the number of vertices. The only reason we have this step is to ensure that our final running time is \(\mathbf{O}(n^2)\) rather than \(\mathbf{O}(n \cdot m)\).

6.0.0.1 The Spanning Linkage Algorithm.

 

Input: An annotated graph \((G,R)\) together with a set \(\mathcal{T} = \{ (s_i,t_i) \mid i\in[k] \}\) of \(k\) terminal pairs and an integer \(r \geq 1\).

Step 1.

Input: An instance \((G,R,\mathcal{T})\) of \(k\)-Spanning Disjoint paths.

Procedure: Check if \(G\) contains a \(K_t\)-minor model \(\varphi\) with \(t \mathrel{\vcenter{:}}= \lfloor \frac{5}{2} (2(r+1)^2 + 2k) \rfloor + 1\) using . If the outcome is yes, forward \((G,R,\mathcal{T})\) and \(\varphi\) to Step 1.1, otherwise proceed to Step 2.

Step 1.1.

Input: An instance \((G,R,\mathcal{T})\) of \(k\)-Spanning Disjoint paths where \(\mathsf{depth}_2(G,R) \leq r\) together with a \(K_t\)-minor model \(\varphi\) in \(G\).

Procedure: Apply to either find an irrelevant vertex \(v \in V(G)\setminus R\) or determine that \(\mathsf{depth}_2(G,R) > r\). In the second case reject the instance and in the first case forward \((G-v,R,\mathcal{T})\) to Step 1.

Step 2:

Input: An instance \((G,R,\mathcal{T})\) of \(k\)-Spanning Disjoint paths.

Procedure: Apply the algorithm from to find one of the following outcomes:

1. a \(K_t\)-minor model \(\varphi\) in \(G\),

2. a tree-decomposition \(\mathcal{D}\) of width at most \(f_{\ref{prop95FindGoodFlatWall}}(t) \cdot f_{\ref{thm95IrrelevantInMesh}}(r,k)\) for \(G\), or

3. a set \(A \subseteq V(G)\), where \(|A| \leq g_{\ref{prop95FindGoodFlatWall}(t)}\) together with an \((f_{\ref{thm95IrrelevantInMesh}}(r,k) \times f_{\ref{thm95IrrelevantInMesh}}(r,k))\)-mesh \(M\) that is flat and suspended in \(G-A\) as witnessed by the sphere-rendition \(\rho\) and the treewidth of \(M\) in \(G\) is at most \(f_{\ref{prop95FindGoodFlatWall}}(t) \cdot f_{\ref{thm95IrrelevantInMesh}}(r,k)\).

In case i), forward \((G,R,\mathcal{T})\) and \(\varphi\) to Step 1.1. In case ii), forward \((G,R,\mathcal{T})\) to Step 4, and in case iii) forward \((G,R,\mathcal{T})\), \(A\), \(M\), and \(\rho\) to Step 3.

Step 3.

Input: An instance \((G,R,\mathcal{T})\) of \(k\)-Spanning Disjoint paths, together with a set \(A \subseteq V(G)\setminus R\) where \(|A| \leq g_{\ref{prop95FindGoodFlatWall}(t)}\) together with an \((f_{\ref{thm95IrrelevantInMesh}}(r,k) \times f_{\ref{thm95IrrelevantInMesh}}(r,k))\)-mesh \(M\) that is flat and suspended in \(G-A\) as witnessed by the sphere-rendition \(\rho\) and the treewidth of \(M\) in \(G\) is at most \(f_{\ref{prop95FindGoodFlatWall}}(t) \cdot f_{\ref{thm95IrrelevantInMesh}}(r,k)\).

Procedure: Run the algorithm from to either (i) determine that \(\mathsf{depth}_2(G,R) > r\), in which case we reject the instance, or (ii) find a vertex \(v \in V(G) \setminus R\) such that \((G,R,\mathcal{T})\) is a yes-instance if and only if \((G-v,R,\mathcal{T})\). In case (ii) forward \((G-v,R,\mathcal{T})\) to Step 2.

Step 4.

Input: An instance \((G,R,\mathcal{T})\) of \(k\)-Spanning Disjoint paths where \(\mathsf{tw}(G) \leq f_{\ref{prop95FindGoodFlatWall}}(t) \cdot f_{\ref{thm95IrrelevantInMesh}}(r,k)\).

Procedure: Apply the algorithm from to \((G,R,\mathcal{T})\) to determine whether \((G,R,\mathcal{T})\) is a yes- or no-instance. Return the outcome.

With the Spanning Linkage Algorithm established, we are ready to state the main theorem of this section.

Notice that the Spanning Linkage Algorithm closes a loop only if an irrelevant vertex has been found. Hence, the algorithm iterates through at most \(n\) loops. Since all subroutines called throughout the algorithm have linear running times, this immediately yields the desired \(\mathbf{O}(n^2)\) bound. The double-exponential dependency on \(r + k\) then follows from the individual subroutines. Finally, to see that the algorithm is correct, one only needs to observe that – under the assumption that \(\mathsf{depth}_2(G,R) \leq 2\) – each subroutine correctly finds an irrelevant vertex or produces the desired outcome. Hence, all that is left to do is prove and to complete the proof of .

We stress that, although is stated for the decision version of \(k\)-Spanning Disjoint Paths, the algorithm from can be modified to also find a solution in the same time and thus, the Spanning Linkage Algorithm is able to find a solution – given that one exists.

6.1 Finding an irrelevant vertex↩︎

The goal of this subsection is to piece together several parts of the previously established toolset with some additional tools from the literature in order to find an irrelevant vertex whenever we are presented with a large flat mesh.

6.1.0.1 Quickly finding a suspended flat mesh.

One subroutine we are still missing is a way to quickly find a suspended flat mesh. Indeed, for this we require two additional results from the literature.

The first allows us to immediately reduce any flat mesh to one with a blank compass.

The second is the one that actually finds the suspended flat mesh.

6.1.0.2 Finding a folio homogeneous mesh.

Let \(G\) be a graph and \(M \subseteq G\) be a flat wall in \(G\) witnessed by the sphere rendition \(\rho\). The treewidth of \(M\) in \(G\) is the smallest integer \(w\) such that the treewidth of the compass of \(M\) in \(\rho\) is at most \(w\).

With this, we are finally ready to import the key tools from the work of Cavallaro, Gorsky, Kreutzer, Thilikos, and Wiederrecht [16] that will drive our later machinery.

We are now ready to proceed with the proof of .

6.2 The case of bounded treewidth↩︎

Deleting irrelevant vertices reduces every instance of bounded \(\mathsf{depth}_2\) to an equivalent one whose treewidth is bounded in terms of \(k\) and \(\mathsf{depth}_2\); it then remains to solve such a bounded-treewidth instance. This subsection supplies the algorithm for that case.

The algorithm is a standard dynamic programming over a tree decomposition, and the only point requiring care is that the table must witness the spanning condition. We use a tree decomposition in which every bag contains the terminals and has width \(\mathbf{O}(k+\mathsf{tw}(G))\), and at each node we record, for every partial linkage pattern on the bag, whether it admits a realisation covering every vertex of \(R\) already processed, the vertices of \(R\) still isolated in the current bag being left to be covered later. As there are \(2^{\mathbf{poly}(k+\mathsf{tw}(G))}\) such patterns per node, the decision follows in time \(2^{\mathbf{poly}(k+\mathsf{tw}(G))}\cdot|G|\).

The above algorithm may also keep track, for each \(t\in V(T)\), of a set of \(Z\)-realisations in \(G_t\), for all \(Z\in\mathcal{P}(t)\). The knowledge of these sets makes is possible to construct a solution, i.e., the disjoint paths between the terminals of \(\mathcal{T}\) that span \(R\), in case \((G,R,\mathcal{T})\) is a yes-instance.

Notice that an easy modification of the above can also solve the optimisation version of SDP, that is to compute \(\textsf{max}_\mathsf{SDP}(G,R,\mathcal{T})\): the maximum size of a subset \(R'\) of \(R\) for which \((G,R,\mathcal{T})\) is a Yes-instance of SDP. The only that changes is that now, instead of \(\mathsf{table}_{t}\colon \mathcal{P}(t)\to\{0,1\}\), we compute \(\mathsf{maxtable}_{t}: \mathcal{P}(t)\to\mathbb{N}\) where \(\mathsf{maxtable}_{t}(Z)\) is the maximum size of a subset \(R'\) of \(R\cap V(G_t)\) where there is a \(Z\)-realisation \(\mathcal{C}_{Z}\) in \(G_t\) and 5 holds with \(R\) replaced by \(R'\).

7 Irrevelant-vertex tightness↩︎

Let us now denote by \(\mathcal{X}\) the class of all annotated graphs \(\mathbf{H}\) such that there exists a \(2\)-outer-annotated grid \(\mathbf{G}\) such that \(\mathbf{H}\) is a red-minor of \(\mathbf{G}\).

With and we have established the positive part of our main result. That is, in every red-minor-closed class \(\mathcal{C}\), if it does not contain the entire class \(\mathcal{X}\), then there exists an irrelevant vertex rule for the \(k\)-Spanning Disjoint Paths problem. In particular, if \(\mathcal{X} \not\subseteq \mathcal{C}\), then there exists a Vital Linkage Theorem for \(k\)-Spanning Disjoint Paths. In this section we prove the reverse. That is, we show that for every \(w \in \mathbb{N}\), \(\mathcal{X}\) contains an annotated graph \((G_w,R_w)\) such that there are vertices \(s,t \in V(G_w)\) for which \((G_w,R_w,\{ (s,t)\})\) is a vital instance of \(1\)-Spanning Disjoint Paths while \(\mathsf{tw}(G_w) \geq w\). This shows that a variant of for \(\mathcal{X}\) cannot hold and therefore implies, in particular, that \(TC(\mathcal{X})\) does not have the irrelevant vertex property.

Our construction is inductive and finally requires two types of gadgets. Each gadget will have a certain amount of “entries” and “exists” together with two ordered sets of interface vertices which exist mainly to propagate the construction. These Interface vertices will be of degree \(1\) and will not be part of the vital instance hidden inside. Roughly speaking, we differentiate between two gadgets: A forward gadget and a backward gadget. Both gadgets have an intrinsic orientation which we signify by left and right. The forward gadget has a single entry on the left and a single exit on the right. See for a schematic illustration. The backward gadget on the other hand appears in two incarnations (which differ in a single edge). The core backward gadget is a two way, it has an entry on the left that is connected to an exit on the right, and it has an entry on the right connected to an exist to the left. The second incarnation of the backward gadget is obtained from the core construction by adding an edge – subdivided with a red vertex – connecting the exit on the left to the entry on the left. Hence, this gadget has a single entry and a single exit, both on the right. See for an illustration.

7.1 Constructing a vital instance↩︎

Let us now formalise the construction. As explained before we will have two main gadgets which we identify by its “orientation”. Each higher-order gadget is then constructed out of two copies of its own type one level lower plus one copy of the other kind from one level below.

7.1.0.1 Base constructions.

We start with the base of our induction.

The gadget \(\mathbf{forward}_1\) is the tuple \((G_{\mathbf{f},1},R_{\mathbf{f},1},s,t,\ell_1,r_1)\) defined as follows. The graph \(G_{\mathbf{f},1}\) has vertex set \(\{ s,t,x,\ell_1,r_1,z_1,z_2\}\) where \(R_{\mathbf{f},1} \mathrel{\vcenter{:}}= \{ z_1,z_2\}\). The edge set of \(G_{\mathbf{f},1}\) is \(\{ sz_1, z_1x, xz_2, z_2t, \ell_1x, xr_1\}\).

The vertex \(s\) is the unique entry of \(\mathbf{forward}_1\) and the vertex \(t\) is the unique exit of \(\mathbf{forward}_1\). The left interface is \(\{ \ell_1\}\) and the right interface is \(\{ r_1\}\). The path \(P_1= \langle \ell_1,x,r_1\rangle\) is the \(1\)st row of \(\mathbf{forward}_1\).

The gadget \(\mathbf{backward}_1\) is the tuple \((G_{\mathbf{b},1},R_{\mathbf{b},1},s_1,t_1,s_2,t_2,\ell_1,r_1)\) defined as follows. The graph \(G_{\mathbf{b},1}\) has vertex set \(\{ s_1,t_1,s_2,t_2,x,\ell_1,r_1,y,z_1,z_2\}\) where \(R_{\mathbf{b},1} \mathrel{\vcenter{:}}= \{ y,z_1,z_2\}\). The edge set of \(G_{\mathbf{b},1}\) is \(\{ t_2z_1, z_1x, xz_2, z_2s_2, s_1y, yt_1, \ell_1x, xr_1\}\).

The vertices \(s_1\) and \(s_2\) are the entries of \(\mathbf{backward}_1\) and the vertices \(t_1\) and \(t_2\) are the exists of \(\mathbf{backward}_1\). The left interface is \(\{ \ell_1\}\) and the right interface is \(\{ r_1\}\). The path \(P_1= \langle \ell_1,x,r_1\rangle\) is the \(1\)st row of \(\mathbf{backward}_1\). See for illustrations of \(\mathsf{forward}_1\) and \(\mathsf{backward}_1\).

Generally speaking, in each level of our construction we will have a left and a right interface, denotes as \(\{ \ell_1,\dots,\ell_n\}\) and \(\{ r_1,\dots,r_n\}\) respectively. For \(i \in [n]\), the \(i\)th left (right) interface will refer to the vertex \(\ell_i\) (\(r_i\)).

Before we describe the full inductive construction, let us make one more illustration in form of the construction of \(\mathbf{forward}_2\) and \(\mathbf{backward}_2\).

The gadget \(\mathbf{forward}_2\) is the tuple \((G_{\mathbf{f},2},R_{\mathbf{f},2},s,t,\ell_1,\ell_2,r_1,r_2)\) obtained as follows. Let \(\mathbf{L} = (L,R_L,s_L,t_L,\ell^1_L,r^1_{L})\) and \(\mathbf{R} = (R,R_R,s_R,t_R,\ell^1_R,r^1_{R})\) be two disjoint copies of \(\mathbf{forward}_1\). Moreover, let \(\mathbf{M} = (M,R_M,s^1_M,t^1_M,s^2_M,t^2_M,\ell^1_M,r^1_{M})\) be a copy of \(\mathbf{backward}_1\) disjoint from both \(\mathbf{L}\) and \(\mathbf{R}\). The graph \(G_{\mathbf{f},2}\)is obtained by

• first identifying \(r^1_L\) and \(\ell^1_M\) into the vertex \(a_1\) and \(r^1_M\) and \(\ell^1_R\) into the vertex \(b_1\), then

• adding new vertices \(\ell_2\), \(x\), and \(r_2\) together with the edges \(\ell_2x\) and \(xr_2\), then

• adding the edges \(a_1x\) and \(xb_1\), and finally,

• adding the edges \(t_La_1\), \(b_1s^2_M\), \(t^2_Ms^1_M\), and \(t^1_Ms_R\).

We set \(s \mathrel{\vcenter{:}}= s_L\) and \(t \mathrel{\vcenter{:}}= t_R\), and \(R_{\mathbf{f},2} \mathrel{\vcenter{:}}= R_L \cup R_M \cup R_R\). Moreover, we declare \(\ell_1 \mathrel{\vcenter{:}}= \ell^1_L\) and \(r_1 \mathrel{\vcenter{:}}= r^1_R\) such that \(\{ \ell_1,\ell_2\}\) is the left interface of \(\mathbf{forward}_2\) and \(\{ r_1,r_2\}\) is its right interface.

Notice that the construction of \(\mathbf{forward}_2\) crucially uses a modification of \(\mathbf{backward}_1\) where the exit \(t_2\) and the entry \(s_1\) are being linked by an edge.

The gadget \(\mathbf{backward}_2\) is the tuple \((G_{\mathbf{b},2},R_{\mathbf{b},2},s_1,t_1,s_2,t_2,\ell_1,\ell_2,r_1,r_2)\) obtained as follows. Let \(\mathbf{L} = (L,R_L,s^1_L,t^1_L,s^2_L,t^2_L\ell^1_L,r^1_{L})\) and \(\mathbf{R} = (R,R_R,s^1_R,t^1_R,s^2_R,t^2_R,\ell^1_R,r^1_{R})\) be two disjoint copies of \(\mathbf{backward}_1\). Moreover, let \(\mathbf{M} = (M,R_M,s_M,t_M,\ell^1_M,r^1_{M})\) be a copy of \(\mathbf{forward}_1\) disjoint from both \(\mathbf{L}\) and \(\mathbf{R}\). The graph \(G_{\mathbf{b},2}\)is obtained by

• first identifying \(r^1_L\) and \(\ell^1_M\) into the vertex \(a_1\) and \(r^1_M\) and \(\ell^1_R\) into the vertex \(b_1\), then

• adding new vertices \(\ell_2\), \(x\), and \(r_2\) together with the edges \(\ell_2x\) and \(xr_2\), then

• adding the edges \(a_1x\) and \(xb_1\), and finally,

• adding the edges \(s^2_La_1\), \(t^1_Ls_M\), \(b_1t^2_R\), and \(t_Ms^1_R\).

We set \(s_1 \mathrel{\vcenter{:}}= s^1_L\), \(s_2 \mathrel{\vcenter{:}}= s^2_R\), \(t_1 \mathrel{\vcenter{:}}= t^1_R\) and \(t_2 \mathrel{\vcenter{:}}= t^2_L\), and \(R_{\mathbf{b},2} \mathrel{\vcenter{:}}= R_L \cup R_M \cup R_R\). Moreover, we declare \(\ell_1 \mathrel{\vcenter{:}}= \ell^1_L\) and \(r_1 \mathrel{\vcenter{:}}= r^1_R\) such that \(\{ \ell_1,\ell_2\}\) is the left interface of \(\mathbf{backward}_2\) and \(\{ r_1,r_2\}\) is its right interface.

Notice that each of the level \(1\) gadgets has a path joining \(\ell_1\) to \(r_1\) whose edges are not being used in the \(R\)-spanning \(s\)-\(t\)-path (or the two \(R\)-spanning paths in the backward gadget). The level \(2\) gadgets maintain this property and add a second path \(P_2\) with similar properties connecting \(\ell_2\) and \(r_2\). Moreover, the level \(2\) constructions also contain a path \(U\) from \(a_1\) to \(b_1\) which intersects \(P_2\) precisely in the vertex \(x\). As we will see later, this path \(U\) must always be used by any solution. If we now interpret the area of the level \(2\) gadget containing all red vertices as a vortex, then \(U\) forms a simple loop on the boundary of this vortex. Indeed, this is precisely the viewpoint we wish to induce. Recall our proofs of and . Here, it was crucial to observe that many “stacked” simple loops provide enough infrastructure to reroute a given solution, thereby showing that the instance was not vital. Our goal is to stack more and more such simple loops onto \(U\) by increasing the level, while also showing that these simple loops must always be used in every solution to the corresponding instance of Spanning Disjoint Paths. If this succeeds, an argument similar to the one from will then find a large bramble in these gadgets that is unavoidable.

let now \(n \geq 2\) be an integer. We continue with the description of the general level \(n\) construction.

The gadget \(\mathbf{forward}_n\) is the tuple \((G_{\mathbf{f},n},R_{\mathbf{f},n},s,t,\ell_1,\dots,\ell_n,r_1,\dots,r_n)\) obtained as follows. Let \(\mathbf{L} = (L,R_L,s_L,t_L,\ell^1_L,\dots \ell^{n-1}_L,r^1_{L},\dots,r^{n-1}_L)\) and \(\mathbf{R} = (R,R_R,s_R,t_R,\ell^1_R,\dots,\ell^{n-1}_R,r^1_{R},\dots,r^{n-1}_R)\) be two disjoint copies of \(\mathbf{forward}_{n-1}\). In addition, we consider a copy of \(\mathbf{backward}_{n-1}\) disjoint from both \(\mathbf{L}\) and \(\mathbf{R}\) denotes as \(\mathbf{M} = (M,R_M,s^1_M,t^1_M,s^2_M,t^2_M,\ell^1_M,\dots,\ell^{n-1}_M,r^1_{M},\dots,r^{n-1}_M)\). The graph \(G_{\mathbf{f},n}\)is obtained by

• first identifying \(r^i_L\) and \(\ell^i_M\) into the vertex \(a_i\) and \(r^i_M\) and \(\ell^i_R\) into the vertex \(b_i\) for each \(i\in[n-1]\), then

• adding new vertices \(\ell_n\), \(x\), and \(r_n\) together with the edges \(\ell_nx\) and \(xr_n\),

• adding the edges \(a_ia_{i+1}\) and \(b_ib_{i+1}\) for all \(i \in [n-2]\), then

• adding the edges \(a_{n-1}x\) and \(xb_{n-1}\), and finally,

• adding the edges \(t_La_1\), \(b_1s^2_M\), \(t^2_Ms^1_M\), and \(t^1_Ms_R\).

We set \(s \mathrel{\vcenter{:}}= s_L\) and \(t \mathrel{\vcenter{:}}= t_R\), and \(R_{\mathbf{f},2} \mathrel{\vcenter{:}}= R_L \cup R_M \cup R_R\). Moreover, we declare \(\ell_i \mathrel{\vcenter{:}}= \ell^i_L\) and \(r_i \mathrel{\vcenter{:}}= r^i_R\) for all \(i \in[n-1]\) such that \(\{ \ell_1,\dots,\ell_n\}\) is the left interface of \(\mathbf{forward}_n\) and \(\{ r_1,\dots,r_n\}\) is its right interface. Additionally, we call the path \(U_n\) the \(n\)th loop of \(\mathbf{forward}_n\). If we denote by \(U_1,\dots,U_{n-1}\) the \(n-1\) loops of \(\mathbf{M}\), then those together with \(U_n\) become the \(n\) loops of \(\mathbf{forward}_n\). Similarly, the \(n\)th row of \(\mathbf{forward}_n\) is the path \(P_n = \langle \ell_n,x,r_n\rangle\) and for \(i \in [n-1]\), the \(i\)th row of \(\mathbf{forward}_n\) is the path \(P_i\) obtained from the union of the \(i\)th rows of \(\mathbf{L}\), \(\mathbf{M}\), and \(\mathbf{R}\).

The gadget \(\mathbf{backward}_n\) is the tuple \((G_{\mathbf{b},n},R_{\mathbf{b},n},s_1,t_1,s_2,t_2,\ell_1,\dots,\ell_n,r_1,\dots,r_n)\) obtained as follows. Let \(\mathbf{L} = (L,R_L,s^1_L,t^1_L,s^2_L,t^2_L,\ell^1_L,\dots \ell^{n-1}_L,r^1_{L},\dots,r^{n-1}_L)\) and \(\mathbf{R} = (R,R_R,s^1_R,t^1_R,s^2_R,t^2_R,\ell^1_R,\dots,\ell^{n-1}_R,r^1_{R},\dots,r^{n-1}_R)\) be two disjoint copies of \(\mathbf{backward}_{n-1}\). In addition, we consider a copy of \(\mathbf{fowward}_{n-1}\) disjoint from both \(\mathbf{L}\) and \(\mathbf{R}\) denotes as \(\mathbf{M} = (M,R_M,s_M,t_M,\ell^1_M,\dots,\ell^{n-1}_M,r^1_{M},\dots,r^{n-1}_M)\). The graph \(G_{\mathbf{b},n}\)is obtained by

• first identifying \(r^i_L\) and \(\ell^i_M\) into the vertex \(a_i\) and \(r^i_M\) and \(\ell^i_R\) into the vertex \(b_i\) for each \(i\in[n-1]\), then

• adding new vertices \(\ell_n\), \(x\), and \(r_n\) together with the edges \(\ell_nx\) and \(xr_n\),

• adding the edges \(a_ia_{i+1}\) and \(b_ib_{i+1}\) for all \(i \in [n-2]\), then

• adding the edges \(a_{n-1}x\) and \(xb_{n-1}\), and finally,

• adding the edges \(s^2_La_1\), \(t^1_Ls_M\), \(b_1t^2_R\), and \(t_Ms^1_R\).

We set \(s_1 \mathrel{\vcenter{:}}= s^1_L\), \(s_2 \mathrel{\vcenter{:}}= s^2_R\), \(t_1 \mathrel{\vcenter{:}}= t^1_R\) and \(t_2 \mathrel{\vcenter{:}}= t^2_L\), and \(R_{\mathbf{b},2} \mathrel{\vcenter{:}}= R_L \cup R_M \cup R_R\). Moreover, we declare \(\ell_i \mathrel{\vcenter{:}}= \ell^i_L\) and \(r_i \mathrel{\vcenter{:}}= r^i_R\) for all \(i \in[n-1]\) such that \(\{ \ell_1,\dots,\ell_n\}\) is the left interface of \(\mathbf{backward}_n\) and \(\{ r_1,\dots,r_n\}\) is its right interface. Additionally, we call the path \(U_n\) the \(n\)th loop of \(\mathbf{backward}_n\). If we denote by \(U_1,\dots,U_{n-1}\) the \(n-1\) loops of \(\mathbf{M}\), then those together with \(U_n\) become the \(n\) loops of \(\mathbf{backward}_n\). Similarly, the \(n\)th row of \(\mathbf{backward}_n\) is the path \(P_n = \langle \ell_n,x,r_n\rangle\) and for \(i \in [n-1]\), the \(i\)th row of \(\mathbf{backward}_n\) is the path \(P_i\) obtained from the union of the \(i\)th rows of \(\mathbf{L}\), \(\mathbf{M}\), and \(\mathbf{R}\).

Before we move on, let us observe that \(\mathbf{forward}_n\) and \(\mathbf{backward}_n\) are indeed members of \(\mathcal{X}\) for all \(n \in \mathbb{N}_{\geq 1}\).

7.2 Treewidth of the instances↩︎

To see that the graphs of \(\mathbf{forward}_n\) and \(\mathbf{backward}_n\) have treewidth in \(\mathbf{O}(n)\) is relatively straightforward. In essence, we may use the loops and rows to construct a bramble similar to the way we have constructed brambles in several of the proof in earlier sections.

7.3 Vitality of the instances↩︎

All that is left is to show that the instances of \(1\)-Spanning Disjoint Paths and \(2\)-Spanning Disjoint Paths generated by \(\mathbf{forward}_n\) and \(\mathbf{backward}_n\) are vital.

Let \(G_{\mathbf{f}n,}^{\star}\) be the graph obtained from the graph \(G_{\mathbf{f},n}\) of \(\mathbf{forward}_n\) by deleting all of its interface vertices. Similarly, let \(G_{\mathbf{b},n}^{\star}\) be the graph obtained from the graph \(G_{\mathbf{b},n}\) of \(\mathbf{backward}_n\) by deleting all of its interface vertices. Then, \((G^{\star}_{\mathbf{f},n},R_{\mathbf{f},n},\{ (s,t) \})\) is the instance of \(1\)-Spanning Disjoint Paths generated by \(\mathbf{forward}_n\) while \((G^{\star}_{\mathbf{b},n},R_{\mathbf{b},n},\{ (s_1,t_1), (s_2,t_2)\})\) is the instance of \(2\)--Spanning Disjoint Paths generated by \(\mathbf{backward}_n\).

Combining no gives the following theorem on the non-existence of a variant of .

8 Conclusion↩︎

In this paper we identify \(\mathsf{depth}_2\) as the precise threshold parameter governing the applicability of the Irrelevant Vertex Technique for \(k\)-Spanning Disjoint Paths. This yields an algorithm running in \(2^{2^{\mathbf{poly}(k+d)}}\cdot n^2\) time, where \(k\mathrel{\vcenter{:}}=|\mathcal{T}|\) is the number of terminal pairs and \(d\mathrel{\vcenter{:}}=\mathsf{depth}_2(G,R)\). We stress that our dichotomy is combinatorial rather than algorithmic: it delineates exactly those classes on which the Irrelevant Vertex Technique can be made to work, which is a statement about the reach of a particular method and not about the inherent complexity of the problem. In principle, a class could lie beyond the \(\mathsf{depth}_2\) boundary and still admit a polynomial-time algorithm by some other route. To turn the combinatorial boundary into a complexity-theoretic one, one would therefore need to prove that Spanning Disjoint Paths is NP-complete when restricted to the class of all minors of the \(2\)-outer-annotated \((k\times k)\)-grid, for every \(k\in\mathbb{N}\). As mentioned in the introduction, we cannot exclude that Spanning Disjoint Paths is solvable in polynomial time using other or new algorithmic techniques, and we leave this as an open question.

Another direction is to relax the goal from polynomial-time solvability to fixed-parameter or slice-wise tractability. Concretely, one may ask, for a suitably chosen “tight” annotated parameter \(\mathsf{p}\), for an XP algorithm for Spanning Disjoint Paths with respect to \(\mathsf{p}(G,R)\), the number of terminal pairs \(k=|\mathcal{T}|\), or both. In this direction, we conjecture that Spanning Disjoint Paths can be solved in \(f(d_\infty)\cdot |G|^{f(k)}\), \(f(k)\cdot |G|^{f(d_\infty)}\), or \(|G|^{f(k,d_\infty)}\) time, where \(d_\infty\mathrel{\vcenter{:}}=\mathsf{depth}_\infty(G,R)\); that is, with the exponent of \(|G|\) controlled by only one of the two parameters, or by both together. Establishing any of these bounds would show that bidimensionality yields a tight algorithmic dichotomy, since Spanning Disjoint Paths is NP-complete on planar graphs even when \(k=1\), so no bound with a \(|G|\)-exponent independent of \(d_\infty\) can be expected.

As already mentioned, \(\mathsf{depth}_2\) is only one of infinitely many ways to extend the notion of treewidth to annotated graphs. Recall that, for every \(r\in\mathbb{N}\cup\{\infty\}\), the parameter \(\mathsf{depth}_r\) collapses to treewidth once the graph is fully annotated, and that the two ends of this spectrum already carry names: for \(r=1\) the parameter is called monodimensionality [18], while for \(r=\infty\) it is called bidimensionality [7], [17]. In this sense, as \(r\) grows through the finite values, \(\mathsf{depth}_r\) interpolates between the two, capturing gradually denser degrees of “monodimensionality”. It is natural to ask whether these degrees demarcate dichotomies for other problems as well. A concrete candidate is the Terminal \(d\)-Dominating Cyclability problem, whose input is again an annotated graph \((G,R)\); here, instead of requiring the cycle to pass through every red vertex, we ask for a cycle \(C\) whose vertex set \(d\)-dominates \(R\), in the sense that every vertex of \(R\) lies within distance at most \(d\) from some vertex of \(V(C)\). For \(d=0\) this is exactly Terminal Cyclability, but already for larger \(d\) our techniques do not extend to it under the \(\mathsf{depth}_2\) parameter. Do higher degrees of monodimensionality suffice in that setting, and, if so, when is the resulting threshold tight, either combinatorially (with respect to the Irrelevant Vertex Technique) or algorithmically (with respect to a polynomial algorithm)? Answering this would require, for every \(d\in\mathbb{N}\), a local structure theorem in the spirit of 4. Such a theorem appears considerably more intricate, and difficult even to formulate, than the one we prove here; for the extreme case \(d=\infty\) a corresponding min-max theorem was obtained in [5].

Our paper provides two algorithms, and it is worth separating their roles. The first is the algorithm of 4, which certifies the local structure of annotated graphs of bounded \(\mathsf{depth}_2\) and runs in \(\mathbf{poly}(t+r+w)\cdot |G|^6\) time. The second takes the local structure provided by 4 as its starting point and solves \(k\)-Spanning Disjoint Paths in quadratic time by repeatedly removing irrelevant vertices. We made no attempt to optimise the exponent of \(|G|\) in the first algorithm and leave this for further investigation; in fact, we believe it can be reduced to quadratic, which would bring the preprocessing step in line with the second algorithm.

A further direction would be to find a min-max graph parameter, defined through tree decompositions, that is equivalent to \(\mathsf{depth}_2\). Informally, the torsos of such a decomposition should locally exhibit precisely the structure certified by 4, so that the global parameter records, in a single quantity, the local guarantees our theorem provides wall by wall. Such a min-max theorem could be established using standard local-to-global arguments, as developed in [46], [62], at the cost of an additional factor of \(|G|\) in the running time of the algorithm of 4. We avoided giving the proof of such a theorem, as it is not required for the results of this paper.

Acknowledgement. We wish to thank Petr Golovach for valuable early discussions on several problems about how to span graphs inside graphs.

References↩︎

---

1. Supported by French National Research Agency (ANR) under project GODASse ANR-24-CE48-4377 and under the France 2030 grant reference number ANR-24-RRII-0002 operated by the Inria Quadrant Program.↩︎

2. sedthilk@thilikos.info↩︎

3. Supported by the Institute for Basic Science (IBS-R029-C1).↩︎

4. wiederrecht@kaist.ac.kr↩︎

5. Technically this is not a drawing but an “almost embedding”, but for the sake of this informal description, the intuition of a drawing is sufficient. See for the formal definitions.↩︎