Lecture by Marcin Pilipczuk (University of Warsaw): The square root phenomenon: subexponential algorithms in sparse graph classes

Nov 26, 2018 | 02:15 PM

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.

Time & Location

Nov 26, 2018 | 02:15 PM

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

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)