# Minor Containment and Disjoint Paths in almost-linear time

Preprint · Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis

- Archive id: arxiv:2404.03958
- Published: 2024-04-05
- arXiv: https://arxiv.org/abs/2404.03958
- Source URL: https://arxiv.org/abs/2404.03958
- PDF: https://arxiv.org/pdf/2404.03958
- Provenance: arxiv

## Abstract

We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time ${\\cal O}\_H(n^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the ${\\cal O}\_H(\\cdot)$-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 ${\\cal O}\_{H,\|X\|}(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 Paths problem, for which we obtain an ${\\cal O}\_{k}(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 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.