Overview
The goal of the SYSTEMATICGRAPH project is to put the search for tractable algorithmic graph problems into a systematic and methodological framework: instead of focusing on specific sporadic problems, we intend to obtain a unified algorithmic understanding by mapping the entire complexity landscape of a particular problem domain. A dichotomy theorem is a complete classification result that characterizes the complexity of each member of a family of problems: it identifies all the cases that admit efficient algorithms and proves that all the other cases are computationally hard. The project will demonstrate that such a complete classification is feasible for a wide range of graph problems coming from areas such as finding patterns, routing, and survivable network design, and novel algorithmic results and new levels of algorithmic understanding can be achieved even for classic and well-studied problems.
The project is funded by an ERC Consolidator Grant from the European Research Council under the European Commission's
Horizon 2020 Framework Programme.