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 C417 in the building of the Faculty of Informatics on a (roughly) weekly schedule.
Spring 2024 – schedule overview
February 19 | Liana Khazaliya (TU Vienna) | Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth |
March 4 | Martin Dzúrik (Masaryk University) | Combinatorial Spectra of Graphs |
April 8 | Marek Filakovský (Masaryk University) | Topological methods for promised homomorphisms - Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs |
April 15 | Samuel Braunfeld (Charles University) | Some interactions between model theory and structural graph theory |
Upcoming speakers
April 22 | Igor Balla (Masaryk University) | TBA |
May 6 | Kaushik Mallik (ISTA) | |
June 3 | Alexandru Malekshahian (King's College London) | |
June 10 | Felix Schröder (Charles University) |
Liana Khazaliya (TU Vienna): Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Monday, February 19, 14:00, room C417
Upward Planarity Testing and Orthogonal Planarity Testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth [Orthogonal: GD'19; Upward: SoCG'22]. In this talk, I will show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known n^{O(tw)}-time algorithms cannot be improved to run in time n^{o(tw)} unless the Exponential Time Hypothesis fails.
Joint work with Bart M. P. Jansen, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, and Kirill Simonov
Martin Dzúrik (Masaryk University): Combinatorial Spectra of Graphs
Monday, March 4, 14:00, room C417
Combinatorial spectra of graphs is a generalization of H-Hamiltonian spectra. The main motivation was to made from H-Hamiltonian spectra an operation and develop some algebra in this field. An improved version of this operation form a commutative monoid. The most important thing is that most of the basic concepts of graph theory, such as maximum pairing, vertex and edge connectivity and coloring, Ramsey numbers, isomorphisms and regularity, can be expressed in the language of this operation.
Arxiv preprint avalilable here
Marek Filakovský (Masaryk University): Topological methods for promised homomorphisms - Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
Monday, April 8, 14:00, room C417
A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours [1,...,k] such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).
joint work with Nakajima, Opršal, Tasinato and Wagner
Samuel Braunfeld (Charles University): Some interactions between model theory and structural graph theory
Monday, April 15, 14:00, room C417
We will discuss how model-theoretic concepts concerned with separating tame from wild behavior in classes of infinite structures and with developing a structure theory for the tame classes can be applied to classes of finite structures, interacting with programs in structural graph theory. In particular, these concepts have been behind significant recent progress in determining when the general algorithmic problem of first-order model checking is (fixed-parameter) tractable.
Past terms
Spring 2021: Special Seminar – part of Round the World Relay in Combinatorics, where a number of seminars and groups around the world were getting together. Each site hosted a talk, and everyone was welcome.
Fall 2020: ITI Online Seminar – a one-semester online venue for presenting current research in discrete mathematics and theoretical computer science in the Czech Republic.