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.

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

Travel Information to Vienna / your Hotel

Please consult our visitors’ guide.

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

Please consult our visitors’ guide.

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 [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 [Abstract]
  Abstract. Deciding weather a graph is -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 -colorable of “far from being -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 [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 [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 [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 [Abstract]
  Abstract. tba
• Pierre Marquis: A Few Words about Knowledge Compilation slides [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 [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

Saturday, September 3

Sunday, September 4

 Photos