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.

Creative Commons BY 4.0

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