# Planar Disjoint Shortest Paths is Fixed-Parameter Tractable

Article · Michał Pilipczuk, Giannos Stamoulis, Michał Włodarczyk

- Archive id: arxiv:2505.03353
- Published: 2025-05-06
- Venue: Society for Industrial and Applied Mathematics eBooks
- DOI: https://doi.org/10.1137/1.9781611978971.165
- arXiv: https://arxiv.org/abs/2505.03353
- Citations: 1
- Source URL: https://arxiv.org/abs/2505.03353
- PDF: https://arxiv.org/pdf/2505.03353
- Provenance: arxiv

## Abstract

In the Disjoint Shortest Paths problem one is given a graph $G$ and a set $\\mathcal{T}=\\{(s\_1,t\_1),\\dots,(s\_k,t\_k)\\}$ of $k$ vertex pairs. The question is whether there exist vertex-disjoint paths $P\_1,\\dots,P\_k$ in $G$ so that each $P\_i$ is a shortest path between $s\_i$ and $t\_i$. While the problem is known to be W\[1\]-hard in general, we show that it is fixed-parameter tractable on planar graphs with positive edge weights. Specifically, we propose an algorithm for Planar Disjoint Shortest Paths with running time $2^{O(k\\log k)}\\cdot n^{O(1)}$. Notably, our parameter dependency is better than state-of-the-art $2^{O(k^2)}$ for the Planar Disjoint Paths problem, where the sought paths are not required to be shortest paths.

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

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
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.