Graph Width Parameters: from Structure to Algorithms (GWP 2023)

Satellite Workshop of ICALP 2023
Monday 10 July 2023

This is the third edition of GWP, following GWP 2021 and GWP 2022.

More information to come.

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:
  1. discovering general properties of graph classes from which we can determine the tractability or hardness of graph problems, and
  2. 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).


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