SYSTEMATICGRAPH SIGNED
Systematic mapping of the complexity landscape of hard algorithmic graph problems
Total Cost €
0EC-Contrib. €
0Partnership
0Views
0SYSTEMATICGRAPH 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.
Project "SYSTEMATICGRAPH" data sheet
The following table provides information about the project.
| Coordinator |
MAX-PLANCK-GESELLSCHAFT ZUR FORDERUNG DER WISSENSCHAFTEN EV
Organization address contact info |
| 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 |
Partnership
Take a look of project's partnership.
| # | ||||
|---|---|---|---|---|
| 1 | MAX-PLANCK-GESELLSCHAFT ZUR FORDERUNG DER WISSENSCHAFTEN EV | DE (MUENCHEN) | coordinator | 1˙177˙000.00 |
| 2 | MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATOINTEZET | HU (BUDAPEST) | participant | 355˙000.00 |
Map
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.
Publications
| year | authors and title | journal | last update |
|---|---|---|---|
| 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 (fabio@fabiodisconzi.com) 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.