Cover Image

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard

Fuente: arXiv

Saved in:

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

Similar Items

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

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

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

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

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

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)

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

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

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

Approximation Algorithms for Digraph Width Parameters
by: Kintali, Shiva, et al.
Published: (2011)

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

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
by: Bhaskar, Umang, et al.
Published: (2025)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

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

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

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

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

Parameterized Maximum Node-Disjoint Paths
by: Lampis, Michael, et al.
Published: (2024)

Uncrossed Multiflows and Applications to Disjoint Paths
by: Chekuri, Chandra, et al.
Published: (2025)

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

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
by: Bucić, Matija, et al.
Published: (2025)

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

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

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

Finding a Shortest $M$-link Path in a Monge Directed Acyclic Graph
by: Wan, Joy Z.
Published: (2024)

Stochastic Embedding of Digraphs into DAGs
by: Filtser, Arnold
Published: (2025)

Disjoint Tours and the Price of Diversity
by: de Berg, Mark, et al.
Published: (2025)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

Node-Weighted Multicut in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2026)

Constant-Factor Approximation for the Uniform Decision Tree
by: Szyfelbein, Michał
Published: (2026)

Online Disjoint Set Covers: Randomization is not Necessary
by: Bienkowski, Marcin, et al.
Published: (2024)

Online Disjoint Spanning Trees and Polymatroid Bases
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
by: Zhou, Jianqi, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Polylogarithmic Approximation for Robust s-t Path
by: Li, Shi, et al.
Published: (2023)

Fully Dynamic Strongly Connected Components in Planar Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Connected k-Median with Disjoint and Non-disjoint Clusters
by: Eube, Jan, et al.
Published: (2025)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
by: Ferdous, S M, et al.
Published: (2023)

Packed Acyclic Deterministic Finite Automata
by: Shibata, Hiroki, et al.
Published: (2024)