Seminar on Foundations of Computing

This research seminar provides a venue for presenting research results concerning algorithm design, discrete mathematics, formal methods, logic and related areas of theoretical computer science. The seminar is jointly organized by the research laboratories DIMEA, FORMELA, and LIVE. The seminar builds on the FMDSA seminar organized by the FORMELA laboratory in the past.

Time and place

The seminar takes place on Monday at 2PM term time in Room A321 in the building of the Faculty of Informatics on a (roughly) weekly schedule.

Fall 2024 – schedule overview

September 02	Niklas Schlomberg (Bonn)	Packing cycles in planar and bounded-genus graphs
September 16	Kush Grover (Brno)	Fuzzy Path Logic: A new preference logic for motion planning
September 23	Eva Výtvarová (CEITEC)	Human brain structure-function relationship: zooming-out to the whole-brain network
October 14	Jared Leon-Malpartida	Reed's conjecture and a recolourability version for of odd-hole-free graphs
November 04	Marcin Briański	On Erdős-Pósa properties of some acyclic patterns in directed graphs
November 11	Josef Tkadlec	Fixation times of the Moran process
November 18	Alexandru Malekshahian	Many distinct lengths of leaf-to-leaf paths in bounded degree trees
November 25	Veronika Eclerová	Oscillations All Around Us: Exploring Synchronization in Complex Systems

Upcoming speakers

December 9	Ander Lamaison	Palettes determine uniform Turán density
December 16	Richard Mayr	2-player Stochastic Reachability Games: Strategy Complexity and Computational Complexity

Niklas Schlomberg : Packing cycles in planar and bounded-genus graphs

Monday, September 02, 14:00, room C417

We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. The family of cycles under consideration must be uncrossable and allow for a certain oracle access. Our setting generalizes many problems that were studied separately in the past. For example, three families that satisfy the above properties are (i) all cycles in a directed or undirected graph, (ii) all odd cycles in an undirected graph, and (iii) all cycles in an undirected graph that contain precisely one demand edge, where the demand edges form a subset of the edge set. The latter family (iii) corresponds to the classical disjoint paths problem in fully planar and bounded-genus instances. While constant-factor approximation algorithms were known for edge-disjoint paths in such instances, we improve the constant in the planar case and obtain the first such algorithms for vertex-disjoint paths. We also obtain approximate min-max theorems of the Erdős--Pósa type.

This is joint work with Hanjo Thiele and Jens Vygen.

Kush Grover: Fuzzy Path Logic: A new preference logic for motion planning

Monday, September 16, 14:00, room C417

Defining soft preferences for motion planning (MP) in Signal Temporal Logic (STL) can work to some extent by using robustness. However, undesired paths may still be considered optimal. To address this, we introduce a new family of temporal logics specifically designed for soft preferences. This logic naturally expresses path segments and handles degrees of satisfaction more flexibly. Built on fuzzy, time-varying signal constraints, it offers greater expressivity, making it (i) more intuitive for human-given specifications in MP, and (ii) more suitable for learning specifications from demonstrations compared to other logics.

Eva Výtvarová: Human brain structure-function relationship: zooming-out to the whole-brain network

Monday, September 23, 14:00, room C417

The human brain can be viewed as a coupled system where nonlinear interactions give rise to emergent phenomena such as perception, cognition, and consciousness. This system has a structure that can be represented as a network of grey matter brain nodes mutually connected by white matter tracts. In this talk, I will introduce diverse communication models proposing scenarios of information propagation on the structural substrate. From the intentional stimulation, I will move towards spontaneous whole-brain activity and demonstrate that even at rest, a human brain behaves in an organized manner that can be described by network topology parameters, patterns, or co-activation states both in spatial and temporal domains. Many of these parameters are robust and can be used to differentiate between health and disease or between diverse conditions during data acquisition.

Jared Leon-Malpartida: Reed's conjecture and a recolourability version for of odd-hole-free graphs

Monday, October 14, 14:00, room A321

Given a vertex colouring of a graph, a Kempe chain is a bichromatic component of the graph. Performing a Kempe chain operation consists of swapping the colours of the vertices within a Kempe chain. Kempe chains are central in the known proofs of classical colouring results, namely the four-colour theorem and Vizing’s edge-colouring theorem. We say that a graph is k-recolourable if any k-colouring of the graph can be obtained by starting with a k-colouring and performing a sequence of Kempe changes.
Motivated by Reed's conjecture, it was recently conjectured that for all 0≤ε<1/3, any graph is k-recolourable for all k>⌈εω(G)+(1−ε)(Δ(G)+1)⌉. A result by Bonamy, Kaiser, and Legrand-Duchesne towards this conjecture implies that odd-hole-free graphs have no frozen k-colourings for k>⌈(ω(G)+Δ(G)+1)/2⌉, which are the main known obstructions to recolourability. Thus, they also conjectured that all odd-hole-free graphs are k-recolourable for k>⌈(ω(G)+Δ(G)+1)/2⌉. Furthermore, they settled this conjecture for the special case of perfect graphs and a weakened version of it for arbitrary odd-hole-free graphs.
In joint work with De Meyer, Legrand-Duchesne, Planken, and Tamitegama, we prove that any odd-hole-free graph is k-recolourable for k>⌈(ω(G)+Δ(G)+2)/2⌉. In this talk, I will present the main ideas behind this proof.

