https://www.dagstuhl.de/20121

March 15 – 20 , 2020, Dagstuhl Seminar 20121

Sparsity in Algorithms, Combinatorics and Logic

Organizers

Daniel Král' (Masaryk University – Brno, CZ)
Michal Pilipczuk (University of Warsaw, PL)
Sebastian Siebertz (HU Berlin, DE)
Blair D. Sullivan (North Carolina State University – Raleigh, US)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Michael Gerke for scientific matters

Documents

Dagstuhl Seminar Schedule (Upload here)

(Use seminar number and access code to log in)

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.

Motivation text license
  Creative Commons BY 3.0 DE
  Daniel Král', Michal Pilipczuk, Sebastian Siebertz, and Blair D. Sullivan

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Algorithm design
  • Parameterized complexity
  • Sparse graphs
  • Graph decompositions
  • Model theory

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.