Grants under the SONATA BIS-14 competition are awarded for research projects aimed at establishing a new research team, carried out by persons holding a degree or academic title who obtained a doctoral degree between 5 and 12 years prior to submitting the application.

The funds received in the competition can be used for salaries for the research team, including scholarships for students or doctoral students, the purchase or production of research equipment, and other costs related to the expenses necessary to carry out the research project.

About the project

Since the 1970s, we have known that there are many natural computational problems that we will (probably) never be able to solve efficiently. An example of such a problem is the Largest Independent Set: for a given graph, one needs to find the largest set of pairwise non-adjacent vertices. The simplicity of the problem definition is deceptive: unless something very unexpected happens, we cannot count on fast (or even ‘significantly faster than brute-force’) algorithms that will solve this problem, even approximately. However, such algorithms may exist if we limit the possible input graphs (instances) to a certain family (called a class).

The study of computational problems in special graph classes has been a very active research direction in recent decades. In this and other contexts, there is often a duality between sparse and dense graphs. There are many reasonable definitions of sparse graphs, but in general, classes of sparse graphs are considered to be well understood. They often have strong structural properties that allow, for example, the chromatic number to be bounded. In many cases, these properties can also be exploited algorithmically. Numerous classical computational problems, which are difficult in general, become significantly easier in classes of sparse graphs – i.e. there are fast algorithms for them, at least approximations. On the other hand, dense graphs are considered to be structurally complex. Moreover, from a computational perspective, they often provide us with negative results.

However, it turns out that even among the classes of dense graphs, one can find many highly structured examples. Intuitively, we will be interested in classes of graphs that ‘only pretend to be dense’. More formally, there are classes of (potentially dense) graphs in which some rare structure can still be found, although it is not immediately apparent. In this project, we will investigate how the results obtained for classes of sparse graphs can be generalised to such ‘structurally sparse’ classes. In particular, we are interested in transferring tools from one world to the other.

Moreover, we will also study graph classes that ‘only pretend to be sparse’. More specifically, we will deal with (potentially sparse) graphs with a fixed order on the vertices. The order relation is dense, but still not too complicated. Thanks to the first of these properties, even simple graph families (e.g. associations) are quite rich in an ordered world. Thanks to the second property, we can still count on interesting structural and algorithmic properties.