We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restricted to vertex sets of bounded cutrank. We prove the following statements about the expressive power of low rank MSO. - Over any class of graphs that is weakly sparse, low rank MSO has the same expressive power as separator logic. This equivalence does not hold over all graphs. - Over any class of graphs that has bounded VC dimension, low rank MSO has the same expressive power as flip-connectivity logic. This equivalence does not hold over all graphs. - Over all graphs, low rank MSO has the same expressive power as flip-reachability logic. Here, separator logic is an extension of first-order logic by basic predicates for checking connectivity, which was proposed by Bojańczyk [ArXiv 2107.13953] and by Schirrmacher, Siebertz, and Vigny [ACM ToCL 2023]. Flip-connectivity logic and flip-reachability logic are analogues of separator logic suited for non-sparse graphs, which we propose in this work. In particular, the last statement above implies that every property of undirected graphs expressible in low rank MSO can be decided in polynomial time.

Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions of first-order logic such as FO+dp admit efficient model checking on graph classes excluding a fixed topological minor, comparable results for richer fragments of CMSO were previously unknown. We further develop the framework of Sau, Stamoulis, and Thilikos [SODA 2025] for fragmenting CMSO via annotated graph parameters, which restrict set quantification to vertex sets satisfying bounded structural conditions. Following this approach, we identify a fragment of CMSO, namely the one defined by allowing quantification only over sets having what we call low monodimensionality, that generalizes several previously-known logics and we show that model checking for this fragment, enhanced with the disjoint-paths predicate, is fixed-parameter tractable on topological-minor-free graph classes. Such classes essentially delimit the tractability for this logic on subgraph-closed classes. As a consequence, our results lift several known algorithmic meta-theorems beyond first-order logic to the topological-minor-free setting.

For a graph \(G\), the parameter treedepth measures the minimum depth among all forests \(F\), called elimination forests, such that \(G\) is a subgraph of the ancestor-descendant closure of \(F\). We introduce a logic, called neighborhood operator logic with acyclicity, connectivity and clique constraints \((\mathsf{NEO_2[FRec]\!+\!ACK}\) for short\()\), that captures all NP-hard problems—like Independent Set or Hamiltonian Cycle—that are known to be tractable in time \(2^{\mathcal{O}(\mathsf{td})} n^{\mathcal{O}(1)}\) and space \(n^{\mathcal{O}(1)}\) on \(n\)-vertex graphs provided with elimination forests of depth \(\mathsf{td}\). We provide a model checking algorithm for \(\mathsf{NEO_2[FRec]\!+\!ACK}\) with such complexity that unifies and extends these results. For \(\mathsf{NEO_2[FRec]\!+\!K}\), the fragment of the above logic that does not use acyclicity and connectivity constraints, we get a strengthening of this result, where the space complexity is reduced to \(\mathcal{O}(\mathsf{td}\log (n))\).

We show that every \(H\)-minor-free graph that also excludes a \((k \times k)\)-grid as a minor has treewidth/branchwidth bounded from above by a function \(f(t,k)\) that is linear in \(k\) and polynomial in \(t := |V(H)|\). Such a result was proven originally by [Demaine & Hajiaghayi, Combinatorica, 2008], where \(f\) was indeed linear in \(k\). However the dependency in \(t\) in this result was non-explicit (and huge). Later, [Kawarabayashi & Kobayashi, JCTB, 2020] showed that this bound can be estimated to be \(f(t,k) \in 2^{\mathcal O(t \log t)} \cdot k\). Wood recently asked whether \(f\) can be pushed further to be polynomial, while maintaining the linearity on \(k\). We answer this in a particularly strong sense, by showing that the treewidth/branchwidth of \(G\) is in \(\mathcal O(gk + t^{2304})\), where \(g\) is the Euler genus of \(H\). This directly yields \(f(t,k) = \mathcal O(t^2 k + t^{2304})\).

In the Disjoint Shortest Paths problem one is given a graph \(G\) and a set \(\mathcal{T} = \{(s_1,t_1),\ldots,(s_k,t_k)\}\) of \(k\) vertex pairs. The question is whether there exist vertex-disjoint paths \(P_1,\ldots,P_k\) in \(G\) so that each \(P_i\) is a shortest path between \(s_i\) and \(t_i\). While the problem is known to be \(\textsf{W}\)[1]-hard in general, we show that it is fixed-parameter tractable on planar graphs with positive edge weights. Specifically, we propose an algorithm for Planar Disjoint Shortest Paths with running time \(2^{\mathcal{O}(k \log k)} \cdot n^{\mathcal{O}(1)}\). Notably, our parameter dependency is better than state-of-the-art \(2^{\mathcal{O}(k^2)}\) for the Planar Disjoint Paths problem, where the sought paths are not required to be shortest paths.

