Minor Containment and Disjoint Paths in Almost-Linear Time
Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis · 2024
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.