{"id":"arxiv/2605.14902","url":"https://arxiv.org/abs/2605.14902","tags":["math.CO","cs.DM","cs.DS"],"score":0,"title":"Optimal Bounds for the k-Disjoint Paths Problem","domain":"math.CO","source":"arxiv","authors":["Dario Cavallaro","Maximilian Gorsky","Stephan Kreutzer","Dimitrios M. Thilikos","Sebastian Wiederrecht"],"reviews":0,"subject":"math.CO","summary":"The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Paths, Rooted Minor Checking, and Folio. A key ingredient behind the fixed-parameter tractability of the $k$-Disjoint Paths problem is the irrelevant-vertex technique. This machinery is governed by the Vital Linkage Theorem and the so-called Linkage Function $\\ell$. However, despite its foundational role, the best known bounds on the Linkage Function are enormous and are only implicitly understood. The quantitative…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-14","reactions":{}}