Graph Width Parameters: from Structure to Algorithms (GWP 2025)
This is the fourth edition of GWP, following GWP 2021,
GWP 2022 and GWP 2023.
We acknowledge financial support from Durham University.
Aim and Scope
Most optimization problems defined on graphs are computationally hard. For such problems it is natural to restrict the input and ask:
For which graph classes does the problem become efficiently solvable and for which graph classes does it stay hard?
Knowing that a graph has small "width" (for example, treewidth, clique-width, mim-width, twin-width) has proven to be highly useful for designing efficient algorithms for many well-known problems, such as Graph Colouring, Independent Set, and Feedback Vertex Set. That is, a guarantee of bounded width enables a certain problem to be solved by a dynamic programming algorithm, or by applying a meta-theorem.
However, for many graph classes it is not known if the class has small width for some appropriate width parameter. This has resulted in ad-hoc efficient algorithms for special graph classes that may unknowingly make use of the fact that the graph classes under consideration have small width.
More generally speaking, rather than solving problems one by one and graph-class by graph-class, the focus of our satellite workshop is:
- discovering general properties of graph classes from which we can determine the tractability or hardness of graph problems, and
- discovering which graph problems can be solved efficiently on graph classes of bounded width.
For this purpose we aim to bring together researchers from Discrete Mathematics (structure) and Theoretical Computer Science (algorithms).
More information to come.
Organisers
Flavia Bonomo
University of Buenos Aires
Buenos Aires, Argentina
Nick Brettell
Victoria University of Wellington
Wellington, New Zealand
Andrea Munaro
University of Parma
Parma, Italy
Daniel Paulusma
Durham University
Durham, UK