<div class="csl-bib-body">
<div class="csl-entry">Dreier, J. N. (2024, September 9). <i>The combinatorics of monadic stability, monadic dependence, and related notions</i> [Presentation]. Algomanet - fall 2024, Warschau, Poland. http://hdl.handle.net/20.500.12708/207970</div>
</div>
Algorithmic Meta-Theorems are results that solve whole families of algorithmic problems on well-behaved classes of instances. The tractable instances are usually described using graph theory, and the families of algorithmic problems are typically described in terms of logic. In this context, we say a graph class is "tractable" if the first-order model-checking problem is FPT (fixed-parameter tractable) on this class. More precisely, a graph class C is "tractable" if there is an algorithm that decides for a given graph G from C and a sentence ɸ of first-order logic, in time f(ɸ)⋅|G|c if ɸ holds on G (where c is a small constant independent of G and ɸ). Landmark results show that nowhere dense graph classes, hereditary stable classes, and classes of ordered graphs of bounded twin-width are tractable.
The central conjecture in the field is that for hereditary graph classes (those closed under induced subgraphs), a graph class is tractable if and only if it is "dependent". Here, "dependence" refers to a very general notion originating from model theory, where it is usually considered in the infinite. In this course, I will introduce an ongoing program that aims to prove the central conjecture by first rediscovering dependence (and related notions) as purely combinatorial, finitary, graph-theoretic concepts, and then using these concepts to develop a model-checking algorithm.
In this context, most relevant approaches were originally developed for nowhere dense graph classes, then generalized to stable graph classes, and finally extended to dependent classes. Similarly, we start this course by exploring nowhere dense classes, then stable classes, and finally dependent classes.
en
dc.language.iso
en
-
dc.subject
Algorithmic Meta-Theorems
en
dc.subject
Graph Theory
en
dc.subject
Algorithms
en
dc.title
The combinatorics of monadic stability, monadic dependence, and related notions
en
dc.type
Presentation
en
dc.type
Vortrag
de
dc.type.category
Presentation
-
tuw.publication.invited
invited
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.author.orcid
0000-0002-2662-5303
-
tuw.event.name
Algomanet - fall 2024
-
tuw.event.startdate
09-09-2024
-
tuw.event.enddate
13-09-2024
-
tuw.event.online
On Site
-
tuw.event.type
Event for non-scientific audience
-
tuw.event.place
Warschau
-
tuw.event.country
PL
-
tuw.event.presenter
Dreier, Jan Niclas
-
tuw.event.track
Single Track
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.languageiso639-1
en
-
item.grantfulltext
none
-
item.cerifentitytype
Publications
-
item.openairetype
conference presentation
-
item.openairecristype
http://purl.org/coar/resource_type/R60J-J5BD
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