We show that for any fixed integer k ⩾ 0, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected n-vertex graph of Euler genus at most k in time 𝒪_k(n^{2-1/25}). Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most k after deletion of at most k vertices, we show an algorithm for the same task that achieves the running time bound 𝒪_k(n^{2-1/356} log^{6k} n). Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of K_h-minor-free graphs, but the running time bound is 𝒪_h(n^{2-c_h}) for some constant c_h > 0 depending on h. That is, our savings in the exponent of the polynomial function of n, as compared to the naive quadratic algorithm, are independent of the parameter k. The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus.

The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these problems, permitting the application of this technique on surface-embedded graphs, is the fact that every graph of large enough treewidth contains a vertex that is irrelevant, in the sense that its removal yields an equivalent instance of the problem. The straightforward application of this technique yields algorithms with running time that is quadratic in the size of the input graph. This running time is due to the fact that it takes linear time to detect one irrelevant vertex and the total number of irrelevant vertices to be detected is linear as well. Using advanced techniques, sub-quadratic algorithms have been designed for particular problems, even in general graphs. However, designing a general framework for linear-time algorithms has been open, even for the bounded-genus case. In this paper we introduce a general framework that enables finding in linear time an entire set of irrelevant vertices whose removal yields a bounded-treewidth graph, provided that the input graph has bounded genus. Our technique consists in decomposing any surface-embedded graph into a tree-structured collection of bounded-treewidth subgraphs where detecting globally irrelevant vertices can be done locally and independently. Our method is applicable to a wide variety of known graph containment or graph modification problems where the irrelevant vertex technique applies. Examples include the (Induced) Minor Folio problem, the (Induced) Disjoint Paths problem, and the F-Minor-Deletion problem.

Given a graph G and a vertex set X, the annotated treewidth tw(G,X ) of X in G is the maximum treewidth of an X-rooted minor of G, i.e., a minor H where the model of each vertex of H contains some vertex of X. That way, tw(G, X ) can be seen as a measure of the contribution of X to the tree-decomposability of G. We introduce the logic CMSO/tw as the fragment of monadic second-order logic on graphs obtained by restricting set quantification to sets of bounded annotated treewidth. We prove the following Algorithmic Meta-Theorem (AMT): for every non-trivial minor-closed graph class, model checking for CMSO/tw formulas can be done in quadratic time. Our proof works for the more general CMSO/tw+dp logic, that is CMSO/tw enhanced by disjoint-path predicates. Our AMT can be seen as an extension of Courcelle’s theorem to minor-closed graph classes where the bounded-treewidth condition in the input graph is replaced by the bounded-treewidth quantification in the formulas. Our results yield, as special cases, all known AMTs whose combinatorial restriction is non-trivial minor-closedness.

Abstract. A framework consists of an undirected graph [Formula: see text] and a matroid [Formula: see text] whose elements correspond to the vertices of [Formula: see text]. Recently, Fomin et al. [ Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2023, pp. 2214–2227] and Eiben, Koana, and Wahlström [ Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2024, pp. 377–423] developed parameterized algorithms for computing paths of rank [Formula: see text] in frameworks. More precisely, for vertices [Formula: see text] and [Formula: see text] of [Formula: see text], and an integer [Formula: see text], they gave FPT algorithms parameterized by [Formula: see text] deciding whether there is an [Formula: see text]-path in [Formula: see text] whose vertex set contains a subset of elements of [Formula: see text] of rank [Formula: see text]. These algorithms are based on the Schwartz–Zippel lemma for polynomial identity testing and thus are randomized, and therefore the existence of a deterministic FPT algorithm for this problem remains open. We present the first deterministic FPT algorithm that solves the problem in frameworks whose underlying graph [Formula: see text] is planar. While the running time of our algorithm is worse than the running times of the recent randomized algorithms, our algorithm works on more general classes of matroids. In particular, this is the first FPT algorithm for the case when matroid [Formula: see text] is represented over rationals. We complement this result by proving that if the input matroids are given by their independence oracles, then there is no algorithm solving the problem with [Formula: see text] oracle queries. Furthermore, this computational lower bound holds even if the input graphs are planar graphs of treewidth at most two.

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence , defining some property of the modified part of the graph, and the target sentence , defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic ( CMSO ) and have models of bounded treewidth, while target sentences express first-order logic ( FO ) properties. Our logic captures problems that are not definable in FO and, moreover, may have instances of unbounded treewidth. Our main result is that, for this compound logic, model-checking can be done in quadratic time on minor-free graphs. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique . It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle’s theorem and Gaifman’s theorem. Our algorithmic meta-theorem encompasses, unifies, and extends the known meta-algorithmic results for CMSO and FO on minor-closed graph classes.

