Optimal Bounds for the k-Disjoint Paths Problem

Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer, Dimitrios M. Thilikos, Sebastian Wiederrecht

arXivarxiv/2605.14902May 14, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.14902
curl -X POST /api/v1/records/arxiv/2605.14902/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.14902/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'