A postdoc at MPII.

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

The disjoint paths problem is an extensively studied problem in graph theory and theoretical computer science and it also has important practical applications, e.g. it appears in VLSI design and various routing problems. In designing network algorithms one need to route paths through a small number of hubs, which introduces the length bounded variant of the disjoint paths problem. The disjoint paths problem also finds application in scheduling and timetabling.

The input is a graph G=(V,E) and a set of pairs of vertices {(s_1,t_1),...,(s_k,t_k)} the question is to find k paths P_1,...,P_k such that the path P_i connects s_i to t_i for i=1 to k and every pair of paths P_i,P_j are internally vertex disjoint. This also called k-disjoint paths problem. The problem is hard in general graphs, however it admits an FPT algorithm in undirected graphs. In directed graphs, the problem is much harder: it is NP-complete already for 2-disjoint paths problem.

In this talk, we provide an overview of this problem and we try to cover the state of the art. We then consider a relaxed version of this problem and explain some ideas around it, namely we focus on the disjoint paths with congestion: every vertex can route upto c paths where c is the congestion.

Saeed Amiri

--email hidden

passcode not visible

logged in users only

Disjoint paths, directed graphs, algorithms, graph minor theorem

We explain everything which is needed to understand the topic, however, a bit understanding about structural properties such as tree width might help.

If a reader is interested in the problem here are some suggestions for further reading (the graph minor XIII is very hard to read):

https://link.springer.com/chapter/10.1007/978-3-642-19094-0_2
https://www.sciencedirect.com/science/article/pii/S0095895685710064
http://drops.dagstuhl.de/opus/volltexte/2016/6424/pdf/LIPIcs-MFCS-2016-7.pdf