Dagstuhl Seminar 28121
Solving Problems on Augmented Graphs: From Structure to Algorithms
( Mar 19 – Mar 24, 2028 )
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/28121
Organizers
- Maria Chudnovsky (Princeton University, US)
- Bart Jansen (TU Eindhoven, NL)
- Daniel Paulusma (Durham University, GB)
- Oliver Schaudt (Bayer AG - Leverkusen, DE)
Contact
- Michael Gerke (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
Many discrete optimization problems can be modelled as graph problems, leading to a long list of well-studied problems including graph partitioning, covering and packing problems, network design problems, width parameter problems, and so on. Our seminar deals with problems on graphs that are augmented with additional data that specify requirements on the desired output or properties of the given input. An example of such a problem is Steiner Tree, where a special set of vertices called terminals must be connected by a minimum-weight subtree of the input graph. Most augmented graph problems are computationally hard. This leads to the fundamental question, which lie at the heart of our Dagstuhl Seminar: how can we deal with computational hardness of problems on augmented graphs?
A well-established line of research investigates how structural restrictions on an input graph be exploited to obtain polynomial-time or fixed-parameter tractable algorithms, leading to a fruitful interplay between structural graph theory and algorithm design. The goal of the workshop is to develop the corresponding synergy for problems on augmented graphs. This leads to questions such as: how can structural limitations on the placement of terminals be used to solve Steiner Tree efficiently? To investigate the translation of the structure of augmented graphs into algorithms, we aim to bring together researchers from Discrete Mathematics and Theoretical Computer Science.
Topics of the Dagstuhl Seminar will include:
- Structure and algorithms for annotated graphs
- Width parameters for annotated graphs
- Structure and algorithms for graphs augmented with an intersection model
- Parameterized complexity
- Special graph classes
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 problems on augmented graphs. This will also increase our understanding of how the complexities of different graph problems are related to each other.
Creative Commons BY 4.0
Maria Chudnovsky, Bart Jansen, Daniel Paulusma, and Oliver Schaudt
Related Seminars
- Dagstuhl Seminar 19271: Graph Colouring: from Structure to Algorithms (2019-06-30 - 2019-07-05) (Details)
- Dagstuhl Seminar 22481: Vertex Partitioning in Graphs: From Structure to Algorithms (2022-11-27 - 2022-12-02) (Details)
- Dagstuhl Seminar 25041: Solving Problems on Graphs: From Structure to Algorithms (2025-01-19 - 2025-01-24) (Details)
Classification
- Computational Complexity
- Data Structures and Algorithms
- Discrete Mathematics
Keywords
- graph classes
- graph width parameters
- graph algorithms
- augmented graphs
- structural graph theory
