Ομιλητής: Sebastian Wiederrecht (LIRMM)
Τίτλος: Tangle Duality and Monotonicity in Digraph Searching
Ημερομηνία: 24-03-2022, 14:00
Αίθουσα: Α56, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Σύνοψη
In undirected graphs tangles yield an obstructions to small treewidth. This gives a way to decompose graphs into highly connected and structurally rich areas. Though there is much understanding on how such decompositions can be found and deployed in undirected graphs, the picture is more complicated for directed graphs.
In this talk, we present a generalisation of tangles to directed graphs which we show to be dual to a width-parameter very close to DAG-width. In fact, we show that the width parameter we find through this approach correspondence to strategies in the (non-monotone) cops and robber reachability game. Hence our approach yields, for the first time, a width parameter for digraphs, together with a decomposition, capturing a non-monotone variant of DAG-width.