Opendata, web and dolomites


Systematic mapping of the complexity landscape of hard algorithmic graph problems

Total Cost €


EC-Contrib. €






 SYSTEMATICGRAPH project word cloud

Explore the words cloud of the SYSTEMATICGRAPH project. It provides you a very rough idea of what is the project "SYSTEMATICGRAPH" about.

solutions    natural    techniques    complexity    csps    complete    hard    hence    networks    sporadic    classifying    routing    satisfaction    parameterized    unification    appear    tools    network    successful    full    admit    domain    time    efficient    mapping    generality    discovered    computationally    similarly    unified    approximability    context    landscapes    algorithms    systematic    relevance    classification    put    discovering    abstract    comparatively    survivable    constraint    investigation    variants    computer    methodological    formal    reveal    circuits    waiting    classifications    appearing    objects    usually    algorithmic    models    description    classic    restricted    feasible    coming    road    communication    intend    instead    graph    dichotomy    practical    obtain    levels    landscape    enormously    patterns    necessarily    theoretical    science    deserves    setting    relations    completely    special    framework    graphs    sufficiently    tractable    entire    search    little   

Project "SYSTEMATICGRAPH" data sheet

The following table provides information about the project.


Organization address
postcode: 80539
website: n.a.

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Germany [DE]
 Total cost 1˙532˙000 €
 EC max contribution 1˙532˙000 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2016-COG
 Funding Scheme ERC-COG
 Starting year 2017
 Duration (year-month-day) from 2017-07-01   to  2022-06-30


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 


 Project objective

Graph-theoretical models are natural tools for the description of road networks, circuits, communication networks, and abstract relations between objects, hence algorithmic graph problems appear in a wide range of computer science applications. As most of these problems are computationally hard in their full generality, research in graph algorithms, approximability, and parameterized complexity usually aims at identifying restricted variants and special cases, which are at the same time sufficiently general to be of practical relevance and sufficiently restricted to admit efficient algorithmic solutions. The goal of the 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.

Completely classifying the complexity of each and every algorithmic problem appearing in a given formal framework would necessarily reveal every possible algorithmic insight relevant to the formal setting, with the potential of discovering novel algorithmic techniques of practical interest. This approach has been enormously successful in the complexity classifications of Constraint Satisfaction Problems (CSPs), but comparatively very little work has been done in the context of graphs. The systematic investigation of hard algorithmic graph problems deserves the same level of attention as the dichotomy program of CSPs, and graph problems have similarly rich complexity landscapes and unification results waiting to be discovered. 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.


year authors and title journal last update
List of publications.
2019 Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich
Routing with congestion in acyclic digraphs
published pages: 105836, ISSN: 0020-0190, DOI: 10.1016/j.ipl.2019.105836
Information Processing Letters 151 2020-04-08
2018 Radu Curticapean
Block interpolation: A framework for tight exponential-time counting complexity
published pages: 265-280, ISSN: 0890-5401, DOI: 10.1016/j.ic.2018.02.008
Information and Computation 261 2020-04-08
2019 Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms
published pages: 3890-3935, ISSN: 0178-4617, DOI: 10.1007/s00453-019-00579-4
Algorithmica 81/10 2020-04-08
2018 Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Paweł Rzążewski
Fine-grained complexity of coloring unit disks and balls
published pages: 47-80, ISSN: 1920-180X, DOI: 10.20382/jocg.v9i2a4
Journal of Computational Geometry 9(2) 2020-04-08
2018 Daniel Lokshtanov, Dániel Marx, Saket Saurabh
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
published pages: 1-30, ISSN: 1549-6325, DOI: 10.1145/3170442
ACM Transactions on Algorithms 14/2 2020-04-08
2018 Daniel Lokshtanov, Dániel Marx, Saket Saurabh
Slightly Superexponential Parameterized Problems
published pages: 675-702, ISSN: 0097-5397, DOI: 10.1137/16m1104834
SIAM Journal on Computing 47/3 2020-04-08
2019 Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen
Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs
published pages: 421-438, ISSN: 0178-4617, DOI: 10.1007/s00453-018-0479-5
Algorithmica 81/2 2020-04-08

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "SYSTEMATICGRAPH" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "SYSTEMATICGRAPH" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

METAPoF (2019)

Metaphor as the Purpose of the Firm

Read More  

POLAR (2020)

Polarization and its discontents: does rising economic inequality undermine the foundations of liberal societies?

Read More  

MetTraC (2019)

Biocatalytic Methyltransferase Cascades

Read More