Opendata, web and dolomites


Cuts and decompositions: algorithms and combinatorial properties

Total Cost €


EC-Contrib. €






Project "CUTACOMBS" data sheet

The following table provides information about the project.


Organization address
postcode: 00 927

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 Poland [PL]
 Total cost 1˙228˙250 €
 EC max contribution 1˙228˙250 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2016-STG
 Funding Scheme ERC-STG
 Starting year 2017
 Duration (year-month-day) from 2017-03-01   to  2022-02-28


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    UNIWERSYTET WARSZAWSKI PL (WARSZAWA) coordinator 1˙228˙250.00


 Project objective

In this proposal we plan to extend mathematical foundations of algorithms for various variants of the minimum cut problem within theoretical computer science. Recent advances in understanding the structure of small cuts and tractability of cut problems resulted in a mature algorithmic toolbox for undirected graphs under the paradigm of parameterized complexity. In this position, we now aim at a full understanding of the tractability of cut problems in the more challenging case of directed graphs, and see opportunities to apply the aforementioned successful structural approach to advance on major open problems in other paradigms in theoretical computer science. The specific goals of the project are grouped in the following three themes.

Directed graphs. Chart the parameterized complexity of graph separation problems in directed graphs and provide a fixed-parameter tractability toolbox, equally deep as the one in undirected graphs. Provide tractability foundations for routing problems in directed graphs, such as the disjoint paths problem with symmetric demands.

Planar graphs. Resolve main open problems with respect to network design and graph separation problems in planar graphs under the following three paradigms: parameterized complexity, approximation schemes, and cut/flow/distance sparsifiers. Recently discovered connections uncover significant potential in synergy between these three algorithmic approaches.

Tree decompositions. Show improved tractability of graph isomorphism testing in sparse graph classes. Combine the algorithmic toolbox of parameterized complexity with the theory of minimal triangulations to advance our knowledge in structural graph theory, both pure (focused on the Erdos-Hajnal conjecture) and algorithmic (focused on the tractability of Maximum Independent Set and 3-Coloring).


year authors and title journal last update
List of publications.
2019 Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk
Improved Bounds for the Excluded-Minor Approximation of Treedepth
published pages: 34:1-34:13, ISSN: , DOI: 10.4230/lipics.esa.2019.34
27th Annual European Symposium on Algorithms (ESA 2019) 2020-04-24
2019 Chen, Jiehua; Hermelin, Danny; Sorge, Manuel
On Computing Centroids According to the $p$-Norms of Hamming Distance Vectors
published pages: 28:1--28:16, ISSN: , DOI: 10.4230/lipics.esa.2019.28
27th Annual European Symposium on Algorithms (ESA \'19) 2020-04-24
2019 Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge
Packing Directed Circuits Quarter-Integrally
published pages: 72:1-72:13, ISSN: , DOI: 10.4230/lipics.esa.2019.72
27th Annual European Symposium on Algorithms (ESA 2019) 2020-04-24
2017 Shaohua Li, Qilong Feng, Xiangzhong Meng, Jianxin Wang
An Improved FPT Algorithm for the Flip Distance Problem
published pages: , ISSN: , DOI: 10.4230/lipics.mfcs.2017.65
42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 2020-04-24
2019 Masařík, Tomáš
Flexibility of planar graphs without 4-cycles
published pages: 935-940, ISSN: , DOI:
Acta Mathematica Universitatis Comenianae 88(3) 2020-04-24
2018 Kratsch, Stefan; Li, Shaohua; Marx, Dániel; Pilipczuk, Marcin; Wahlström, Magnus
Multi-budgeted directed cuts
published pages: 18:1-18:14, ISSN: , DOI: 10.4230/lipics.ipec.2018.18
13th International Symposium on Parameterized and Exact Computation (IPEC 2018) 2020-04-24
2019 Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz
Algorithmic Properties of Sparse Digraphs
published pages: 46:1-46:20, ISSN: , DOI: 10.4230/lipics.stacs.2019.46
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 2020-04-24
2019 Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
published pages: , ISSN: , DOI:
60th Annual IEEE Symposium on Foundations of Computer Science 2020-04-24
2019 Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk
Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs
published pages: 33:1-33:14, ISSN: , DOI: 10.4230/lipics.esa.2019.33
27th Annual European Symposium on Algorithms (ESA 2019) 2020-04-24
2019 William S. Evans, Pawel Rzazewski, Noushin Saeedi, Chan-Su Shin, Alexander Wolff
Representing Graphs and Hypergraphs by Touching Polygons in 3D
published pages: , ISSN: , DOI:
Graph Drawing 2019 2020-04-24
2020 Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
published pages: , ISSN: , DOI:
ACM-SIAM Symposium on Discrete Algorithms (SODA20) 2020-04-24
2018 Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał
On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs
published pages: 474-484, ISSN: , DOI: 10.1109/FOCS.2018.00052
2018 IEEE 59th Annual Symposium on Foundations of Computer Science 2020-04-24
2018 Iyad A. Kanj, Christian Komusiewicz, Manuel Sorge, Erik Jan van Leeuwen
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
published pages: 51:1-51:14, ISSN: , DOI: 10.4230/LIPIcs.ESA.2018.51
Proceedings of the 26th Annual European Symposium on Algorithms (ESA \'18) 2020-04-24
2018 Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
Assessing the Computational Complexity of Multi-Layer Subgraph Detection
published pages: , ISSN: 2050-1242, DOI:
Network Science 2020-04-24
2018 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$$Pt-Free and Broom-Free Graphs
published pages: , ISSN: 0178-4617, DOI: 10.1007/s00453-018-0479-5
Algorithmica 2020-04-24
2018 Anita Liebenau, Marcin Pilipczuk, Paul Seymour, Sophie Spirkl
Caterpillars in Erdős–Hajnal
published pages: , ISSN: 0095-8956, DOI: 10.1016/j.jctb.2018.09.002
Journal of Combinatorial Theory, Series B 2020-04-24
2018 Jiehua Chen, Ondrej Suchy, Hendrik Molter, Manuel Sorge
Cluster Editing in Multi-Layer and Temporal Graphs
published pages: , ISSN: , DOI:
Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\'18) 2020-04-24
2018 Bonamy, Marthe; Kowalik, Łukasz; Nederlof, Jesper; Pilipczuk, Michał; Socała, Arkadiusz; Wrochna, Marcin
On Directed Feedback Vertex Set parameterized by treewidth
published pages: 65-78, ISSN: , DOI: 10.1007/978-3-030-00256-5_6
Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, LNCS 11159 2020-04-24
2018 Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz
An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs
published pages: , ISSN: 0178-4617, DOI: 10.1007/s00453-018-0504-8
Algorithmica 2020-04-24
2018 Li, Shaohua; Pilipczuk, Marcin
An improved FPT algorithm for Independent Feedback Vertex Set
published pages: , ISSN: , DOI: 10.1007/978-3-030-00256-5_28
Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, LNCS 111159 2020-04-24

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "CUTACOMBS" 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 "CUTACOMBS" are provided by the European Opendata Portal: CORDIS opendata.

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

EffectiveTG (2018)

Effective Methods in Tame Geometry and Applications in Arithmetic and Dynamics

Read More  

MuFLOART (2018)

Microbiological fluorescence observatory for antibiotic resistance tracking

Read More  

TransTempoFold (2019)

A need for speed: mechanisms to coordinate protein synthesis and folding in metazoans

Read More