We give an algorithm that, given graphs$G$and$H$, tests whether$H$is a minor of$G$in time$\mathcal{O}_{H}(\overline{n}^{1+o(1)})$; here,$n$is the number of vertices of$G$and the$\mathrm{O}_{H}(.)$-notation hides factors that depend on$H$and are computable. By the Graph Minor Theorem, this implies the existence of an$n^{1+o(1)}$-time membership test for every minor-closed class of graphs. More generally, we give an$\mathcal{O}_{H,\vert X\vert} (m^{1+o(1)})$-time algorithm for the rooted version of the problem, in which$G$comes with a set of roots$X\subseteq V(G)$and some of the branch sets of the sought minor model of$H$are required to contain prescribed subsets of$X$; here,$m$is the total number of vertices and edges of$G$. This captures the Disjoint Pathsproblem, for which we obtain an$\mathcal{O}_{k}(m^{1+o(1)\backslash }$-time algorithm, where$k$is the number of terminal pairs. For all the mentioned problems, the fastest algorithms known before are due to Kawarabayashi, Kobayashi, and Reed [JCTB 2012], and have a time complexity that is quadratic in the number of vertices of$G$. Our algorithm has two main ingredients: First, we show that by using the dynamic treewidth data structure of Korhonen, Majewski, Nadara, Pilipczuk, and Sokolowski [FOCS 2023], the irrelevant vertex technique of Robertson and Seymour can be implemented in almost-linear time on apex-minor-free graphs. Then, we apply the recent advances in almost-linear time flow/cut algorithms to give an almost-linear time implementation of the recursive understanding technique, which effectively reduces the problem to apex-minor-free graphs.

It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, Siebertz, STOC 2014]. However, the dependency on the formula size is non-elementary, and in fact, this is unavoidable even for the class of all trees [Frick and Grohe, LICS 2002]. On the other hand, it is known that the dependency is elementary for classes of bounded degree [Frick and Grohe, LICS 2002] as well as for classes of bounded pathwidth [Lampis, ICALP 2023]. In this paper we generalise these results and almost completely characterise subgraph-closed graph classes for which the model checking problem is fixed-parameter tractable with an elementary dependency on the formula size. Those are the graph classes for which there exists a number d such that for every r, some tree of depth d and size bounded by an elementary function of r is avoided as an (≤r)-subdivision in all graphs in the class. In particular, this implies that if the class in question excludes a fixed tree as a topological minor, then first-order model checking for graphs in the class is fixed-parameter tractable with an elementary dependency on the formula size.

Disjoint-paths logic, denoted FO+ DP, extends first-order logic (FO) with atomic predicates dpk[(x1, y1), …, (xk, yk)], expressing the existence of internally vertex-disjoint paths between xi and yi, for 1 ≤ i ≤ k. We prove that for every graph class excluding some fixed graph as a topological minor, the model checking problem for FO+ DP is fixed-parameter tractable. This extends the model checking algorithm of Golovach et al. [SODA 2023] for FO+ DP for minor-closed graph classes. It also essentially settles the question of tractable model checking for this logic on subgraph-closed classes, since the problem is hard on subgraph-closed classes not excluding a topological minor (assuming a further mild condition on efficiency of encoding).

