{"id":"arxiv:2404.03958","kind":"preprint","title":"Minor Containment and Disjoint Paths in almost-linear time","authors":["Tuukka Korhonen","Michał Pilipczuk","Giannos Stamoulis"],"author_count":3,"year":2024,"published":"2024-04-05","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2404.03958","nct_id":null,"source_url":"https://arxiv.org/abs/2404.03958","archive_url":"https://space-kitty.com/papers/arxiv:2404.03958","updated":"2024-04-05","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2404.03958","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS","math.CO"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}