[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - November 26th 2018

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our Monday Lecture & Colloquium on November 26th at 14:15 h & 16:00 h at HU Berlin.

Location:

Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]
Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin

Time: Monday, November 26th - 14:15 h

Lecture: Marcin Pilipczuk (University of Warsaw)

Title: The square root phenomenon: subexponential algorithms in sparse graph classes

Abstract:

While most NP-hard graph problems remain NP-hard when restricted to planar graphs, they become somewhat simpler: they often admit algorithms with running time exponential in the square root of the size of the graph (or some other meaningful parameter). This behavior has been dubbed "the square root phenomenon". For many problems, such an algorithm follows from the theory of bidimensionality relying on a linear dependency on the size of the largest grid minor and treewidth of a planar graph. In recent years we have seen a number of other algorithmic techniques, significantly extending the boundary of the applicability of the "square root phenomenon". In my talk I will survey this area and highlight main algorithmic approaches.

Coffee & Tea Break :

Before Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]

Time: Monday, November 26th - 16:00 h

Colloquium: Sebastian Siebertz (Humboldt-Universität zu Berlin)

Title: First-order interpretations of sparse graph classes

Abstract:

The notions of bounded expansion and nowhere denseness capture uniform sparseness of graph classes and render various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce structurally bounded expansion and structurally nowhere dense graph classes, dfined as first-order interpretations of bounded expansion and nowhere dense graph classes. As a first step towards their algorithmic treatment, we provide a characterization of structurally bounded expansion classes via low shrubdepth decompositions, a dense analogue of low treedepth decompositions. We prove that structurally nowhere dense graph classes are vc-minimal.