ERC Consolidator Grant · 2023
Limits of Structural Tractability
The combination of methods from logic and graph theory has been extremely successful in the design of algorithms, in complexity theory, and other areas of theoretical computer science. A success story exemplifying the power of this approach is the recent development in the algorithmic structure theory of sparse graphs. In this line of research, structural results stemming from Robertson and Seymour’s graph minor theory, and the more recent sparsity theory of Nešetřil and Ossona de Mendez, were com- bined with logical methods in order to obtain a systematic understanding of tractability. An example result in this area states that every graph property definable in first order logic can be…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.