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 25041

Solving Problems on Graphs: From Structure to Algorithms

( Jan 19 – Jan 24, 2025 )

Please use the following short url to reference this page:




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.

Copyright Akanksha Agrawal, Maria Chudnovsky, 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)

  • Computational Complexity
  • Data Structures and Algorithms
  • Discrete Mathematics

  • computational complexity
  • graph classes
  • graph containment relations
  • graph width parameters
  • graph algorithms