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

Upcoming speakers

November 04	Marcin Brianski
November 11	Josef Tkadlec
November 18	Alexandru Malekshahian
November 25	Veronika Eclerová

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.