Marcin Briański: On Erdős-Pósa properties of some acyclic patterns in directed graphs

Monday, November 4, 14:00, room A321

A seminal result of Erdős and Pósa from 1965 states that every graph either contains k pairwise vertex disjoint cycles or a set of O(k log k) vertices intersecting every cycle (in modern terminology we say that cycles have the Erdős-Pósa property [EP property for short here]). This result led to many developments in structural graph theory with many results for e.g. EP property of minor models of a fixed planar graph or even length cycles. Arguably, establishing EP property becomes much harder if one wishes to investigate it in the context of directed graphs. Indeed, it took more than 20 years to prove EP property of directed cycles (proven by Reed, Robertson, Seymour, and Thomas in 1996). And, to my knowledge, the only acyclic pattern for which EP property in directed graphs is known is the path (c.f. Menger's theorem). In this talk I will discuss a result on the EP property of another class of directed acyclic patterns called tripods.
Based on joint work with Meike Hatzel, Karolina Okrasa, and Michał Pilipczuk.

Josef Tkadlec: Fixation times of the Moran process

Monday, November 11, 14:00, room A321

Moran process is a classic random process that models the competition of two or more types of individuals on a network-structured population. The individuals reproduce, the offspring migrate along the edges of the network, and they replace the neighbors. In the absence of mutation, one of the types eventually triumphs over the whole network. We survey the existing results on the time (that is, the number of steps of the Moran process) until this occurs. We consider various regimes (directed vs. undirected networks, neutral vs. strong selection, Birth-death vs. death-Birth updating) and highlight some outstanding open questions.

Alexandru Malekshahian: Many distinct lengths of leaf-to-leaf paths in bounded degree trees

Monday, November 18, 14:00, room A321

How many different distances are we guaranteed to find between leaves in a tree with given maximum degree and number of leaves? Naive intuition suggests that the number of such distances is minimized for the balanced regular tree. I will prove this, and discuss a related bound on how many of these leaf-to-leaf distances we can find that are 'small'. This addresses two conjectures of Narins, Pokrovskiy and Szabo.

Joint work with Francesco di Braccio and Kyriakos Katsamaktsis.

Veronika Eclerová: Oscillations All Around Us: Exploring Synchronization in Complex Systems

Monday, November 25, 14:00, room A321

Synchronization is a fundamental phenomenon shaping dynamics in fields as varied as neuroscience, epidemiology, ecology, and physics. This talk introduces the work of our Nonlinear Dynamics team, which currently focuses on understanding oscillatory behaviors through the mathematical framework of dynamical systems. By exploring bifurcations of limit cycles and dynamics on invariant tori, we analyze transitions that drive complex behaviors in driven and coupled systems. Through these mathematical insights, we highlight applications across disciplines, demonstrating the universal relevance of oscillatory dynamics and the collaborative efforts behind our research.

Joint work with Lenka Přibylová.

Ander Lamaison: Palettes determine uniform Turán density

Monday, December 9, 14:00, room A321

We study Turán problems for hypergraphs with an additional uniformity condition on the edge distribution. This kind of Turán problems was introduced by Erdős and Sós in the 1980s but it took more than 30 years until the first non-trivial exact results were obtained. Central to the study of the uniform Turán density of hypergraphs are palette constructions, which were implicitly introduced by Rödl in the 1980s. We prove that palette constructions always yield tight lower bounds, unconditionally confirming present empirical evidence. This results in new and simpler approaches to determining uniform Turán densities, which completely bypass the use of the hypergraph regularity method.

Richard Mayr: 2-player Stochastic Reachability Games: Strategy Complexity and Computational Complexity

Monday, December 16, 14:00, room C325

The reachability objective is arguably one of the most basic objectives in graph games: A play satisfies the objective iff it ever visits a given target state. The opposing players, Maximizer and Minimizer, aim to maximize (resp. minimize) the probability of visiting the target state. We consider both concurrent (aka simultaneous move) and turn-based (aka alternating move) 2-player stochastic games, both on finite game graphs and on countably infinite game graphs. We give an overview about the strategy complexity, i.e., how much memory is required for epsilon-optimal (resp. optimal) Maximizer and Minimizer strategies. For finite game graphs, we also discuss the computational complexity of computing the value of the game.

Links:

• Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke: Strategy Complexity of Reachability in Countable Stochastic 2-Player Games,, Dynamic Games and Applications. 2024, https://doi.org/10.1007/s13235-024-00575-6