Routing with Congestion in Acyclic Digraphs

2016/05/06 by Amiri, Saeed Akhoondian, Kreutzer, Stephan, Marx, Dániel +1 · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1605.01866

Abstract

We study the version of the k-disjoint paths problem where k demand pairs (s₁,t₁), …, (s_k,t_k) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n^O(d) if we allow congestion k-d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f(k)n^{o(d/log d)} for any computable function f.

Cited by

• The Directed Disjoint Paths Problem with Congestion
• Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors

Related

• Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
• Disjoint Shortest Paths with Congestion on DAGs
• The Directed Disjoint Paths Problem with Congestion
• Routing in Undirected Graphs with Constant Congestion
• The hardness of routing two pairs on one face