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

Satellite Workshop of ICALP 2021
Monday 12 July 2021

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) has proven to be highly useful for designing efficient algorithms for many well-known problems, such as Feedback Vertex Set, Graph Colouring and Independent Set. That is, boundedness of width enables the application of a problem-specific dynamic programming algorithm or a meta-theorem to solve a certain problem. 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).

Registration

For free registration to the workshop, please fill in this form.

Format

This workshop will be held online, over Zoom.

It will be a one-day workshop, consisting of 6 invited talks, and finishing with a session for further discussion and open problems.

For the final session of the workshop, we invite short presentations that highlight an open problem or potential area for future research. If you wish to have a 10-minute slot in our workshop please send an email with a title and short description to a.munaro@qub.ac.uk.

Speakers

Programme

All times are in the Central European Summer Timezone (CEST), UTC+2, GMT+2.

9.30-10.15: David Wood – "The structure of planar graphs"
10.15-10.30: Break
10.30-11.15: Jan Arne Telle – "On Parameters in the Mim-width Family"
11.15-11.45: Break
11.45-12.30: Eunjung Kim – "Twin-width and Friends"
12.30-12.45: Break
12.45-13.30: Vadim Lozin – "A parametric approach to hereditary classes of graphs"
13.30-14.15: Break
14.15-15.00: Paweł Rzążewski – "The advantages of being modest: subexponential- and quasipolynomial-time algorithms for H-free graphs"
15.00-15.15: Break
15.15-16.00: Lalla Mouatadid – "Measuring Linear Structure on Graphs"
16.00-16.30: Break
16.30-18.30: Open problem session and discussion

Abstracts

David R. Wood – "The structure of planar graphs"

This talk is about graph structures that (potentially) are useful in algorithmic applications. The focus is on planar graphs, but many of the results hold for more general graph classes. The starting point is the Lipton-Tarjan separator theorem, followed by Baker's decomposition of a planar graph into layers with bounded treewidth. I will then move onto layered treewidth, which is a more global version of Baker's decomposition. Finally, I will introduce row treewidth, which is a refinement of layered treewidth. Dujmović et al [JACM '20] proved that planar graphs have bounded row treewidth. This result has been the key to solving several open problems, and is ripe for algorithmic applications.

Jan Arne Telle – "On Parameters in the Mim-width Family"

Mim-width is a parameter introduced by Vatshelle in his PhD thesis of 2012. In this talk we give a brief introduction to mim-width, comparing it to other width parameters, discussing graph classes of bounded mim-width and also algorithmic applications. We mention also sim-width which is bounded on larger graph classes like chordal graphs, and bi-mim-width that is used for directed graphs.

Eunjung Kim – "Twin-width and Friends"

Twin-width is a graph invariant which measures a distance to a cograph. Since its recent introduction in [Bonnet et al., FOCS '20], it turned out that twin-width has surprisingly versatile structure: it admits an efficient FO-model checking, remains robust under FO-transduction, allows simple and natural dynamic programming algorithms, and a class of bounded twin-width graphs is small, χ-bounded, equivalent to a proper permutation class under FO-transduction, and the list goes on. The notion of twin-width naturally extends to digraphs and binary structures in general. Many well-studied graph classes are known to have bounded twin-width including minor-closed classes, bounded rank-width graphs, unit interval graphs and map graphs, permutation graphs avoiding a fixed pattern and so on.
In this talk, we introduce the notion of twin-width and basic results about twin-width. Then we present a recent development on how known graph classes such as graphs of bounded path-width, tree-width and rank-width as well as minor-closed classes can be characterized using some natural variants of twin-width.

Vadim Lozin – "A parametric approach to hereditary classes of graphs"

The world of hereditary classes is rich and diverse, and it contains a variety of classes of theoretical or practical importance. Thousands of results in the literature have been devoted to individual classes and only few of them analyze the universe of hereditary classes as a whole. We explore this universe by means of graph parameters. With each parameter we associate the family of hereditary classes, where this parameter is bounded by a constant, and characterize this family by means of critical classes. In particular, we obtain a complete parametric description of the bottom of the universe of hereditary classes, up to classes of bounded neighbourhood diversity. We also obtain a description in terms of critical classes for a variety of other parameters, such as tree-width, tree-depth, h-index, VC-dimension, etc.

Paweł Rzążewski – "The advantages of being modest: subexponential- and quasipolynomial-time algorithms for H-free graphs"

The classical notion of tractability involves the existence of a polynomial-time algorithm for a given problem. However, there are many notorious problems for which we do not know such algorithms, with Independent Set in Pt-free graphs as a prominent example. It appears that some interesting results can be obtained if we are more modest and ask for subexponential-time or quasipolynomial-time algorithms. In the talk we survey recent exciting developments in the area, point out the important methods, and discuss possible directions for future research.

Lalla Mouatadid – "Measuring Linear Structure on Graphs"

We introduce a new graph parameter (LexCycle) that, we believe, measures the linear structure exhibited by various graph classes. LexCycle is based on multi-LexBFS traversals. In this talk, we'll briefly cover how graph searching has successfully been used to extract structural and algorithmic results on certain graph classes that seem to share a notion of linearity. We'll exhibit this linear structure in various classes (from perfect: cocomparability, to not so perfect: AT-free), and prove fixed point type theorems for LexBFS.

Organisers

Flavia Bonomo
University of Buenos Aires
Buenos Aires, Argentina

Nick Brettell
Victoria University of Wellington
Wellington, New Zealand

Andrea Munaro
Queen's University Belfast
Belfast, UK

Daniel Paulusma
Durham University
Durham, UK