Algorithmics and Computational Complexity Research GroupSummer Term 2021

# Research Colloquium (Summer Term 2021)

The research colloquium "Algorithmik und Komplexitätstheorie" provides talks of external guests, members of the research staff, Ph.D. students, and advanced students (theses) about recent results and research topics in theoretical computer science and related areas. The core areas are algorithmics and computational complexity theory. If you would like to receive information about upcoming talks, please join our mailing list. If you would like to give a talk yourself, feel free to send an email to m.renken@tu-berlin.de.

Due to the Coronavirus situation, this semester’s talks are given online, usually at meet.akt.tu-berlin.de/b/mal-jkm-myf.

Click on rows to expand. The schedule will be updated during the term.
Date Speaker Title
20.04.2021
16:00
Matthias Bentert
(TU Berlin)
Using a geometric lens to find k disjoint shortest paths.

Given an undirected n-vertex graph and k pairs of terminal vertices $(s_1,t_1),…,(s_k,t_k)$, the k-Disjoint Shortest Paths (k-DSP)-problem asks whether there are k pairwise vertex-disjoint paths $P_1,…,P_k$ such that $P_i$ is a shortest $s_i$-$t_i$-path for each $i∈[k]$. Recently, Lochet [arXiv 2019] provided an algorithm that solves k-DSP in $n^{O(k^{4^k})}$ time, answering a 20-year old question about the computational complexity of k-DSP for constant k. On the one hand, we present an improved $O(k*n^{{12k⋅k!+k+1}})$-time algorithm based on a novel geometric view on this problem. For the special case $k=2$, we show that the running time can be further reduced to $O(n^2*m)$ by small modifications of the algorithm and a further refined analysis. On the other hand, we show that k-DSP is W[1]-hard with respect to k, showing that the dependency of the degree of the polynomial running time on the parameter k is presumably unavoidable.

27.04.2021
16:00
Christoph Hertrich
(TU Berlin)
tba

tba

04.05.2021
16:00
Leon Kellerhals
(TU Berlin)
Placing Green Bridges Optimally, with a Multivariate Analysis.

tba

11.05.2021
16:00
Niclas Boehmer
(TU Berlin)
tba

tba