http://www.dagstuhl.de/14451

November 2 – 7 , 2014, Dagstuhl Seminar 14451

Optimality and tight results in parameterized complexity

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)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 4, Issue 11 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

Summary

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.

License
  Creative Commons BY 3.0 Unported license
  Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, and Peter Rossmanith

Related Dagstuhl Seminar

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Parameterized complexity
  • Fixed-parameter tractability
  • NP-hardness
  • Tight lower bounds

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support