Dagstuhl-Seminar 25041
Solving Problems on Graphs: From Structure to Algorithms
( 19. Jan – 24. Jan, 2025 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/25041
Organisatoren
- Akanksha Agrawal (Indian Institute of Techology Madras, IN)
- Maria Chudnovsky (Princeton University, US)
- Daniel Paulusma (Durham University, GB)
- Oliver Schaudt (Bayer AG - Leverkusen, DE)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Christina Schwarz (für administrative Fragen)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Programm
Many discrete optimization problems can be modeled as graph problems, leading to a long list of well-studied problems, which include graph partitioning, covering and packing problems, network design problems, width parameter problems, and so on. Most of these graph problems are computationally hard. However, this situation may change if we require the input to belong to some special graph class. This leads to two fundamental questions, which formed the focus of our Dagstuhl Seminar: for which classes of graphs can a computationally hard graph problem be solved in polynomial time, and for which classes of graphs does the problem remain hard?
One of the main research aims of our seminar was to discover new insights that lead to results for a whole range of problems rather than just for a single problem alone. That is, our goal was to determine general properties, such that large classes of graph problems sharing certain common features can be solved efficiently on a graph class if and only if the graph class has these properties. For this purpose, our seminar brought together researchers from Discrete Mathematics, working in structural graph theory, and researchers from Theoretical Computer Science, working in algorithmic graph theory. In total, 41 participants from 13 different countries attended the seminar.
The scientific program of the seminar consisted of 18 sessions: 5 survey talks of fifty minutes, 10 contributed talks of at most thirty minutes, and 5 open problem sessions. This left ample time for discussions and problem-solving. Participants presented the progress that was made during the seminar during several "progress report" sessions.
Each of the five survey talks covered a particular structural or algorithmic key aspect of the seminar in order to enable collaborations of researchers with different backgrounds. On Monday, Tuukka Korhonen presented a survey on new results on induced minors of graphs. This is a well-known graph containment relation, but recently developed techniques led to significant progress and new open problems. On the same day, \'Edouard Bonnet discussed a number of new results and open problems on twin-width, a relatively new graph width parameter that is being studied intensively. The final survey talk on Monday was given by Stefan Kratsch, who discussed a number of open problems around modular-based graph parameters and graph width parameters from the perspective of parameterized complexity.
On Tuesday, Maria Chudnovsky presented an overview of the induced subgraphs and tree decompositions project that currently comprises a series of 18 papers. Afterward, Nicolas Trotignon explained the importance of layered wheels. These are graphs of arbitrarily large treewidth that play a significant role in the induced subgraphs and tree decompositions project. In general, a layered wheel consists of many paths, all pairwise with edges between them (thus guaranteeing large treewidth), where many additional desired properties may be forced. Thus layered wheels provide a useful source of boundary examples of families of graphs with large treewidth. A few weeks after the completion of our seminar, three of the participants, Bogdan Alecu, \'Edouard Bonnet, and Nicolas Trotignon, found, together with Pedro Bureo Villafana, a large new family of layered wheels providing counterexamples to several known conjectures in the field, some of which were discussed at the seminar.
The five general open problem sessions took place on Monday, Tuesday, Wednesday, and Thursday. Details of the presented problems can be found in the report, together with abstracts of all the talks.
We thank Julien Codsi for his help with the Dagstuhl Report of our seminar.
Creative Commons BY 4.0
Akanksha Agrawal, Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt
Many discrete optimization problems can be modelled as graph problems, leading to a long list of well-studied problems, which include graph partitioning, covering and packing problems, network design problems, width parameter problems, and so on. Most of these graph problems are computationally hard. However, this situation may change if we require the input to belong to some special graph class. This leads to two fundamental questions, which lie at the heart of our Dagstuhl Seminar: for which classes of graphs can a computationally hard graph problem be solved in polynomial time, and for which classes of graphs does the problem remain hard?
In our seminar, we aim to discover new insights that lead to results for a whole range of problems rather than just for a single problem alone. That is, our goal is to determine general properties, such that large classes of graphs problems sharing certain common features can be solved efficiently on a graph class if and only if the graph class has these properties. For this purpose, we aim to bring together researchers from Discrete Mathematics and Theoretical Computer Science.
Topics of the seminar will include:
- Graph Algorithms
- Graph Classes
- Graph Containment Relations
- Parameterized Complexity
- Width Parameters.
We plan an appropriate number of survey talks, presentations of recent results, open problem sessions, and ample time for problem solving. As outcomes we expect to develop new, general methodology for solving a large variety of graph problems. This will also increase our understanding of how the complexities of different graph problems are related to each other.
Akanksha Agrawal, Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt
Please log in to DOOR to see more details.
- Akanksha Agrawal (Indian Institute of Techology Madras, IN) [dblp]
- Bogdan Alecu (University of Leeds, GB) [dblp]
- Édouard Bonnet (ENS - Lyon, FR) [dblp]
- Maria Chudnovsky (Princeton University, US) [dblp]
- Julien Codsi (Princeton University, US)
- Konrad Dabrowski (Newcastle University, GB) [dblp]
- Esther Galby (TU Hamburg, DE) [dblp]
- Jan Goedgebeur (KU Leuven, BE) [dblp]
- Petr A. Golovach (University of Bergen, NO) [dblp]
- Meike Hatzel (IBS - Daejeon, KR) [dblp]
- Lars Jaffke (Norwegian School of Economics - Bergen, NO) [dblp]
- Bart Jansen (TU Eindhoven, NL) [dblp]
- Jorik Jooken (KU Leuven, BE)
- Tuukka Korhonen (University of Copenhagen, DK) [dblp]
- Stefan Kratsch (HU Berlin, DE) [dblp]
- Michael Lampis (University Paris-Dauphine, FR) [dblp]
- Paloma Lima (IT University of Copenhagen, DK) [dblp]
- Daniel Lokshtanov (University of California - Santa Barbara, US) [dblp]
- Barnaby Martin (Durham University, GB) [dblp]
- Martin Milanic (University of Primorska, SI) [dblp]
- Pranabendu Misra (Chennai Mathematical Institute, IN) [dblp]
- Andrea Munaro (University of Parma, IT) [dblp]
- Daniel Neuen (MPI für Informatik - Saarbrücken, DE) [dblp]
- Jelle Oostveen (Utrecht University, NL) [dblp]
- Sukanya Pandey (RWTH Aachen, DE) [dblp]
- Fahad Panolan (University of Leeds, GB) [dblp]
- Daniel Paulusma (Durham University, GB) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Michal Pilipczuk (University of Warsaw, PL) [dblp]
- Pawel Rzazewski (Warsaw University of Technology, PL) [dblp]
- Saket Saurabh (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Oliver Schaudt (Bayer AG - Leverkusen, DE) [dblp]
- Roohani Sharma (MPI für Informatik - Saarbrücken, DE) [dblp]
- Mark Siggers (Kyungpook National University - Daegu, KR) [dblp]
- Siani Smith (University of Bristol, GB)
- Ramanujan Sridharan (University of Warwick - Coventry, GB) [dblp]
- Csaba Tóth (California State University - Northridge, US) [dblp]
- Nicolas Trotignon (CNRS - Ecole Normale Supérieure de Lyon, FR) [dblp]
- Kristina Vuskovic (University of Leeds, GB) [dblp]
- Michal Wlodarczyk (University of Warsaw, PL) [dblp]
- Viktor Zamaraev (University of Liverpool, GB) [dblp]
Verwandte Seminare
Klassifikation
- Computational Complexity
- Data Structures and Algorithms
- Discrete Mathematics
Schlagworte
- computational complexity
- graph classes
- graph containment relations
- graph width parameters
- graph algorithms
