Tight approximation and kernelization bounds for vertex-disjoint shortest paths

DOI10.1007/S00224-025-10252-9MaRDI QIDQ7233451zbMATH OpenFDO

Authors Matthias Bentert, Fedor V. Fomin, Petr A. Golovach

Publication date 27 April 2026

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-025-10252-9

zbMATH Keywords

ethfixed-parameter tractabilityparameterized (in)approximability

Mathematics Subject Classification ID

Graph theory (05Cxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A birthday repetition theorem and complexity of approximating dense CSPs
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• A simplified NP-complete satisfiability problem
• Almost polynomial factor inapproximability for parameterized k-clique
• Almost polynomial hardness of node-disjoint paths in grids
• Approximating disjoint-path problems using packing integer programs
• Color-coding
• Detecting disjoint shortest paths in linear time and more
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 7788350 (Why is no real title available?)
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Lossy kernelization
• Lower bounds for approximate (\& exact) k-disjoint-shortest-paths
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• New hardness results for routing on disjoint paths
• On the complexity of k-SAT
• On the Computational Complexity of Combinatorial Problems
• Optimal binary space partitions for segments in the plane
• Parameterized algorithms
• Planar Formulae and Their Uses
• The Directed Disjoint Shortest Paths Problem
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem
• The Problem of Compatible Representatives
• Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
• Which problems have strongly exponential complexity?

This page was built for publication: Tight approximation and kernelization bounds for vertex-disjoint shortest paths

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