We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G , we seek for a cycle C in G of minimum cost 𝖮𝖯𝖳 = f(C) . We give an algorithm that given an n -vertex graph G , parameter ɛ > 0, and the function f represented by an oracle, in time n 𝒪 (log 1/ɛ) finds a cycle C in G with f(C) ≤ (1+ɛ). 𝖮𝖯𝖳. This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest ( s,t -Path problem, which requires exponentially many queries to the oracle for finding an n 2/3-ɛ -approximation Goel et al. [ 7 ], FOCS 2009. We complement our algorithm with a matching lower bound. We show that for every ɛ > 0, obtaining a (1+ɛ)-approximation requires at least n Ω (log 1/ ɛ) queries to the oracle. When the function f is integer-valued, our algorithm yields that a cycle of cost 𝖮𝖯𝖳 can be found in time n 𝒪(log 𝖮𝖯𝖳) . In particular, for 𝖮𝖯𝖳 = n 𝒪(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n 𝒪(log n ) queries are required even when 𝖮𝖯𝖳= 𝒪( n ). We also consider special cases of monotone submodular functions, corresponding to the number of different color classes needed to cover a cycle in an edge-colored multigraph G . For special cases of the corresponding minimization problem, we obtain fixed-parameter tractable algorithms and polynomial-time algorithms, when restricted to certain classes of inputs.

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored \(n\) -vertex undirected graph, vertices \(s\) and \(t\) , and an integer \(k\) , finds an \((s,t)\) -path containing at least \(k\) different colors in time \(2^{k}n^{\mathcal{O}(1)}\) . This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman on finding a path through \(k\) specified vertices. It also implies the first \(2^{k}n^{\mathcal{O}(1)}\) time algorithm for finding an \((s,t)\) -path of length at least \(k\) . Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\) -vertex undirected graph \(G\) , a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\) , a positive integer weight function on the vertices of \(G\) , two sets of vertices \(S,T\subseteq V(G)\) , and integers \(p,k,w\) , and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\) , while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^{2}\log(q+k))}n^{\mathcal{O}(1)}w\) time randomized algorithm for this problem.

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or $\mathcal{G}$-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle's theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle's theorem and Gaifman's theorem. We finally prove extensions where the target property is expressible in FOL+DP, i.e., the enhancement of FOL with disjoint-paths predicates.

Let G be a minor-closed graph class and let G be an n-vertex graph. We say that G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. Our first result is an algorithm that decides whether G is a k-apex of G in time 2^poly(k)⋅n². This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020, TALG 2022], whose running time was 2^poly(k)⋅n³. The elimination distance of G to G, denoted by ed_G(G), is the minimum number of rounds required to reduce each connected component of G to a graph in G by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] proved the existence of an FPT-algorithm, with parameter k, to decide whether ed_G(G) ≤ k. This algorithm is based on the computability of the minor-obstructions and its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether ed_G(G) ≤ k in time 2^{2^{2^poly(k)}}⋅n². This is the first algorithm for this problem with an explicit parametric dependence in k. In the special case where G excludes some apex-graph as a minor, we give two alternative algorithms, one running in time 2^{2^O(k²log k)}⋅n² and one running in time 2^{poly(k)}⋅n³. As a stepping stone for these algorithms, we provide an algorithm that decides whether ed_G(G) ≤ k in time 2^O(tw⋅ k + tw log tw)⋅n, where tw is the treewidth of G. This algorithm combines the dynamic programming framework of Reidl, Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where G contains only the empty graph (i.e., for treedepth) with the representative-based techniques introduced by Baste, Sau, and Thilikos [SODA 2020]. In all the algorithmic complexities above, poly is a polynomial function whose degree depends on G, while the hidden constants also depend on G. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs E_k(G) = {G ∣ ed_G(G) ≤ k}.

A framework consists of an undirected graph $G$ and a matroid $M$ whose elements correspond to the vertices of $G$. Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023] developed parameterized algorithms for computing paths of rank $k$ in frameworks. More precisely, for vertices $s$ and $t$ of $G$, and an integer $k$, they gave FPT algorithms parameterized by $k$ deciding whether there is an $(s,t)$-path in $G$ whose vertex set contains a subset of elements of $M$ of rank $k$. These algorithms are based on Schwartz-Zippel lemma for polynomial identity testing and thus are randomized, and therefore the existence of a deterministic FPT algorithm for this problem remains open. We present the first deterministic FPT algorithm that solves the problem in frameworks whose underlying graph $G$ is planar. While the running time of our algorithm is worse than the running times of the recent randomized algorithms, our algorithm works on more general classes of matroids. In particular, this is the first FPT algorithm for the case when matroid $M$ is represented over rationals. Our main technical contribution is the nontrivial adaptation of the classic irrelevant vertex technique to frameworks to reduce the given instance to one of bounded treewidth. This allows us to employ the toolbox of representative sets to design a dynamic programming procedure solving the problem efficiently on instances of bounded treewidth.

We introduce the following submodular generalization of the SHORTEST CYCLE problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G, we seek for a cycle C in G of minimum cost OPT = f(C). We give an algorithm that given an n-vertex graph G, parameter ε > 0, and the function f represented by an oracle, in time n

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored n-vertex undirected graph, vertices s and t, and an integer k, finds an (s,t)-path containing at least k different colors in time 2kn

