Approximations of treewidth and other graph parameters
ToT speaker: Hans L. Bodlaender
Motivated from applications from graph algorithms and from sparse matrix factorization, in 1991, we (Bodlaender, Gilbert, Hafsteinsson and Kloks) introduced approximation algorithms for four different graph parameters, including treewidth and pathwidth. In this talk, the main ideas of these algorithms will be sketched, together with a discussion of the connections with sparse matrix factorization, and a historic overview of the further developments of approximations of these parameters.
Approximate Shortest Paths and Distance Oracles
Invited speaker: Shiri Chechik
Computing shortest paths is one of the most fundamental graph problems. While classical shortest paths algorithms like Dijkstra's algorithm provide efficient solutions, they fall short when dealing with large graphs, e.g., continent-sized road networks, necessitating faster alternatives. Sublinear-time queries can be achieved through preprocessing, leading to the concept of distance oracles – data structures facilitating fast retrieval of distance estimates for any pair of nodes. Designing distance oracles involves balancing various parameters: construction time, data structure size, query time, and the accuracy of the estimated distance. Not only are distance oracles important structures by their own right with both practical and theoretical interest, but they also have strong ties to numerous other problems in algorithms, such as spanners, compact routing schemes and low-stretch spanning trees. A significant challenge arises from the dynamic nature of real-world networks, subject to both permanent changes (e.g., road additions) and temporary disruptions (e.g., closures or blockages). Dynamic settings capture permanent alterations, while fault tolerance settings address temporary changes. In this talk, I will explore key findings on approximate shortest paths and distance oracles across static, dynamic, and fault-tolerant settings.
Graph classes and logic
Invited speaker: Michał Pilipczuk
Structural graph theory offers a wide range of notions that can be used to quantify the structure in graphs, such as various graph parameters, notions of embedding, and decompositions. The central concept here is that of a graph class, which is a set of graphs that share some common structural property of interest. But what if instead of relying on purely combinatorial definitions, we resorted to logic? That is, the idea is to define graph classes by excluding obstructions interpretable in logic, or by postulating the existence of some kind of decompositions definable in logic. During the talk we will both revisit, from this angle, classic results linking treewidth and cliquewidth with logic MSO, as well as survey the recent advances on understanding the combinatorics of monadically stable and monadically dependent graph classes, which correspond to the same questions asked for the First Order logic (FO).
