Motivation

It was realized already in the early days of computer science that structures (networks, databases, etc.) that are sparse appear ubiquitously in applications. The sparsity of input can be used in a variety of ways, e.g. to design efficient algorithms. This motivates a theoretical study of the abilities and limitations of sparsity-based methods. However, a priori it is not clear how to even define sparsity formally. Multiple sparsity-oriented paradigms have been studied in the literature, e.g. bounded maximum or average degree models, topologically constrained classes of graphs or graphs with bounded width parameters. However, many of those paradigms suffer from being either too restrictive to model real-life applications, or too general to yield strong tractability results.

In the late 2000’s, Ne¹etøil and Ossona de Mendez proposed a new framework of uniform structural sparsity for classes of graphs that generalized existing definitions and initiated the development of a toolbox of sparsity-based methods for analyzing graphs. The central notions of their framework are bounded expansion and nowhere dense classes. It quickly turned out that the proposed notions can be used to build a mathematical theory of sparse graphs that offers a wealth of tools, leading to new techniques and powerful results. This theory has been extensively developed in the recent years.

It is particularly remarkable that the concepts of classes of bounded expansion and nowhere dense classes can be connected to fundamental ideas from multiple other fields of computer science, often in a surprising way, providing several complementary viewpoints on the subject. On one hand, foundations of the area are grounded in structural graph theory, which aims at describing structure in graphs through various decompositions and auxiliary parameters. On the other hand, nowhere denseness seems to delimit the border of algorithmic tractability of first-order logic, providing a link to finite model theory and its computational aspects. Finally, there is a fruitful transfer of ideas to and from the field of algorithm design: sparsity-based methods can be used to design new, efficient algorithms, especially in the paradigms of parameterized complexity, approximation algorithms, and distributed computing. Further, classic techniques for designing algorithms on sparse inputs inspire new combinatorial results on sparse graphs.

The aim of this Dagstuhl Seminar is to bring together researchers working on various aspects of sparsity in their own fields, in order to facilitate the exchange of ideas, methods and questions between different communities. So far, the synergy effect between graph theory, logic, and algorithm design has led to fundamental developments in the theory of sparse graph classes. Our goal is to inspire a new wave of developments by "stirring in the pot" of researchers working on different facets of sparsity. An important part of the seminar will be the discussion of the (still fledgling) area of real-life applications of sparsity-based methods, where theory and practice could meet.

Seminar organization

Due to the on-going COVID pandemic, the seminar was held in hybrid format. In total the seminar was attended by 61 participants around the world (from North America to Europe to Asia). 32 of the participants were on-site and 29 remote. To make the hybrid format a success and in particular allow all members to participate in talks and working groups, the following measures were taken.

1. To accommodate both on-site and remote participants, a mix of on-site and remote talks were scheduled. The talks were scheduled in the early to late afternoon (MEZ local time), allowing remote audience members from all parts of the world to attend.
2. Both on-site and remote talks were streamed via zoom. The zoom session was projected onto a whiteboard in the seminar room. The remote participants could see and hear the on-site whiteboard and slide presentations. They could interrupt and ask questions or ask questions in the chat, which were then read by the organizers. This turned out to be a quite successful setup in which all participants could discuss in real-time.
3. On the first day of the seminar we had a short introduction of all participants, one invited tutorial lecture, one contributed talk and the open problem session. In total, we had 5~tutorial lectures and 12 contributed talks spread over the week. The topics and speakers were chosen to create a joint understanding of the state of the art in the fields that were brought together in the seminar.
4. The remaining program put a strong emphasis on open time for ad-hoc discussions and working in groups. After the open problem session on Monday, several groups of on-site and remote participants were formed, who approached the posed problems.
5. A discord server was set up to coordinate further communication and to keep track of the progress of the working groups.
6. A social event was organized online on Tuesday evening.

Work on open problems

Following the open problem session on the first day of the workshop, spontaneous groups working on selected open problems emerged. These typically included a mix of on-site and online participants, working in either synchronous or asynchronous manner using the Discord platform as a mean of communication. Below we list a selection of directions that were pursued during the seminar.

Model-checking on interpretations of locally well-behaved structures. It is known that model-checking First Order logic (FO) can be done in fixed-parameter time on classes of graphs that are locally well-behaved, for instance have locally bounded treewidth. However, the question is whether this is still true if the input graph is ``logically disguised'', or more precisely, has been additionally mapped through some FO transduction. The aim of this research group was to provide an affirmative answer by proving the following theorem: For every class of graphs ${mathscr C}$ that is stable and can be transduced from a class of locally bounded cliquewidth, the model-checking problems for FO is fixed-parameter tractable on ${mathscr C}$. This would generalize several known results on efficient FO model-checking on classes of dense graphs, e.g. map graphs or interpretations of classes of bounded degree, as well as provide multiple new results.

Transducing paths from classes of unbounded shrubdepth. The emerging logically-motivated structure theory for graphs uses First-Order transductions as the main notion of embedding. It is important to understand possible duality theorems for this notion, of the following form: If a class of graphs C does not admit a decomposition of some form, then C transduces a class of specific obstacles witnessing this conclusion. The aim of this research group was to prove the most basic conjecture following this pattern: If a class of graphs C has unbounded shrubdepth, then C transduces the class of all paths.

Treedepth vs pathwidth. It is known that every graph of pathwidth Omega(ab) has treewidth at least a or contains a binary tree of depth $b$ as a minor. It is also known that every graph of treedepth Omega(abc) has treewidth at least a, or contains a binary tree of depth b as a minor, or contains a simple path of length 2^c. This suggests the following conjecture: every graph of treedepth Omega(bc) has either pathwidth at least b or contains a simple path of length 2^c. The aim of this research group was to resolve this conjecture.

{Treewidth-twin-width. The definition of the recently introduced graph parameter twin-width revolves around the mechanism of contraction sequences: simplification operations using which one can "fold" the whole graph into a single vertex. The main complexity measure of a contraction sequence is the maximum number of error edges that are adjacent to any vertex at any time. The goal of this group was to investigate the combinatorial properties of a graph parameter dubbed treewidth-twin-width obtained by additionally requiring that at all times, the graph composed of the error edges has bounded treewidth. Of particular interest is whether various classes known to have bounded twin-width actually have bounded treewidth-twin-width.

Integer programs equivalent to ones with bounded primal treedepth. Integer programming is known to be efficiently solvable for instances with small primal or dual treedepth. While we have a relatively good understanding of conditions when the instance can be transformed to an instance with small dual treedepth, less is known in the case of primal treedepth. The aim of this research group was to relate, for a given instance of integer programming, the smallest possible primal treedepth of an equivalent instance to invariant properties of the instance itself, in particular, to the structure of the column matroid of the constraint matrix. The ultimate goal would be to design algorithms for constructing an equivalent instance with small primal treedepth while avoiding a blow up in the entry complexity (such a blow up would prevent using the existing IP algorithms to solve the constructed instance).

Acknowledgements

Schloss Dagstuhl provided an excellent environment for hosting the seminar. The seminar room was appropriate to host the on-site participants and we found plenty of room for continuing discussions and socializing outside of the official program. This is particularly remarkable in these difficult times with the ongoing COVID pandemic. All participants were eager to meet and research together. According to the conducted survey, as well as the informal feedback to the organizers, the seminar was highly appreciated and can be considered a full success. On behalf of all participants, the organizers want to express their gratitude to the entire Dagstuhl staff and their outstanding support and service throughout the seminar.

Creative Commons BY 4.0

Daniel Král', Michal Pilipczuk, Sebastian Siebertz, and Blair D. Sullivan