The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (FOL) with the extra atomic predicate dpk(x1,y1,…, xk,yk), expressing the existence of internally vertex-disjoint paths between Xi and yi, for i ∈ {1,…, k}. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every proper minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the scattered disjoint paths logic, FOL+SDP, where we further consider the atomic predicate s-sdpk(x1,y1,…,xk,yk), demanding that the disjoint paths are within distance bigger than some fixed value s. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.01723

Abstract. A linkage in a graph [Formula: see text] of size [Formula: see text] is a subgraph [Formula: see text] of [Formula: see text] whose connected components are [Formula: see text] paths. The pattern of a linkage of size [Formula: see text] is the set of [Formula: see text] pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function [Formula: see text] such that if a plane graph [Formula: see text] contains a sequence [Formula: see text] of at least [Formula: see text] nested cycles and a linkage of size at most [Formula: see text] whose pattern vertices lay outside the outer cycle of [Formula: see text] then [Formula: see text] contains a linkage with the same pattern avoiding the inner cycle of [Formula: see text]. In this paper we prove the following variant of this result: Assume that all the cycles in [Formula: see text] are “orthogonally” traversed by a linkage [Formula: see text] and [Formula: see text] is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of [Formula: see text]. We prove that there are two functions [Formula: see text], such that if [Formula: see text] has size at most [Formula: see text], [Formula: see text] has size at least [Formula: see text] and [Formula: see text], then there is a linkage with the same pattern as [Formula: see text] that is “internally combed” by [Formula: see text], in the sense that [Formula: see text]. This result applies to any graph that is partially embedded on a disk (where [Formula: see text] is also embedded). In fact, we prove this result in the most general version where the linkage [Formula: see text] is [Formula: see text]-scattered: every two vertices of distinct paths are within a distance bigger than [Formula: see text]. We deduce several variants of this result in the cases where [Formula: see text] and [Formula: see text]. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs.

For a finite collection of graphs ℱ, the ℱ- TM-Deletion problem has as input an n -vertex graph G and an integer k and asks whether there exists a set S ⊆ V(G) with |S| ≤ k such that G \ S does not contain any of the graphs in ℱ as a topological minor. We prove that for every such ℱ, ℱ - TM-Deletion is fixed parameter tractable on planar graphs. Our algorithm runs in a 2 𝒪( k 2) ⋅ n 2 time, or, alternatively, in 2 𝒪( k ) ⋅ n 4 time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface.

Let 𝒢 be a minor-closed graph class. We say that a graph G is a k -apex of 𝒢 if G contains a set S of at most k vertices such that G\S belongs to 𝒢 . We denote by 𝒜 k ( 𝒢 ) the set of all graphs that are k -apices of 𝒢 . In the first paper of this series, we obtained upper bounds on the size of the graphs in the minor-obstruction set of 𝒜 k ( 𝒢 ), i.e., the minor-minimal set of graphs not belonging to 𝒜 k ( 𝒢 ). In this article, we provide an algorithm that, given a graph G on n vertices, runs in time 2 poly (k) ⋅ n 3 and either returns a set S certifying that G ∈ 𝒜 k ( 𝒢 ), or reports that G ∉ 𝒜 k ( 𝒢 ). Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of 𝒢 . In the special case where 𝒢 excludes some apex graph as a minor, we give an alternative algorithm running in 2 poly (k) ⋅ n 2 -time.

In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge addition and the question is, given a graph G and an integer k, whether it is possible to transform G to a graph in 𝒫 after applying k times the operation ⊠ on G. This problem has been extensively studied for particilar instantiations of ⊠ and 𝒫. In this paper we consider the general property 𝒫_ϕ of being planar and, moreover, being a model of some First-Order Logic sentence ϕ (an FOL-sentence). We call the corresponding meta-problem Graph ⊠-Modification to Planarity and ϕ and prove the following algorithmic meta-theorem: there exists a function f: ℕ² → ℕ such that, for every ⊠ and every FOL sentence ϕ, the Graph ⊠-Modification to Planarity and ϕ is solvable in f(k,|ϕ|)⋅n² time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifman’s Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.

Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2^{poly(k)}n³ time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2^{poly(k)}n² time.

For a finite collection of graphs , the -TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S ⊆ V(G) with |S| ≤ k such that G\S does not contain any of the graphs in as a topological minor. We prove that for every such , -TM-Deletion is fixed parameter tractable on planar graphs. In particular, we provide an f(h, k) · n2 algorithm where h is an upper bound to the vertices of the graphs in .