http://www.dagstuhl.de/14451

02. – 07. November 2014, Dagstuhl Seminar 14451

Optimality and tight results in parameterized complexity

Organisatoren

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)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 4, Issue 11 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl Seminars [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

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.