Parameterized maximum node-disjoint paths

DOI10.4230/LIPICS.IPEC.2025.3MaRDI QIDQ7356317zbMATH OpenFDO

Authors Michael Lampis, Manolis Vasilakis

Publication date 23 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2025.3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A faster parameterized algorithm for treedepth
• Almost polynomial hardness of node-disjoint paths in grids
• An exact characterization of tractable demand patterns for maximum disjoint path problems
• An exponential time parameterized algorithm for planar disjoint paths
• Approximating disjoint-path problems using packing integer programs
• Color-coding
• Computing treedepth in polynomial space and linear FPT time
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Faster parameterized algorithm for cluster vertex deletion
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Improved approximation for node-disjoint paths in planar graphs
• Irrelevant vertices for the planar disjoint paths problem
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Minor containment and disjoint paths in almost-linear time
• New algorithms for maximum disjoint paths based on tree-likeness
• New hardness results for routing on disjoint paths
• On approximating node-disjoint paths in grids
• On routing disjoint paths in bounded treewidth graphs
• On the Computational Complexity of Combinatorial Problems
• On the computational complexity of vertex integrity and component order connectivity
• Parameterized algorithm for the disjoint path problem on planar graphs: exponential in k^2 and linear in n
• Parameterized algorithms
• Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• Planar disjoint paths, treewidth, and kernels
• Slightly superexponential parameterized problems
• Structural parameterizations for two bounded degree problems revisited
• The disjoint paths problem in quadratic time

This page was built for publication: Parameterized maximum node-disjoint paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7356317)