SONATA BIS

Key information:

Project title: From dense graphs to sparse ones and back again
Duration: 07.04.2025 - 06.04.2030
Funding: National Science Centre (NCN), SONATA BIS 14, 2024/54/E/ST6/00094

Team:

  1. Paweł Rzążewski, principal investigator
  2. Paweł Rafał Bieliński, PhD student
  3. ... 
  4. ...

Main objectives:


The notion of sparse graphs has been one of the central concepts in structural and algorithmic graph theory in past few decades. There are many reasonable definitions of "sparse," but in general classes of sparse graphs are considered to be well-understood. They often admit some strong structural properties which allow us to, e.g., bound the chromatic number. In many cases these properties can also be exploited algorithmically.

However, it turns out that even among classes of dense graphs we can find many examples that are well-structured. Intuitively speaking, we will be interested in classes of graphs that "only pretend to be dense." Slightly more formally, there are classes of (possibly dense) graphs that admit some sparse underlying structure. There are many ways of defining such structurally sparse classes, e.g., via discrete geometry, as intersection graphs of geometric objects, using matroid theory etc.
In this project we will be mostly interested in classes defined by:
* forbidding certain patterns, especially as induced minors,
* bounding certain width parameters, especially related to structured tree-like decompositions.

Moreover, we are also going to look at classes of graphs that "only pretend to be sparse." More specifically, we are going to investigate (possibly sparse) graphs with a total order on vertices. The total order relation is dense, but still not very complicated. Due to the first property, even very simple families of graphs (say, matchings) have  quite rich structure in the ordered world. Due to the second property, we might still hope for some interesting structural and algorithmic results.

We aim to look at ordered graphs from two perspectives. First, we want to conduct a systematic study of structural and algorithmic properties of classes of ordered graphs defined by forbidding certain (ordered) induced subgraphs. Such investigations in the unordered setting are in the core of the modern structural and algorithmic graph theory.

Second, we want to investigate order-preserving homomorphisms of ordered graphs, and explore their combinatorial and computational properties. We attempt to build a theory similar to the one of homomorphisms of unordered graphs.

Summing up, the proposed project has the following high-level goals.
Goal 1. Explore structural and algorithmic properties of classes of graphs defined by forbidden induced minor or by bounding width parameters related to structured tree-like decompositions.
Goal 2a. Initiate and conduct a systematic study on structural and algorithmic properties of ordered graph classes defined by forbidding certain induced subgraphs.
Goal 2b. Initiate the study of the theory of order-preserving homomorphisms of ordered graphs.

Selected papers:

  1. É. Bonnet, P. Rzążewski, An 11/6 Approximation Algorithm for Vertex Cover on String Graphs, SoCG 2025 Proc., LIPIcs 332, pp. 24:1-24:15, 2025
  2. M. Čertík, A.E. Feldmann, J. Nešetřil, P. Rzążewski, On Computational Aspects of Ordered Matching Problems, ICTAC 2025 Proc., LNCS 16237, pp. 459-467, 2025
  3. P. Rzążewski, B. Walczak, Polynomial-time recognition and maximum independent set in Burling graphs, WG 2025 Proc., LNCS 16124, pp. 445-460, 2026
  4. T. Abrishami, M. Briański, J. Davies, X. Du, J. Masaříková, P. Rzążewski, B. Walczak, Burling graphs in graphs with large chromatic number, SODA 2026 Proc., pp. 3978-3998, 2026
  5. M. Čertík, A.E. Feldmann, J. Nešetřil, P. Rzążewski, Complexity Aspects of Homomorphisms of Ordered Graphs, SOFSEM 2026 Proc., LNCS 16448, pp. 416-431, 2026
  6. P. Rzążewski, M. Piecyk, List coloring ordered graphs with forbidden induced subgraphs, STACS 2026 Proc., LIPIcs 364, pp. 74:1-74:17, 2026
  7. M. Čertík, A.E. Feldmann, J. Nešetřil, P. Rzążewski, On Computational Aspects of Cores of Ordered Graphs, RAMICS 2026 Proc., LNCS 16526, pp. 114-132, 2026
  8. É. Bonnet, J. Czyżewska, T. Masařík, M. Pilipczuk, P. Rzążewski, QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes, SWAT 2026 Proc., LIPIcs 370, pp. 9:1-9:14, 2026
  9. P.T. de Lima, A. Nikabadi, P. Rzążewski, Hitting all longest paths in H-free graphs and H-graphs, LATIN 2026 Proc., to appear
  10. P. R. Bieliński, M. Piecyk, P. Rzążewski, Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs, ESA 2026 Proc., LIPIcs 388, pp. 30:1-30:15, 2026
  11. V. Blažej, J.P. Gollin, T. Hons, T. Masařík, M. Milanič, P. Rzążewski, O. Suchý, A. Wesolek, Tree-independence number of P5-free graphs with no large bicliques, ESA 2026 Proc., LIPIcs 388, pp. 77:1-77:17, 2026
  12. N. Alon, M. Milanič, P. Rzążewski, Induced matching treewidth and tree-independence number, revisited, Electronic Journal of Combinatorics 33(3), P3.70, 2026
  13. J. Davies, P. Rzążewski, J. Spalding-Jamieson, B. Walczak, Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs, SODA 2027 Proc., to appear