# WorKer 2011 – The Third Workshop on Kernelization

Vienna University of Technology, 2-4 September 2011, Vienna, Austria.
This page has been mirrored here from its original location at http://www.kr.tuwien.ac.at/drm/worker2011.

## 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.

## Organizers

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

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

The organizers acknowledge the funding from the following organizations:

• Vienna Center for Logic and Algorithms (VCLA)
• Wolfgang Pauli Institute (WPI)
• European Research Council (ERC)

## Registration

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

### 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

## Talks

### Keynote Talks

• Armin Biere: Preprocessing and Inprocessing Techniques in SAT slides [Abstract]
• Sourav Chakraborty: Property Testing: Sublinear Algorithms for Promise Problems slides [Abstract]
• Michael R. Fellows: Kernelization and the Larger Picture of Practical Algorithmics, in Contemporary Context slides [Abstract]
• Fedor V. Fomin: Protrusions in graphs and their applications slides [Abstract]
• Bart Jansen: Kernelization for a Hierarchy of Structural Parameters slides [Abstract]
• Daniel Lokshtanov: Generalization and Specialization of Kernelization slides [Abstract]
• Pierre Marquis: A Few Words about Knowledge Compilation slides [Abstract]
• Anders Yeo: Simultaneously Satisfying Linear Equations Over F_2: Parameterized Above Average slides [Abstract]

### Contributed Talks

• Robert Crowston: Max-r-Lin Above Average and its Applications slides
• Henning Fernau: A linear kernel for the differential of a graph slides
• Sepp Hartung: Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs slides
• Pim van ‘t Hof: Parameterized Complexity of Vertex Deletion into Perfect Graph Classes slides
• Falk Hüffner: Graph Transformation and Kernelization: Confluent Data Reduction for Edge Clique Cover slides
• Stefan Kratsch: Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem slides
• Erik Jan van Leeuwen: Kernels for domination when the stars are out slides
• Dániel Marx: Kernelization of Packing Problems
• Hadas Shachnai: From Approximative Kernelization to High Fidelity Reductions slides
• Karolina Soltys: Hierarchies of kernelization hardness slides
• Magnus Wahlström: Polynomial kernels for some graph cut problems slides
• Gregory Gutin: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problem slides

## Schedule

### 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