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^1+o (1) ) ; 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^1+o (1) -time membership test for every minor-closed class of graphs. More generally, we give an O₇, |ₗ| (m^1+o (1) ) -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^1+o (1) ) -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 Sokoowski 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.