Info > SONATA BIS
SONATA BIS
Key information:
Project title: From dense graphs to sparse ones and back again (or Hobbit for short)
Duration: 07.04.2025 - 06.04.2030
Funding: National Science Centre (NCN)
Team:
- Paweł Rzążewski, principal investigator
- Paweł Rafał Bieliński, PhD student
- ...
- ...
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.
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:
- E. 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
- M. Čertik, 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
- P. Rzążewski, B. Walczak, Polynomial-time recognition and maximum independent set in Burling graphs, WG 2025 Proc., LNCS 16124, pp. 445-460, 2026
- 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
- 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
- P. Rzążewski, M. Piecyk, List coloring ordered graphs with forbidden induced subgraphs, STACS 2026 Proc., LIPIcs 364, pp. 74:1 - 74:17, 2026
- P.T. Lima, M. Milanic, P. Mursic, K. Okrasa, P. Rzążewski, K. Storgel, Tree decompositions meet induced matchings: beyond Max Weight Independent Set, JCSS (available online), 2026
- D. Lokshtanov, P. Rzążewski, S. Saurabh, R. Sharma, M. Zehavi, Maximum Partial List H-Coloring on P5-free graphs in polynomial time, Journal of Graph Theory (available online), 2026
- E. Bonnet, J. Czyżewska, T. Masarik, 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
- P. R. Bieliński, M. Piecyk, P. Rzążewski, Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs, ESA 2026 Proc., LIPIcs 288, pp: 30:1 - 30:15, 2026
- V. Blazej, J.P. Gollin, T. Hons, T. Masarik, M. Milanic, P. Rzążewski, O. Suchy, A. Wesolek, Tree-independence number of P5-free graphs with no large bicliques, ESA 2026 Proc., LIPIcs 288, pp: 77:1 - 77:17, 2026