http://www.dagstuhl.de/17041

January 22 – 27 , 2017, Dagstuhl Seminar 17041

Randomization in Parameterized Complexity

Organizers

Marek Cygan (University of Warsaw, PL)
Fedor V. Fomin (University of Bergen, NO)
Danny Hermelin (Ben Gurion University – Beer Sheva, IL)
Magnus Wahlström (Royal Holloway University of London, GB)


1 / 5 >

For support, please contact

Simone Schilke for administrative matters

Marc Herbstritt for scientific matters

Dagstuhl Reports

As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.

Documents

List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule [pdf]

(Use seminar number and access code to log in)

Motivation

Randomization plays a prominent role in many subfields of theoretical computer science. Typically, this role is twofold: On the one hand, randomized methods can be used to solve essentially classical problems easier or more efficiently. In many cases, this allows for simpler, faster, and more appealing solutions for problems that have rather elaborate deterministic algorithms; in other cases, randomization provides the only known way to cope with the problem (e.g. polynomial identity testing, or deciding whether there exists a perfect matching with exactly b red edges in an edge-colored bipartite graph). On the other hand, there are also cases where randomness is intrinsic to the question being asked, such as the study of properties of random objects, and the search for algorithms which are efficient on average for various input distributions.

Parameterized complexity is an approach of handling computational intractability, where the main idea is to analyze the complexity of problems in finer detail by considering additional problem parameters beyond the input size. This area has enjoyed much success in recent years, and has yielded several new algorithmic approaches that help us tackle computationally challenging problems. While randomization already has an important role in parameterized complexity, for instance in techniques such as color-coding or randomized contractions, there is a common opinion within researchers of the field that the full potential of randomization has yet to be fully tapped.

In this seminar we hope to help bridge this gap, by bringing together experts in the areas of randomized algorithms and parameterized complexity. In doing so, we hope to:

  • Establish domains for simpler and/or more efficient FPT algorithms via randomization.
  • Identify problems which intrinsically need randomization.
  • Study parameterized problems whose instances are generated by some underlying distribution.
  • Stimulate the development of a broadened role of randomness within parameterized complexity.

License
  Creative Commons BY 3.0 DE
  Marek Cygan and Fedor V. Fomin and Danny Hermelin and Magnus Wahlström

Classification

  • Data Structures / Algorithms / Complexity
  • Networks

Keywords

  • Parameterized complexity
  • Fixed-parameter tractability
  • Randomness
  • Intractability

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.