Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 24411

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

( Oct 06 – Oct 11, 2024 )

Please use the following short url to reference this page:




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

Related Seminars
  • 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