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 & CRIL-CNRS, 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 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.
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 Abu-Khzam, 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, Humboldt-Universität zu Berlin, Germany
- Ramanujan Maadapuzhi Sridharan, The Institute of Mathematical Sciences, India
- Pierre Marquis, Université d'Artois & CRIL-CNRS, 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.
Hyper-binary resolution and variable elimination are more recent techniques
of this century. We discuss blocked-clause 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 NP-complete 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
pre-processing (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, Springer-Verlag, pp. 291-307.
Fellows, M. R. Parameterized complexity: New developments and research
frontiers. In Aspects of Complexity (2001), De Gruyter, pp. 51-72.
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, Springer-Verlag, pp. 51-77.
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, Springer-Verlag, pp. 1-2.
- 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 non-standard
parameterizations. Problems such as Chromatic Number are NP-complete 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 fixed-parameter 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 pre-processing 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 pre-processing can be
"guaranteed") and the design of a knowledge compilation map (a multi-criteria
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
MaxLin2-AA. In MaxLin2-AA, 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 MaxLin2-AA 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:
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 |
Photos