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 Photo.
Keynote Speakers
 Armin Biere, Johannes Kepler
University, Linz, Austria
 Sourav Chakraborty, Chennai
Mathematical Institute, India
 Michael R. Fellows, Charles Darwin University, Australia
 Fedor V. Fomin, University of Bergen, Norway
 Bart Jansen, Utrecht
University, the Netherlands
 Daniel Lokshtanov, University of California, San Diego, USA
 Pierre Marquis,
Université d'Artois & CRILCNRS, France
 Anders Yeo, Royal Holloway, University of London, UK
Organizers
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.
Sponsors
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
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 oneway (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
"72hTicket" (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 2529.
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.
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.
Participants
 Faisal AbuKhzam, Lebanese American University, Lebanon
 Rémy Belmonte, University of Bergen, Norway
 Armin Biere, Johannes Kepler University, Linz, Austria
 Sourav Chakraborty, Chennai Mathematical Institute, India
 Robert Crowston, Royal Holloway, University of London, UK
 Wolfgang Dvorak, Vienna University of Technology, Austria
 Uwe Egly, Vienna University of Technology, Austria
 Michael R. Fellows, Charles Darwin University, Australia
 Henning Fernau, Universität Trier, Germany
 Fedor Fomin, University of Bergen, Norway
 Serge Gaspers, Vienna University of Technology, Austria
 Archontia Giannopoulou, National and Kapodistrian University of Athens, Greece
 Jiong Guo, University of Saarland, Germany
 Gregory Gutin, Royal Holloway, University of London, UK
 Sepp Hartung, TU Berlin, Germany
 Pinar Heggernes, University of Bergen, Norway
 Marijn Heule, Delft University of Technology, The Netherlands
 Pim van 't Hof, University of Bergen, Norway
 Falk Hüffner, TU Berlin, Germany
 Bart Jansen, Utrecht University, the Netherlands
 Matti Järvisalo, University of Helsinki, Finland
 Mark Jones, Royal Holloway, University of London, United Kingdom
 Eunjung Kim, CNRS, France
 Stefan Kratsch, Utrecht University, The Netherlands
 Martin Lackner, Vienna University of Technology, Austria
 Daniel Lokshtanov, University of California, San Diego, USA
 Dániel Marx, HumboldtUniversität zu Berlin, Germany
 Ramanujan Maadapuzhi Sridharan, The Institute of Mathematical Sciences, India
 Pierre Marquis, Université d'Artois & CRILCNRS, France
 Jesper Nederlof, University of Bergen, Norway
 Rolf Niedermeier, TU Berlin, Germany
 Sebastian Ordyniak, Vienna University of Technology, Austria
 Christophe Paul, CNRS  LIRMM (Montpellier), France
 Andreas Pfandler, Vienna University of Technology, Austria
 Reinhard Pichler, Vienna University of Technology, Austria
 Marcin Pilipczuk, University of Warsaw, Poland
 Michał Pilipczuk, University of Warsaw, Poland
 Arash Rafiey, IDSIA, Switzerland
 Venkatesh Raman, Institute of Mathematical Sciences, Chennai, India
 Frances A. Rosamond, Charles Darwin University, Australia
 Stefan Rümmele, Vienna University of Technology, Austria
 Saket Saurabh, The Institute of Mathematical Sciences, India
 Martina Seidl, Johannes Kepler Universität Linz, Austria
 Hadas Shachnai, Technion, Israel
 Narges Simjour, University of Waterloo, Canada
 Friedrich Slivovsky, Vienna University of Technology, Austria
 Karolina Soltys, Max Planck Institute, Germany
 Ondra Suchy, Saarland University, Saarbrucken, Germany
 Stefan Szeider, Vienna University of Technology, Austria
 Jan Arne Telle, University of Bergen, Norway
 Dimitrios Thilikos, National and Kapodistrian University of Athens, Greece
 Erik Jan van Leeuwen, University of Bergen, Norway
 Angelina Vidali, University of Vienna, Austria
 Yngve Villanger, University of Bergen, Norway
 Magnus Wahlström, Max Planck Institute for Informatics, Germany
 Mathias Weller, TU Berlin, Germany
 Stefan Woltran, Vienna University of Technology, Austria
 Anders Yeo, Royal Holloway, University of London, UK
Talks
Keynote Talks
 Armin Biere: Preprocessing and Inprocessing Techniques in SAT slides
[Show/Hide Abstract]
Abstract.
SAT solvers are used in many applications in and outside of Computer
Science. The success of SAT is based on the use of good decision
heuristics, learning, restarts, and compact data structures with fast
algorithms. But also efficient and effective encoding, preprocessing and
inprocessing techniques are important in practice. In this talk we give an
overview of old and more recent inprocessing and preprocessing techniques
starting with ancient pure literal reasoning and failed literal probing.
Hyperbinary resolution and variable elimination are more recent techniques
of this century. We discuss blockedclause elimination, which gives a nice
connection to optimizing encodings and conclude with our recent results on
unhiding redundancy fast.
 Sourav Chakraborty: Property Testing: Sublinear Algorithms for
Promise Problems slides
[Show/Hide Abstract]
Abstract.
Deciding weather a graph is $k$colorable is an NPcomplete problem and hence
solving this problem is expected to be hard. But if we are given a promise that
the graph is either $k$colorable of "far from being $k$coloarble", can
we make some intelligent deductions "quickly"? Property testing deals with these kind
of questions, where the goal is to solve some promise problems. The efficiency
of an algorihtm is measured by the number of input bits that are read. In many
cases there are algorithms that can correctly answer with high probability by
looking at a tiny fraction (sometimes even constant) of the input bits. In the
past two decades this area has been at the forefront of research in theoretical
computer science  we will take at look at it.
 Michael R. Fellows: Kernelization and the Larger Picture of
Practical Algorithmics, in Contemporary Context slides
[Show/Hide Abstract]
Abstract.
The natural relationship between Parameterized Complexity and heuristics has
been a subject of papers and talks since the beginnings of parameterized
complexity, and has been especially recognized within the WorKer kernelization
community. In the Journal of Computer and System Sciences (January 2011)
celebrating Richard Karp's 2008 Koyoto Prize, and elsewhere, Karp proposes a
general program, closely related to the standard FPT technique of iterative
compression, as a structured approach to heuristic algorithm design, for
problems in computational molecular biology and genetics. This talk will
discuss Karp's general program in light of the parameterized complexity
framework, and survey the contemporary context of programmatic thinking about
the deployment of mathematics to serve practical computing, in which
preprocessing (kernelization) has, of course, both a central and a leveraged
role.
References.
Fellows, M. R. Parameterized complexity: Main ideas, connections to heuristics
and research frontiers. In Proceedings of ISAAC (2001), vol. 2223 of Lecture
Notes in Computer Science, SpringerVerlag, pp. 291307.
Fellows, M. R. Parameterized complexity: New developments and research
frontiers. In Aspects of Complexity (2001), De Gruyter, pp. 5172.
Fellows, M. R. Parameterized complexity: The main ideas and connections to
practical computing. In Experimental Algorithmics (2002), R. Fleischer,
B. M. E. Moret, and E. M. Schmidt, Eds., vol. 2547 of Lecture Notes in Computer
Science, SpringerVerlag, pp. 5177.
Fellows, M. R. A survey of FPT algorithm design techniques with an emphasis on
recent advances and connections to practical computing. In Proceedings of 12th
Annual European Symposium ESA, Bergen, Norway (2004), S. Albers and T. Radzik,
Eds., vol. 3221 of Lecture Notes in Computer Science, SpringerVerlag, pp. 12.
 Fedor V. Fomin: Protrusions in graphs and their applications
slides
[Show/Hide Abstract]
Abstract.
A protrusion in a graph is a subgraph of constant treewidth
that can be separated from the graph by removing a constant number of
vertices. We discuss combinatorial properties of graphs implying
existence of large protrusions and give a number of algorithmic
applications of protrusions.
 Bart Jansen: Kernelization for a Hierarchy of Structural
Parameters slides
[Show/Hide Abstract]
Abstract.
There are various reasons to study the kernelization complexity of nonstandard
parameterizations. Problems such as Chromatic Number are NPcomplete for a
constant value of the natural parameter, hence we should not hope to obtain
kernels for this parameter. For other problems such as Long Path, the natural
parameterization is fixedparameter tractable but is known not to admit a
polynomial kernel unless the polynomial hierarchy collapses. We may therefore
guide the search for meaningful preprocessing rules for these problems by
studying the existence of polynomial kernels for different parameterizations.
Another motivation is formed by the Vertex Cover problem. Its natural
parameterization admits a small kernel, but there exist refined parameters
(such as the feedback vertex number) which are structually smaller than the
natural parameter, for which polynomial kernels still exist; hence we may
obtain better preprocessing studying the properties of such refined parameters.
In this survey talk we discuss recent results on the kernelization complexity
of structural parameterizations of these important graph problems. We consider
a hierarchy of structural graph parameters, and try to pinpoint the best
parameters for which polynomial kernels still exist.
 Daniel Lokshtanov: Generalization and Specialization of
Kernelization slides
[Show/Hide Abstract]
Abstract.
tba
 Pierre Marquis: A Few Words about Knowledge Compilation slides
[Show/Hide Abstract]
Abstract.
My talk will be about knowledge compilation, a research topic studied in AI for
more than twenty years, and which is concerned with preprocessing some pieces
of information in order to improve some tasks of interest, computationally
speaking. In this talk, after an introduction to knowledge compilation, I will
focus on two important points: the definition of compilable problems (roughly,
those for which computational improvements via preprocessing can be
"guaranteed") and the design of a knowledge compilation map (a multicriteria
evaluation of representation languages which can be used as target languages
for knowledge compilation).
 Anders Yeo: Simultaneously Satisfying Linear Equations Over F_2:
Parameterized Above Average slides
[Show/Hide Abstract]
Abstract.
In this talk we will mainly be considering the parameterized problem
MaxLin2AA. In MaxLin2AA, we are given a system of variables x_1,... ,x_n and
equations of the form x_{i_1}*x_{i_2}*... *x_{i_r} = b, where
{x_{i_1},x_{i_2},...,x_{i_r}} is a subset of {1,2,...,n} and all x_i and b
belong to {1, 1}. Furthermore each equation has a positive integral weight,
and we want to decide whether it is possible to simultaneously satisfy
equations of total weight at least W/2+k, where W is the total weight of all
equations and k is the parameter (if k=0, the possibility is assured).
In this talk we begin by (briefly) explaining what it means to parameterize a
problem above average and why this seems a natural parameterization. We will
motivate why MaxLin2AA is of interest and outline how to obtain a kernel with
at most O(k^2 log k) variables, which solves an open problem of Mahajan et
al. (2006). Finally we will mention a number of open problems and conjectures.
Coauthors: Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones,
Frances Rosamond, Stephan Thomasse
Contributed Talks
 Robert Crowston:
MaxrLin Above Average and its Applications slides
 Henning Fernau:
A linear kernel for the differential of a graph slides
 Sepp Hartung:
LinearTime 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:
Conondeterminism in compositions: A kernelization lower bound for a
Ramseytype 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 belowupperbound 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: LinearTime
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: MaxrLin 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: Conondeterminism in
compositions: A kernelization lower bound for a Ramseytype
problem slides 
15.30  16.00 
Coffee break 
16.00  16.30 
Gregory Gutin: Kernels for
belowupperbound 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 
Photos