Project information
New and traditional structural graph measures for logic and algorithms

Exploring possible approaches to solving generally intractable algorithmic problems shows the necessity of studying the basic combinatorial structure of tractable and intractable instances, which commonly means investigating suitabl structural measures or parameters of the instances. We propose to explore this direction by combining methods and new tools from structural combinatorics and graph logic, taking advantage of the combinatorial/logical duality of many such graph parameters.
Namely in the above areas we plan to investigate; (a) properties and efficient parameterized
computation or approximation of some of the computationally hard parameters; (b) in particular, detailed properties of the hereditary product structure measure and the related new H-clique width parameter, which we have just come with at MFCS'24; (c) the question of FO definability (specifically transducibility) and non-definability of certain graphs in other graph classes; and (d) new algorithmic metatheorems and hardness results using the investigated parameters and definitions of graph classes.