Aims & Scope

Research on theory and applications of kernelization is a vibrant and rapidly developing area in algorithm design and complexity. After successful workshops in Bergen 2009 and Leiden 2010, this third workshop aims at consolidating the results achieved in recent years and discussing future research directions.

A special aspect this year is to take a closer look at related work from different research areas, in particular from Practical Preprocessing, Property Testing, and Knowledge Compilation. Therefore we have invited leading researchers from these three areas to provide keynote talks.

The workshop will feature invited keynote talks as well as several invited and contributed talks with surveys and new technical results. The workshop will also provide opportunities for all participants to engage in joint research and discussions on open problems and future directions.

We expect the workshop program to start in the morning of Friday, 2 September 2011, and to end after lunch on Sunday, 4 September 2011.

WorKer 2011 group

Worker 2011 Group Photo.

Keynote Speakers


The workshop is organized by Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider (chair).

The organizers acknowledge the support from the advisory board consisting of Sourav Chakraborty, Fedor V. Fomin, and Daniel Lokshtanov.


The organizers acknowledge the funding from the following organizations:


The registration is now closed.

For people invited by the organizers it was possible to register until 18 July 2011. Registration is free of charge and includes attendance to all workshop events and lectures, coffee breaks, and lunches.

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

The invited talks will be open to the public. Local people who are interested in some of the talks but do not want to participate in the entire workshop (and the social program) do not need to register.

Travel and Local Information

Traveling to Vienna by plane

Vienna's Airport (VIE) is located 15 km (south)east of the city and is served by all major airlines. If you travel from Saarbrücken, you may consider Air Berlin which offers a connection via Berlin; the trip takes about 3.5 hours.

From the Airport to the City Center

The simplest, but most expensive variant for getting to the city center (resp. your hotel) is taking a taxi. This will probably cost around EUR 30 or more. Some companies like C&K offer taxis, limos or shuttles for a flat rate starting from EUR 32.

CAT is a new train service linking the airport to "Wien Mitte", where you can change to the metro (U3/U4), as well as to tram and buses (see below for information on the public transport in Vienna). The unique feature of CAT is that you can check in at "Wien Mitte" for certain flights when departing from Vienna. The cost is EUR 9 for a single and EUR 16 for a return trip. Note that tickets for underground, trams, or local buses are not included in this price.

Vienna Airport Lines offer buses to "Schwedenplatz" (connection to U1 and U4), "Westbahnhof" (westbound train station, connection to U3), and "Wien Meidling" (southbound train station). One ticket is EUR 6 (single) or EUR 11 (return). Tickets for underground, trams, or local buses are not included in this price.

The cheapest variant from the airport to the city center is going by Schnellbahn S7 (train) to "Wien Mitte" - it costs EUR 3.60 one-way (including underground and bus in Vienna). Be sure to buy "2 zones" from the vending machine. If you buy a separate ticket for Vienna, you need only "1 zone" (EUR 1.80). Have a look at the timetable.

Public Transport in Vienna

Public transport is very efficient in Vienna, and has a searchable timetable (you can search for a connection between stops, addresses, and even landmarks). There are several kinds of tickets: A ticket for a single trip costs EUR 1.80 and can be used for any single trip within Vienna. You may change lines, but you may not interrupt your journey. The most convenient option for you may be the "72h-Ticket" (EUR 13.60, valid for all means of public transport in Vienna for 72 hours from the time punched).
More information: timetable, tickets, Metro and train map (PDF), and Public transportation map (PDF).

The Workshop Venue

Lectures will take place at a department building of Vienna University of Technology. The street address is: Gußhausstrasse 25-29. The lecture room is called "EI 9 Hlawka Hörsaal" and is located on the ground floor. After entering the building through the glass doors turn right.

The venue can be reached by a 5 minutes walk from Karlsplatz, a hub of Vienna's public transport system. For instance the underground lines U1, U2, and U4 have a stop at Karlsplatz.

View Workshop Venue in a larger map

Tourist Information

An extensive account of travel information for Vienna can be found on the official webpage of the a Vienna Tourist Board. The webpage of the city of Vienna offers all sorts of informations on Vienna (including tourist information).

