Dagstuhl Seminar 24411
New Tools in Parameterized Complexity: Paths, Cuts, and Decomposition
( Oct 06 – Oct 11, 2024 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/24411
Organizers
- Fedor V. Fomin (University of Bergen, NO)
- Dániel Marx (CISPA - Saarbrücken, DE)
- Saket Saurabh (The Institute of Mathematical Sciences - Chennai, IN)
- Roohani Sharma (MPI für Informatik - Saarbrücken, DE)
Contact
- Michael Gerke (for scientific matters)
- Christina Schwarz (for administrative 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.
- Upload (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
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
Please log in to DOOR to see more details.
- Akanksha Agrawal (Indian Institute of Techology Madras, IN) [dblp]
- Aditya Anand (University of Michigan - Ann Arbor, US)
- Matthias Bentert (University of Bergen, NO)
- Édouard Bonnet (ENS - Lyon, FR) [dblp]
- Joseph Cheriyan (University of Waterloo, CA) [dblp]
- Éric Colin de Verdière (Gustave Eiffel University - Marne-la-Vallée, FR) [dblp]
- Eduard Eiben (Royal Holloway, University of London, GB) [dblp]
- Fedor V. Fomin (University of Bergen, NO) [dblp]
- Robert Ganian (TU Wien, AT) [dblp]
- Petr A. Golovach (University of Bergen, NO) [dblp]
- Bart Jansen (TU Eindhoven, NL) [dblp]
- Eun Jung Kim (KAIST - Daejeon, KR & CNRS - Paris, FR) [dblp]
- Yusuke Kobayashi (Kyoto University, JP) [dblp]
- Christian Komusiewicz (Friedrich-Schiller-Universität Jena, DE) [dblp]
- Tuukka Korhonen (University of Copenhagen, DK) [dblp]
- Stefan Kratsch (HU Berlin, DE) [dblp]
- Madhumita Kundu (University of Bergen, NO) [dblp]
- Euiwoong Lee (University of Michigan - Ann Arbor, US) [dblp]
- Bingkai Lin (Nanjing University, CN) [dblp]
- William Lochet (CNRS - Montpellier, FR) [dblp]
- Daniel Lokshtanov (University of California - Santa Barbara, US) [dblp]
- Dániel Marx (CISPA - Saarbrücken, DE) [dblp]
- Neeldhara Misra (Indian Institute of Techology - Madras, IN) [dblp]
- Pranabendu Misra (Chennai Mathematical Institute, IN) [dblp]
- Jesper Nederlof (Utrecht University, NL) [dblp]
- Daniel Neuen (MPI für Informatik - Saarbrücken, DE) [dblp]
- Fahad Panolan (University of Leeds, GB) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Michal Pilipczuk (University of Warsaw, PL) [dblp]
- Thatchaphol Saranurak (University of Michigan - Ann Arbor, US) [dblp]
- Ignasi Sau Valls (LIRMM, Université de Montpellier, CNRS - Montpellier, FR) [dblp]
- Saket Saurabh (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Roohani Sharma (MPI für Informatik - Saarbrücken, DE) [dblp]
- Ramanujan Sridharan (University of Warwick - Coventry, GB) [dblp]
- Giannos Stamoulis (University of Warsaw, PL) [dblp]
- Vaishali Surianarayanan (University of California - Santa Barbara, US)
- Stefan Szeider (TU Wien, AT) [dblp]
- Erik Jan van Leeuwen (Utrecht University, NL) [dblp]
- Magnus Wahlström (Royal Holloway, University of London, GB) [dblp]
- Michal Wlodarczyk (University of Warsaw, PL) [dblp]
- Jie Xue (New York University - Shanghai, CN) [dblp]
Related Seminars
Classification
- Computational Complexity
- Data Structures and Algorithms
Keywords
- Parameterized Complexity
- fixed-parameter tractability
- intractability
