TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 12241

Data Reduction and Problem Kernels

( Jun 10 – Jun 15, 2012 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/12241

Organizers

Contact


Summary

Preprocessing (data reduction or kernelization) is used universally in almost every practical computer implementation that aims to deal with an NP-hard problem. The history of preprocessing, such as applying reduction rules to simplify truth functions, can be traced back to the origins of Computer Science the 1950's work of Quine, and much more. A modern example showing the striking power of efficient preprocessing is the commercial integer linear program solver CPLEX. The goal of a preprocessing subroutine is to solve efficiently the “easy parts'' of a problem instance and reduce it (shrinking it) to its computationally difficult “core'' structure (the problem kernel of the instance).

How can we measure the efficiency of such a kernelization subroutine? For a long time, the mathematical analysis of polynomial time preprocessing algorithms was neglected. The basic reason for this anomalous development of theoretical computer science, was that if we seek to start with an instance I of an NP-hard problem and try to find an efficient (P-time) subroutine to replace I with an equivalent instance I' with |I'|<|I| then success would imply P=NP --- discouraging efforts in this research direction, from a mathematically-powered point of view. The situation in regards the systematic, mathematically sophisticated investigation of preprocessing subroutines has changed drastically with advent of parameterized complexity, where the issues are naturally framed. More specifically, we ask for upper bounds on the reduced instance sizes as a function of a parameter of the input, assuming a polynomial time reduction/preprocessing algorithm.

A typical example is the famous Nemhauser-Trotter kernel for the Vertex Cover problem, showing that a “kernel" of at most 2k vertices can be obtained, with k the requested maximum size of a solution. A large number of results have been obtained in the past years, and the research in this area shows a rapid growth, not only in terms of number of papers appearing in top Theoretical Computer Science and Algorithms conferences and journals, but also in terms of techniques. Importantly, very recent developments were the introduction of new lower bound techniques, showing (under complexity theoretic assumptions) that certain problems must have kernels of at least certain sizes, meta-results that show that large classes of problems all have small (e.g., linear) kernels --- these include a large collection of problems on planar graphs and matroid based techniques to obtain randomized kernels.

Kernelization is a vibrant and rapidly developing area. The meeting on kernelization aims at consolidating the results achieved in the recent years, discuss future research directions, and explore further the applications potential of kernelization algorithms, and give excellent opportunities for the participants to engage in joint research and discussions on open problems and future directions.

The main highlights of the workshop were talks on the solution to two main open problems in the area of kernelization.

The seminar consisted of twenty two talks, a session on open questions, and informal discussions among the participants. The organizers selected the talks in order to have comprehensive lectures giving overview of main topics and communications of new research results. Each day consisted of talks and free time for informal gatherings among participants. On the fourth day of the seminar we celebrated the 60th birthday of Mike Fellows, one of the founder of parameterized complexity. On this day we had several talks on the origin, history and the current developments in the field of parameterized complexity.


Participants
  • Faisal N. Abu-Khzam (Lebanese American University, LB) [dblp]
  • Cristina Bazgan (University Paris-Dauphine, FR) [dblp]
  • Hans L. Bodlaender (Utrecht University, NL) [dblp]
  • Bruno Courcelle (University of Bordeaux, FR) [dblp]
  • Marek Cygan (University of Warsaw, PL) [dblp]
  • Rodney Downey (Victoria University - Wellington, NZ) [dblp]
  • Andrew Drucker (MIT - Cambridge, US) [dblp]
  • Michael R. Fellows (Charles Darwin University - Darwin, AU) [dblp]
  • Henning Fernau (Universität Trier, DE) [dblp]
  • Rudolf Fleischer (German University of Technology - Oman, OM) [dblp]
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Robert Ganian (Goethe-Universität Frankfurt am Main, DE) [dblp]
  • Serge Gaspers (UNSW - Sydney, AU) [dblp]
  • Archontia C. Giannopoulou (University of Athens, GR) [dblp]
  • Jiong Guo (Universität des Saarlandes, DE) [dblp]
  • Gregory Z. Gutin (Royal Holloway University of London, GB) [dblp]
  • MohammadTaghi Hajiaghayi (University of Maryland - College Park, US) [dblp]
  • Pinar Heggernes (University of Bergen, NO) [dblp]
  • Danny Hermelin (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Petr Hlinený (Masaryk University - Brno, CZ) [dblp]
  • Juraj Hromkovic (ETH Zürich, CH) [dblp]
  • Falk Hüffner (TU Berlin, DE) [dblp]
  • Bart Jansen (Utrecht University, NL) [dblp]
  • Mark Jones (Royal Holloway University of London, GB) [dblp]
  • Iyad A. Kanj (DePaul University - Chicago, US) [dblp]
  • Eun Jung Kim (University Paris-Dauphine, FR) [dblp]
  • Christian Komusiewicz (TU Berlin, DE) [dblp]
  • Stefan Kratsch (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Michael A. Langston (University of Tennessee, US)
  • Daniel Lokshtanov (University of California - San Diego, US) [dblp]
  • Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
  • Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Daniel Meister (Universität Trier, DE) [dblp]
  • Neeldhara Misra (Indian Institute of Science, IN) [dblp]
  • Matthias Mnich (Universität des Saarlandes, DE) [dblp]
  • Anil Nerode (Cornell University, US) [dblp]
  • Rolf Niedermeier (TU Berlin, DE) [dblp]
  • Christophe Paul (University of Montpellier 2, FR) [dblp]
  • Geevarghese Philip (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Marcin Pilipczuk (University of Warsaw, PL) [dblp]
  • Michal Pilipczuk (University of Bergen, NO) [dblp]
  • Venkatesh Raman (The Institute of Mathematical Sciences, IN) [dblp]
  • Fahimeh Ramezani (MPI für Informatik - Saarbrücken, DE)
  • Felix Reidl (RWTH Aachen, DE) [dblp]
  • Frances A. Rosamond (Charles Darwin University - Darwin, AU) [dblp]
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Noy Rotbart (University of Copenhagen, DK)
  • Ignasi Sau Valls (University of Montpellier 2, FR) [dblp]
  • Saket Saurabh (University of Bergen, NO) [dblp]
  • Ildikó Schlotter (Budapest University of Technology & Economics, HU) [dblp]
  • Hadas Shachnai (Technion - Haifa, IL) [dblp]
  • Somnath Sikdar (RWTH Aachen, DE) [dblp]
  • Karolina Soltys (MPI für Informatik - Saarbrücken, DE)
  • Ulrike Stege (University of Victoria, CA) [dblp]
  • Ondrej Suchý (Universität des Saarlandes, DE) [dblp]
  • Stefan Szeider (TU Wien, AT) [dblp]
  • Jan Arne Telle (University of Bergen, NO) [dblp]
  • Dimitrios M. Thilikos (University of Athens, GR) [dblp]
  • Yngve Villanger (University of Bergen, NO) [dblp]
  • Magnus Wahlström (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
  • Anders Yeo (Royal Holloway University of London, GB) [dblp]

Related Seminars
  • Dagstuhl Seminar 14451: Optimality and tight results in parameterized complexity (2014-11-02 - 2014-11-07) (Details)

Classification
  • data structures / algorithms / complexity

Keywords
  • preprocessing
  • fixed-parameter tractability
  • parameterized algorithmics