Some of the main sights in Vienna include: Stephansdom, St. Stephen's Cathedral, Schloss Schönbrunn, the National Library, the Austrian Parliament, the Wiener Prater with the famous Giant Ferris Wheel, Museumsquartier, several museums are located here or nearby, for instance, the Kunsthistorisches Museum Vienna. Sights near the workshop venue: Belvedere, Karlskirche, Secession, Musikverein, Opera, Albertina, Naschmarkt.



Keynote Talks

Contributed Talks


Friday, September 2

08.50 - 09.00 Opening
09.00 - 10.00 Keynote talk. Fedor V. Fomin: Protrusions in graphs and their applications slides
10.00 - 10.30 Sepp Hartung: Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs slides
10.30 - 11.00 Coffee break
11.00 - 12.00 Keynote talk. Pierre Marquis: A Few Words about Knowledge Compilation slides
12.00 - 12.30 Falk Hüffner: Graph Transformation and Kernelization: Confluent Data Reduction for Edge Clique Cover slides
12.30 - 14.00 Lunch: Mensa
14.00 - 15.00 Keynote talk. Anders Yeo: Simultaneously Satisfying Linear Equations Over F_2: Parameterized Above Average slides
15.00 - 15.30 Robert Crowston: Max-r-Lin Above Average and its Applications slides
15.30 - 16.00 Erik Jan van Leeuwen: Kernels for domination when the stars are out slides
16.00 - 16.30 Coffee break
16.30 - 17.30 Keynote talk. Armin Biere: Preprocessing and Inprocessing Techniques in SAT slides
17.30 - 18.00 Henning Fernau: A linear kernel for the differential of a graph slides

Saturday, September 3

09.00 - 10.00 Open problem session.
10.00 - 10.30 Karolina Soltys: Hierarchies of kernelization hardness slides
10.30 - 11.00 Coffee break
11.00 - 12.00 Keynote talk. Sourav Chakraborty: Property Testing: Sublinear Algorithms for Promise Problems slides
12.00 - 12.30 Hadas Shachnai: From Approximative Kernelization to High Fidelity Reductions slides
12.30 - 13.30 Lunch: Buffet
13.30 - 14.00 Group photo
14.00 - 15.00 Keynote talk. Daniel Lokshtanov: Generalization and Specialization of Kernelization slides
15.00 - 15.30 Stefan Kratsch: Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem slides
15.30 - 16.00 Coffee break
16.00 - 16.30 Gregory Gutin: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems slides
16.30 - 17.30 Keynote talk. Bart Jansen: Kernelization for a Hierarchy of Structural Parameters slides
18.00 Group 1 leaves via public transport to Kahlenberg (view) and then to Heurigen
18.30 Group 2 leaves via private bus directly to Heurigen
19.00 - 23.00 Workshop dinner: at Heurigen Sirbu
22.00 Group 2 leaves via bus to Karlsplatz

Sunday, September 4

09.30 - 10.30 Keynote talk. Michael R. Fellows: Kernelization and the Larger Picture of Practical Algorithmics, in Contemporary Context slides
10.30 - 11.00 Coffee break
11.00 - 11.30 Pim van 't Hof: Parameterized Complexity of Vertex Deletion into Perfect Graph Classes slides
11.30 - 12.00 Magnus Wahlström: Polynomial kernels for some graph cut problems slides
12.00 - 12.30 Dániel Marx: Kernelization of Packing Problems
13.00 - 14.00 Lunch: Restaurant Ischia
14.00 Closing


Stefan Szeider (opening) Fedor Fomin (keynote) Sepp Hartung Pierre Marquis (keynote) Falk Hüffner Anders Yeo (keynote) Robert Crowston Erik Jan van Leeuwen (coffee break) (coffee break) (coffee break) (coffee break) Armin Biere (keynote) Henning Fernau Mike Fellows (open problems) Karolina Soltys Sourav Chakraborty Hadas Shachnai Daniel Lokshtanov (keynote) Stefan Kratsch Gregory Gutin Bart Jansen (excursion Kahlenberg) (heurigen dinner, Kahlenberg) Mike Fellows (keynote) Pim van't Hof Magnus Wahlström Dániel Marx