You are cordially invited to this week's Monday Lecture. When? Monday, May 28, 2018, 14:15 h Where? Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin room MA 041, ground floor The talk by Alan Arroyo at 16:00 is *cancelled* and the talk by Dušan Knop is *rescheduled* from 17:00 to 16:00. ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Lecture - 14:15 Marek Cygan, University of Warsaw Approximation algorithms for the k-Set packing problem In the k-Set Packing problem we are given a universe and a family of its subsets, where each of the subsets has size at most k. The goal is to select a maximum number of sets from the family which are pairwise disjoint. It is a well known NP-hard problem, that has been studied from the approximation perspective since the 80's. During the talk I will describe the history of progress on both the weighted and unweighted variants of the problem, with an exposition of methods used to obtain the best known approximation algorithms, mostly involving local-search-based routines. Tea and coffee break ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Colloquium - 16:00 (moved from 17:00) Dušan Knop, University of Bergen Parameterized Complexity of Steiner Problems In the Steiner Tree problem, a set of terminal vertices in an edge-weighted graph needs to be connected in the cheapest possible way. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on the one hand, Steiner Tree is known to be APX-hard, and on the other hand, it is W[2]-hard if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H of G of the minimum cost such that there is a directed path from s to t in H for all arcs st of R. It is known that the problem can be solved in time |V(G)|^O(|A(R)|) [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time |V(G)|^o(|A(R)|) even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time |V(G)|^o(|T|), unless ETH fails. Therefore, there is a significant gap in the complexity with respect to |T| in the exponent. We show that Directed Steiner Network is solvable in time f(|T|) · |V(G)|^O(c_g·|T|), where c_g is a constant depending solely on the genus g of G and f is a computable function. ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Colloquium - 16:00 (cancelled) Alan Arroyo, University of Waterloo Pseudolinear drawings of graphs - CANCELLED ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Graduiertenkolleg "Facets of Complexity" - www.facetsofcomplexity.de/monday