Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Innerhalb dieser Seite:
Externe Seiten:
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp

Dagstuhl-Seminar 20121

Sparsity in Algorithms, Combinatorics and Logic Postponed

( 15. Mar – 20. Mar, 2020 )

Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:

Ersetzt durch
Dagstuhl-Seminar 21391: Sparsity in Algorithms, Combinatorics, and Logic (2021-09-26 - 2021-10-01) (Details)





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.

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

  • Michal Pilipczuk (University of Warsaw, PL) [dblp]
  • Sebastian Siebertz (Universität Bremen, DE) [dblp]
  • Blair D. Sullivan (University of Utah - Salt Lake City, US) [dblp]

  • data structures / algorithms / complexity

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