##### Dagstuhl Seminar 21391

### Sparsity in Algorithms, Combinatorics, and Logic

##### ( Sep 26 – Oct 01, 2021 )

##### Permalink

##### Organizers

- Daniel Král' (Masaryk University - Brno, CZ)
- Michal Pilipczuk (University of Warsaw, PL)
- Sebastian Siebertz (Universität Bremen, DE)
- Blair D. Sullivan (University of Utah - Salt Lake City, US)

##### Contact

- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)

##### Impacts

- Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming - Brianski, Marcin; Koutecky, Martin; Kral, Daniel; Pekarkova, Kristyna; Schröder, Felix - Cornell University : arXiv.org, 2022. - 8 pp..
- Model Checking on Interpretations of Classesof Bounded Local Cliquewidth - Bonnet, Edouard; Dreier, Jan; Gajarsky, Jakub; Kreutzer, Stephan; Simon, Pierre; Torunczyk, Szymon; Mählmann, Nikolas - Cornell University : arXiv.org, 2022. - 28 pp..
- Transducing paths in graph classes with unbounded shrubdepth : article - Ossona de Mendez, Patrice; Pilipczuk, Michal; Siebertz, Sebastian - Cornell University : arXiv.org, 2022. - 22 pp..

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.

### 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.

- 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.
- 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.
- 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.
- 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.
- A discord server was set up to coordinate further communication and to keep track of the progress of the working groups.
- 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.

**On-site**

- Marthe Bonamy (University of Bordeaux, FR) [dblp]
- Édouard Bonnet (ENS - Lyon, FR) [dblp]
- Marcin Brianski (Jagiellonian University - Kraków, PL) [dblp]
- Jan Dreier (TU Wien, AT) [dblp]
- Zdenek Dvorák (Charles University - Prague, CZ) [dblp]
- Kord Eickmeyer (TU Darmstadt, DE) [dblp]
- Fedor V. Fomin (University of Bergen, NO) [dblp]
- Jakub Gajarský (University of Warsaw, PL) [dblp]
- Martin Grohe (RWTH Aachen University, DE) [dblp]
- Meike Hatzel (TU Berlin, DE) [dblp]
- Petr Hlinený (Masaryk University - Brno, CZ) [dblp]
- Gwenaël Joret (UL - Brussels, BE) [dblp]
- Noleen Koehler (University of Leeds, GB)
- Martin Koutecký (Charles University - Prague, CZ) [dblp]
- Daniel Král' (Masaryk University - Brno, CZ) [dblp]
- Stephan Kreutzer (TU Berlin, DE) [dblp]
- Nikolas Mählmann (Universität Bremen, DE) [dblp]
- Piotr Micek (Jagiellonian University - Kraków, PL) [dblp]
- Wojciech Nadara (University of Warsaw, PL) [dblp]
- Jaroslav Nešetril (Charles University - Prague, CZ) [dblp]
- Jan Obdržálek (Masaryk University - Brno, CZ) [dblp]
- Patrice Ossona de Mendez (EHESS - Paris, FR) [dblp]
- Kristýna Pekárková (Masaryk University - Brno, CZ) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Michal Pilipczuk (University of Warsaw, PL) [dblp]
- Felix Schröder (TU Berlin, DE) [dblp]
- Sebastian Siebertz (Universität Bremen, DE) [dblp]
- Dimitrios M. Thilikos (University of Montpellier & CNRS, FR) [dblp]
- Szymon Torunczyk (University of Warsaw, PL) [dblp]
- Torsten Ueckerdt (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Alexandre Vigny (Universität Bremen, DE) [dblp]
- Bartosz Walczak (Jagiellonian University - Krakow, PL) [dblp]

**Remote:**

- Saeed Amiri (Universität Köln, DE) [dblp]
- Daniel Cranston (Virginia Commonwealth University - Richmond, US) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- Peter Gartland (University of California - Santa Barbara, US) [dblp]
- Archontia C. Giannopoulou (University of Athens, GR) [dblp]
- Mario Grobler (Universität Bremen, DE) [dblp]
- Shweta Jain (University of Utah - Salt Lake City, US) [dblp]
- Ken-ichi Kawarabayashi (National Institute of Informatics - Tokyo, JP) [dblp]
- O-joung Kwon (Incheon National University, KR) [dblp]
- Aurelie Lagoutte (Université Clermont Auvergne - Aubiere, FR) [dblp]
- Brian Lavallee (University of Utah - Salt Lake City, US) [dblp]
- Rose McCarty (University of Waterloo, CA) [dblp]
- Yosuke Mizutani (University of Utah - Salt Lake City, US) [dblp]
- Sang-il Oum (IBS - Daejeon, KR) [dblp]
- Filip Pokrývka (Masaryk University - Brno, CZ) [dblp]
- Evangelos Protopapas (University of Montpellier & CNRS, FR)
- Wojciech Przybyszewski (University of Warsaw, PL)
- Daniel Quiroz (Universidad de Valparaiso, CL) [dblp]
- Felix Reidl (Birkbeck, University of London, GB) [dblp]
- Benjamin Rossman (Duke University - Durham, US) [dblp]
- Saket Saurabh (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Nicole Schirrmacher (Universität Bremen, DE)
- Nicole Schweikardt (HU Berlin, DE) [dblp]
- Luc Segoufin (INRIA & ENS Paris, FR) [dblp]
- Marek Sokolowski (University of Warsaw, PL) [dblp]
- Giannos Stamoulis (University of Montpellier 2, FR) [dblp]
- Blair D. Sullivan (University of Utah - Salt Lake City, US) [dblp]
- Nate Veldt (Texas A&M University - College Station, US) [dblp]
- David Wood (Monash University - Clayton, AU) [dblp]

##### Classification

- data structures / algorithms / complexity

##### Keywords

- algorithm design
- parameterized complexity
- sparse graphs
- graph decompositions
- model theory