In the edge-disjoint paths problems, we are given a (directed or undirected)
graph *G* and ask for paths in *G* connecting given sets of terminal
pairs such that the number of paths containing an edge *e* does
not exceed its capacity. In general, problems of this type are NP-hard but there
are several interesting ways to relax them:

- One may consider only a specified class of graphs, e.g. planar or Eulerian graphs.
- We can allow fractional solutions, so we rather ask for multicommodity flows than for disjoint paths.
- We may want to choose only a subset of the terminals to be connected, so we want to maximize the number (or the weight) of the terminals that can be connected instead of just deciding if all of them can be connected.
- One may allow a congestion on the edges of
*G*, so one may violate the capacity constraints e.g. by a constant factor.

Number | Approval talk | Talk | Name | Topic | Mentoring |
---|---|---|---|---|---|

1 | 2.4 | 23.4. | Simon Ahrens | Cuts, trees and l_{1}-embeddings of graphs
| Markus Struzyna |

2 | 16.4 | 30.4. | Lars Thorge Jensen | Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums | Markus Struzyna |

3 | 23.4 | 7.5. | Jannik Silvanus | Coarse differentiation and multi-flows in planar graphs | Jan Schneider |

4 | 30.4 | 14.5. | Clemens Rösner | Embedding k-outerplanar graphs into l_{1}
| Jan Schneider |

5 | 7.5 | 21.5. | Christiane Engels | Flow-cut gaps for integer and fractional multiflows | Jan Schneider |

6 | 14.5 | 4.6. | Corinna Gottschalk | Primal-dual approximation algorithms for integral flow and multicut in trees | Michael Gester |

7 | 21.5 | 11.6. | Rudolf Scheifele | Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems | Michael Gester |

8 | 4.6 | 18.6. | Thomas Weyd | Routing in undirected graphs with constant congestion | Michael Gester |

9 | 11.6 | 25.6. | Maxime Wegesin | Maximum edge-disjoint paths in planar graphs with congestion 2 | Ulrike Suhl |

10 | 18.6 | 2.7. | Sonja Wittke | Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs | Ulrike Suhl |

List of papers used for this seminar

- A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.

Prof. Dr. B. Korte,

Prof. Dr. J. Vygen,

Prof. Dr. S. Hougardy,

Jun.Prof. Dr. T. Nieberg,

Jun.Prof. Dr. S. Held,

Dr. U. Brenner