Generalized list matrix partition problems on chordal graphs, parameterized by leafage

Flavia Bonomo, University of Buenos Aires, Argentina.

Graph k-coloring and k-clique cover are examples of partition problems in graphs, in the first case into k independent sets, in the second case into k cliques. Moreover, maximum clique and maximum independent set are examples of partition problems into two sets, one arbitrary and the other one required to be a clique (resp. independent set), with the addition of a linear objective function to maximize. These are examples of matrix partition problems. For each symmetric matrix M over {0,1,*}, the M-partition problem seeks a partition of the input graph into independent sets, cliques, or arbitrary sets, with certain pairs of sets being required to have no edges joining them, or to have all edges joining them, as encoded in the matrix. Moreover, the vertices of the input graph can be equipped with lists, restricting the parts to which a vertex can be placed. Even if the first four problems (k-coloring, k-clique cover, maximum clique and maximum independent set) are polynomially solvable on chordal graphs, Feder, Hell, Klein, Nogueira and Protti in 2005 proved that there are M-partition problems (without lists or objective functions) that remain NP-complete for chordal graphs. In this talk, making use of a graph width parameter called “thinness”, we will show that all list matrix partition problems, with linear objective functions and further set cardinality restrictions, are XP on chordal graphs, parameterized by the leafage of the chordal graph. (The leafage of a chordal graph is the minimum number of leaves in a tree such that the graph can be realized as an intersection graph of subtrees of that tree.)

Twin-width, graph classes and a bit of logic

Eunjung Kim, LAMSADE, Paris-Dauphine University, France.

Twin-width is a graph parameter introduced in 2020 by Bonnet, Kim, Thomassé, Watrigant, which quickly gained much traction since then. The contraction of two vertices u,v, in a graph G is an operation that identifies u and v into a new vertex z, and updates the adjacency relations between z and x of V-{u,v} into (black) edge, non-edge and red edge: each reflects the state that {u,v} and {x} are homogeneously adjacent/homogeneously non-adjacent/ not homogeneous. Twin-width of a graph G is the minimum number that upper bounds the red degree of all vertices along the contraction sequence from G to a single-vertex graph.
Many well-studied graph classes like bounded tree-width and rank-width graphs, unit interval graphs, strict hereditary classes of permutations, minor-closed graph classes are known to have bounded twin-width, thus the list of bounded twin-width classes include both spare and dense classes. As such, the notion twin-width provides a new perspective to explain why so many computational problems are fixed-parameter tractable on graph classes seemingly so different. Moreover, natural variants of twin-width give an alternative characterization of graph class of bounded rank-width, tree-width and so on. 
For some graph classes such as ordered graphs, interval and permutation graphs, and tournaments, there is a strong indication that twin-width is the “right” measure to indicate the tameness of a graph class. That is, when a graph class C consists of ordered / interval / permutation graphs, the boundedness versus unboundedness of twin-width of C dictates the behaviors of the class, such as whether FO-model checking is tractable or not on C, whether the class of all graph can be “encoded” in the class C or not, etc. On the other hand, in general, twin-width is not a right notion for measuring the tameness of a class – the class of cubic graphs is tamed in the above sense, but the twin-width of a cubic graph can be arbitrarily large. We also review a recent effort to extend twin-width and capture a wider range of “tamed” graph classes.

Triangle-free graphs of large chromatic number

Nicolas Trotignon, CNRS, École Normale Supérieure de Lyon, France.

Many constructions of triangle-free graphs of arbitrarily large chromatic number have been proposed since the early age of graph theory. We will survey them, focusing on the constructions of Zykov (1952), Mycielski (1955) and Burling (1965). We will present a new construction called twin-cut graphs, recently obtained by Édouard Bonnet, Romain Bourneuf, Julien Duron, Colin Geniet, Stéphan Thomassé and the speaker. They are structurally simple in several respects. For instance, they are all obtained from complete graphs on one or two vertices by repeatedly applying simple operations: disjoint union, gluing along a vertex, gluing along two vertices, and replicating a vertex into a pair of non-adjacent vertices. This answer a question by Chudnovsky, Scott, Penev and the speaker. Also, the hereditary class formed by their induced subgraphs can be recognized in polynomial time. 

35 years of counting, sampling and mixing

Mark Jerrum, Queen Mary, University of London, UK.

The brief for this presentation indicated that it should be on the topic of a paper, with Alistair Sinclair, that appeared as an extended abstract in the proceedings of the 13th edition of this workshop, in 1987. At that time, the concepts listed in the title of the paper — approximate counting, uniform generation and rapidly mixing Markov chains — were only just beginning to be studied. (Nowadays, we would tend to use the term “sampling” rather than “generation”.) Nevertheless, the connections explored in the paper remain relevant today: that “conductance” (an expansion property of the state space of a Markov chain) implies mixing; that approximate counting and nearly uniform sampling are intimately linked, and that crude approximate sampling implies more precise approximate sampling. Although it could hardly be imagined at the time, these ideas were the seeds of a fruitful and coherent interdisciplinary research programme, driven by a host of talented theoretical computer scientists, probabilists and statistical physicists.

After sketching some of the main concepts, I shall take a problem-based approach, concentrating on approximately counting and sampling structures from graph theory. I shall aim to map the current frontier of research using some or all of following examples: matchings and perfect matchings, forests and connected spanning subgraphs, and vertex colourings. We have come a long way in 35 years, but there is more to explore.