Dagstuhl Seminar 14451
Optimality and tight results in parameterized complexity
( Nov 02 – Nov 07, 2014 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/14451
Organizers
- Stefan Kratsch (TU Berlin, DE)
- Daniel Lokshtanov (University of Bergen, NO)
- Dániel Marx (Hungarian Academy of Sciences - Budapest, HU)
- Peter Rossmanith (RWTH Aachen, DE)
Contact
- Dagmar Glaser (for administrative matters)
Schedule
While many seemingly hard computational problems can be solved satisfactorily in practice, classical complexity dictates that they are in fact intractable (NP-hard) in general. This is an unsatisfactory situation since one would desire a more productive interplay between more heuristic practical results and theoretically proven theorems.
Parameterized complexity analyzes the complexity in finer detail by considering additional problem parameters beyond the input size and expresses the efficiency of the algorithms in terms of these parameters. In this framework, many NP-hard problems have been shown to be (fixed-parameter) tractable when certain structural parameters of the inputs are bounded. In the past two decades, there has been tremendous progress in understanding which problems are fixed-parameter tractable and which problems are not (under standard complexity assumptions).
In recent years, the field of parameterized complexity seems to have evolved beyond merely classifying problems as fixed-parameter tractable or not. The focus shifted to understanding how close the algorithmic results are to the ``best possible'' algorithm for the problem. Thanks to significant recent advances on both algorithms (upper bounds) and complexity (lower bounds), we have now a tight understanding of many problems and many algorithmic results can be now proven optimal under reasonable assumptions. Moreover, it turns out that the search for optimality can be formulated with respect to different aspects of parameterized complexity and each such aspect gives a separate challenging but doable research direction. One can consider the optimality of algorithms for parameterized problems (either fixed-parameter tractable or not), the optimality of preprocessing algorithms, and the optimality of algorithms with respect to the generality of the problem being solved. The goal of the seminar is to bring together experts in the area of parameterized complexity and algorithms, highlight these research directions and the relevant recent results, and discuss future research topics.
While many seemingly hard computational problems can be solved satisfactorily in practice, classical complexity dictates that they are in fact intractable (NP-hard) in general. This is an unsatisfactory situation since one would desire a more productive interplay between more heuristic practical results and theoretically proven theorems.
Parameterized complexity analyzes the complexity in finer detail by considering additional problem parameters beyond the input size and expresses the efficiency of the algorithms in terms of these parameters. In this framework, many NP-hard problems have been shown to be (fixed-parameter) tractable when certain structural parameters of the inputs are bounded. In the past two decades, there has been tremendous progress in understanding which problems are fixed-parameter tractable and which problems are not (under standard complexity assumptions).
In recent years, the field of parameterized complexity seems to have evolved beyond merely classifying problems as fixed-parameter tractable or not. The focus shifted to understanding how close the algorithmic results are to the "best possible" algorithm for the problem. Thanks to significant recent advances on both algorithms (upper bounds) and complexity (lower bounds), we have now a tight understanding of many problems and many algorithmic results can be now proven optimal under reasonable assumptions. Moreover, it turns out that the search for optimality can be formulated with respect to different aspects of parameterized complexity and each such aspect gives a separate challenging but doable research direction. One can consider the optimality of algorithms for parameterized problems (either fixed-parameter tractable or not), the optimality of preprocessing algorithms, and the optimality of algorithms with respect to the generality of the problem being solved. The goal of the seminar was to bring together experts in the area of parameterized complexity and algorithms, highlight these research directions and the relevant recent results, and discuss future research topics.
The scientific program of the seminar consisted of 25 talks. Among these there were five 60 minute tutorials on the core topics of the seminar: Marek Cygan and Michal Pilipczuk ("Exponential Time Hypothesis, Part 1+2") covered the Exponential Time Hypothesis (ETH), focussing on techniques for proving tight runtime lower bounds under ETH. Daniel Lokshtanov ("The Strong Exponential Time Hypothesis") introduced Strong ETH as well as related lower bound techniques, and Virginia Vassilevska Williams ("Implications of SETH for polynomial time problems") gave an overview of tight lower bounds for efficiently solvable problems under Strong ETH. Finally, Dániel Marx ("Every Graph is easy or hard") covered the topic of dichotomy theorems for graph problems. Throughout, the tutorials were well-received both as a means of introduction to the topics but also as a convenient way of catching up on very recent results pertaining to the seminar. Furthermore, with most tutorials being held on Monday and Tuesday morning this set a productive atmosphere for tackling open problems regarding tight parameterized complexity results. A further 60 minute contributed talk by Saket Saurabh discussed the recent breakthrough result of fixed-parameter tractability of Graph Isomorphism with respect to treewidth. The rest of the talks were 25-minute presentations on recent research of the participants.
The time between lunch and afternoon coffee was left for self-organized collaborations and discussions. An open problem session was organized on Monday evening. Notes on the presented problems can be found in this report.
Creative Commons BY 3.0 Unported license
Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, and Peter Rossmanith
- Andreas Björklund (Lund University, SE) [dblp]
- Hans L. Bodlaender (Utrecht University, NL & Technical University Eindhoven, NL) [dblp]
- Rajesh Hemant Chitnis (University of Maryland - College Park, US) [dblp]
- Radu Curticapean (Universität des Saarlandes, DE) [dblp]
- Marek Cygan (University of Warsaw, PL) [dblp]
- Holger Dell (Universität des Saarlandes, DE) [dblp]
- Markus Dregi (University of Bergen, NO) [dblp]
- Andrew Drucker (University of Edinburgh, GB) [dblp]
- Henning Fernau (Universität Trier, DE) [dblp]
- Fedor V. Fomin (University of Bergen, NO) [dblp]
- Serge Gaspers (UNSW - Sydney, AU) [dblp]
- Gregory Z. Gutin (Royal Holloway University of London, GB) [dblp]
- MohammadTaghi Hajiaghayi (University of Maryland - College Park, US) [dblp]
- Thore Husfeldt (IT University of Copenhagen, DK) [dblp]
- Bart Jansen (University of Bergen, NO) [dblp]
- Mark Jones (Royal Holloway University of London, GB) [dblp]
- Iyad A. Kanj (DePaul Uniersity - Chicago, US) [dblp]
- Eun Jung Kim (University Paris-Dauphine, FR) [dblp]
- Christian Knauer (Universität Bayreuth, DE) [dblp]
- Christian Komusiewicz (TU Berlin, DE) [dblp]
- Lukasz Kowalik (University of Warsaw, PL) [dblp]
- Stefan Kratsch (TU Berlin, DE) [dblp]
- Daniel Lokshtanov (University of Bergen, NO) [dblp]
- Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
- Matthias Mnich (Universität Bonn, DE) [dblp]
- Jesper Nederlof (TU Eindhoven, NL) [dblp]
- Christophe Paul (CNRS - Montpellier, FR) [dblp]
- Geevarghese Philip (MPI für Informatik - Saarbrücken, DE) [dblp]
- Marcin Pilipczuk (University of Warwick - Coventry, GB) [dblp]
- Michal Pilipczuk (University of Warsaw, PL) [dblp]
- Peter Rossmanith (RWTH Aachen, DE) [dblp]
- Saket Saurabh (The Institute of Mathematical Sciences, IN) [dblp]
- Somnath Sikdar (RWTH Aachen, DE) [dblp]
- Ramanujan Sridharan (University of Bergen, NO) [dblp]
- Ondrej Suchý (Czech Technical University - Prague, CZ) [dblp]
- Stefan Szeider (TU Wien, AT) [dblp]
- Jan Arne Telle (University of Bergen, NO) [dblp]
- Dimitrios M. Thilikos (AlGCo project team, CNRS, FR & LIRMM, FR) [dblp]
- Erik Jan van Leeuwen (MPI für Informatik - Saarbrücken, DE) [dblp]
- Virginia Vassilevska Williams (Stanford University, US) [dblp]
- Magnus Wahlström (Royal Holloway University of London, GB) [dblp]
- Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
- Anders Yeo (Singapore University of Technology and Design, SG) [dblp]
Related Seminars
- Dagstuhl Seminar 12241: Data Reduction and Problem Kernels (2012-06-10 - 2012-06-15) (Details)
Classification
- data structures / algorithms / complexity
Keywords
- parameterized complexity
- fixed-parameter tractability
- NP-hardness
- tight lower bounds
