Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Innerhalb dieser Seite:
Externe Seiten:
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp

Dagstuhl-Seminar 24411

New Tools in Parameterized Complexity: Paths, Cuts, and Decomposition

( 06. Oct – 11. Oct, 2024 )

Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:




This Dagstuhl Seminar will concentrate on developing new tools arising from the parameterized complexity of cuts, paths, and graph decompositions. The last 2 years have been very exciting for the area, with several breakthroughs.

In FOCS 2021, Korhonen introduced a new method for approximating tree decompositions in graphs. His method, deeply rooted in the classical graph theory, is a handy tool for decomposing graphs. Several recent STOC/FOCS papers are developing this method in various settings. In parallel, a novel perspective on graph decompositions was proposed by Bonnet et al. in FOCS 2020. The new twin-width theory has many exciting consequences, and we are still beginning to understand the real impact of the new decompositions on graph algorithms.

In the series of papers (SODA 2021, STOC 2022, SODA 2023), Kim et al. developed a beautiful algorithmic method for handling separators in (undirected, weighted, or directed) graphs by addition of arcs. The new algorithmic tool was used to resolve several long-standing open problems in the area. It also paves the road to many more new discoveries.

Reis and Rothvoss (Arxiv 2023) announced a (log n)O(n) time randomized algorithm to solve integer programs in n variables. This breakthrough will have an impact on many problems in parameterized complexity, especially on the problems of cuts in graphs. Finally, using algebraic methods (new and old), there has been significant progress on several problems around paths, including the classical k-disjoint path problems.

This seminar aims to bring together people from the parameterized complexity community, specialists from the world of cuts, flows, and connectivity, and those who have been at the forefront of these new developments. Thus, this seminar aims to bring together experts from these fields, consolidate the results achieved in recent years, discuss future research directions, and explore further the potential applications of the methods and techniques discussed above.

Copyright Fedor V. Fomin, Dániel Marx, Saket Saurabh, and Roohani Sharma

Verwandte Seminare
  • Dagstuhl-Seminar 17041: Randomization in Parameterized Complexity (2017-01-22 - 2017-01-27) (Details)
  • Dagstuhl-Seminar 19041: New Horizons in Parameterized Complexity (2019-01-20 - 2019-01-25) (Details)

  • Computational Complexity
  • Data Structures and Algorithms

  • Parameterized Complexity
  • fixed-parameter tractability
  • intractability