[Facets-of-complexity] Monday Lectures Facets of Complexity: May 28, 2018, change of schedule

[Günter Rote <rote@inf.fu-berlin.de>]

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