S. Akhoondian Amiri

In the k-Disjoint Paths Problem, a set of terminal pairs of vertices $\{(s_i,t_i)| 1\le i\le k\}$ is given and we are asked to find disjoint paths $P_1,\ldots,P_k$ such that each path $P_i$ connects $s_i$ to $t_i$. There are two main variations of this problem: shortest disjoint paths and disjoint paths with congestion; in the former, the aim is to make each $P_i$ the shortest path and, in the latter, every vertex can tolerate a certain amount c of congestion.

We introduce a more natural problem by mixing the two: k-disjoint shortest paths with congestion-c. This problem is more realistic in the sense that in practical networks we can tolerate certain congestion, moreover, routing along short paths is in priority.

For this problem, we provide a simple algorithm to solve it in time $f(k) n^{O(k-c)}$ on DAGs.
Our algorithm is based on the earlier algorithm of Amiri et al.[IPL 2019], but we significantly simplify their proof argument. We also discuss the hardness of the problem, achieving a better lower bound than the existing one in the previous work.

We believe our simplified method of analysis can be helpful to deal with similar problems on general undirected graphs.

Keywords: Graph Algorithms, Disjoint Paths, Shortest Paths, Scheduling, Routing with Congestion, Acyclic Graphs


FA1 Graphs and Networks 1
June 11, 2021  9:15 AM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.