Worker 2009

Worker 2009

The 1st Workshop on Kernels

Bergen, 12/09/2009 - 13/09/2009


The meeting will take place at  VilVite center,  in Bergen, starting on September 12 (Saturday) at 11.00 with lunch, with the first talk at 12.00. The workshop ends on September 13 (Sunday) around 16.30. The format of the workshop will be several invited lectures on the recent trends in kernelization, short reports on new results, and slots for discussions and open problems.

Note that this workshop does not produce any proceedings and presentations here should not cause any problem for submitting the same material to a regular conference or journal.

Invited speakers

Confirmed invited speakers

  • Holger Dell
  • Gregory Gutin



There is no participation fee, and the workshop includes free coffee breaks and lunches for registered participants. For accommodation you have to contact a hotel yourself. To register for the workshop send a letter containing the following information before August 14 to Saket Saurabh Saket.Saurabh*at*



and indicate wether you are interested in giving a talk. For PhD students: also please organize a brief letter of reference from advisor



The following moderate price hotels are nearby the workshop site


Local INFO

  • From airoport to Bergen centre. Take bus "Flybussen" to the city center (Central bus station). The bus costs 85 NOK single, 150 NOK return. Taxi will be between 300 and 400 NOK. More on transport in Bergen here
  • From Bergen centre. The workshop will be at VilVite center (10 minutes walk from the central bus station) If you have been visited us before, this is 50 meters from the Institute of Informatics. Here is how to get there and here is Google map. 


Registered participants

  • Faisal N. Abu-Khazam
  • Isolde Adler
  • Paul Bonsma
  • Vladmir Estivill Castro
  • Marek Cygan
  • Jean Daligault
  • Holge Dell
  • Frederic Dorn
  • Henning Fernau
  • Johannes Fichte
  • Fedor Fomin
  • Petr Golovach
  • Gregory Gutin
  • Eun Jung Kim
  • Christian Knauer
  • Joachim Knies
  • Stefan Kratsch
  • Daniel Lokshtanov
  • Federico Mancini
  • Rodica Mihai
  • Matthias Mnich
  • Moritz Müller
  • Jesper Nederlof
  • Christophe Paul
  • Anthony Perez
  • G. Phillip
  • Marcin Pilipczuk
  • M Praveen
  • Daniel Raible
  • Saket Saurabh
  • Narges Simjour
  • Ondra Suchy
  • Stefan Szeider
  • Jan Arne Telle
  • Martin Vatshelle
  • Yngve Villanger
  • Magnus Wahlström


Saturday, September 12th

11:00 Lunch
Upper Bounds I
12:00 Gregory Gutin Kernels for Problems Parameterized Above Tight Lower Bounds
13:00 Henning Fernau Kernels for Packing and Covering Problems
13:30 Coffee Break
14:00 Saket Saurabh Min-Max Theorems and Kernelization
15:00 Geevarghese Phillip Dominating Set in Degenerate Graphs
15:30 Coffee Break
Lower Bounds I
16:00 Holger Dell Introduction to Kernel Lower Bounds
17:00 Daniel Lokshtanov Connected Vertex Cover Has no Polynomial Kernel
19:00 Workshop Dinner at Bocca

Sunday, September 13th

Lower Bounds II
9:30 Holger Dell Sparsification Lower Bounds
10:30 Moritz Müller
Lower Bounds for Variants of Kernelization
11:00 Coffee Break
11:30 Magnus Wahlström Kernelizability of Min Ones CSPs I : Lower Bounds
12:00 Jan Arne Telle What Is A Kernel? (Discussion)
13:00 Lunch
Upper Bounds II
14:00 Daniel Lokshtanov Meta-theorems for Kernelization
15:00 Stefan Kratsch Kernelizability of Min Ones CSPs II : Upper Bounds
15:30 Coffee Break
15:45 Fedor Fomin Open Problems