Systematic mapping of the complexity landscape of hard algorithmic graph problems
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.
- Principal investigator: Dániel Marx
- The project started on 2017-07-01
and lasts until 2022-06-30