BOBR is a research project in theoretical computer science focused on investigation of applications of decomposition methods for problems on discrete structures, mostly for graphs, from the point of view of graph theory, algorithmics, and finite model theory. Specific directions are:
model-theoretically motivated structure theory for dense graphs, extending the field of Sparsity to the dense setting;
theory of parameterized dynamic data structures;
algorithms for topological and geometric problems, with particular focus on parameterized and approximation algorithms;
combinatorial and algorithmic properties of graph classes defined through forbidden induced subgraphs.
The project started on April 1st, 2021, and will conclude on March 31st, 2026. It is hosted at the Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw.
The project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, Grant Agreement No 948057.