Minor Containment and Disjoint Paths in almost-linear time

We give an algorithm that, given graphs G and H, tests whether H is a minor of G in time OH(n¹⁺ᵒ⁽¹⁾); here, n is the number of vertices of G and the OH(·)-notation hides factors that depend on H and are computable. By the Graph Minor Theorem, this implies the existence of an n¹⁺ᵒ⁽¹⁾-time membership test for every minor-closed class of graphs. More generally, we give an OH,|X|(m¹⁺ᵒ⁽¹⁾)-time algorithm for the rooted version of the problem, in which G comes with a set of roots X⊆ 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 Paths problem, for which we obtain an Oₖ(m¹⁺ᵒ⁽¹⁾)-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 Soko{}owski [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.