Cover Image

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pilipczuk, Michał, Stamoulis, Giannos, Włodarczyk, Michał
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Minor Containment and Disjoint Paths in almost-linear time
by: Korhonen, Tuukka, et al.
Published: (2024)

Faster diameter computation in graphs of bounded Euler genus
by: Kluk, Kacper, et al.
Published: (2025)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
by: Włodarczyk, Michał
Published: (2024)

Dynamic Detours
by: Dadush, Daniel, et al.
Published: (2026)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

Designing Compact ILPs via Fast Witness Verification
by: Włodarczyk, Michał
Published: (2025)

Going Beyond Surfaces in Diameter Approximation
by: Włodarczyk, Michał
Published: (2025)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
by: Wlodarczyk, Michal
Published: (2023)

Losing Treewidth In The Presence Of Weights
by: Włodarczyk, Michał
Published: (2024)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
by: Choudhary, Keerti, et al.
Published: (2025)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Does Subset Sum Admit Short Proofs?
by: Włodarczyk, Michał
Published: (2024)

Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors
by: Sharma, Roohani, et al.
Published: (2026)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

On Integer Programs That Look Like Paths
by: Briański, Marcin, et al.
Published: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

Parameterized and approximation algorithms for coverings points with segments in the plane
by: Kowalska, Katarzyna, et al.
Published: (2024)

Fixed-Parameter Tractable Submodular Maximization over a Matroid
by: Nematollahi, Shamisa, et al.
Published: (2025)

Massively Parallel Algorithms for Approximate Shortest Paths
by: Dory, Michal, et al.
Published: (2024)

Parameterized dynamic data structure for Split Completion
by: Majewski, Konrad, et al.
Published: (2024)

Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
by: Mizutani, Yosuke, et al.
Published: (2024)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

On Fixed-Parameter Tractability of Weighted 0-1 Timed Matching Problem on Temporal Graphs
by: Kumar, Rinku, et al.
Published: (2025)

Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons
by: Sharma, Vidya Sagar
Published: (2023)

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity
by: Tayal, Mumuksh
Published: (2025)

Revisiting Directed Disjoint Paths on tournaments (and relatives)
by: Gomes, Guilherme C. M., et al.
Published: (2025)

On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2026)

Shortest Paths in Multimode Graphs
by: Kirkpatrick, Yael, et al.
Published: (2025)

On Constrained and k Shortest Paths
by: Bendahi, Abderrahim, et al.
Published: (2024)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

On the Two Paths Theorem and the Two Disjoint Paths Problem
by: Humeau, Samuel, et al.
Published: (2025)

Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
by: Pintér, József, et al.
Published: (2026)