CUTACOMBS SIGNED
Cuts and decompositions: algorithms and combinatorial properties
Total Cost €
0EC-Contrib. €
0Partnership
0Views
0CUTACOMBS project word cloud
Explore the words cloud of the CUTACOMBS project. It provides you a very rough idea of what is the project "CUTACOMBS" about.
Project "CUTACOMBS" data sheet
The following table provides information about the project.
| Coordinator |
UNIWERSYTET WARSZAWSKI
Organization address contact info |
| 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 |
Partnership
Take a look of project's partnership.
| # | ||||
|---|---|---|---|---|
| 1 | UNIWERSYTET WARSZAWSKI | PL (WARSZAWA) | coordinator | 1˙228˙250.00 |
Map
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).
Publications
| year | authors and title | journal | last update |
|---|---|---|---|
| 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 (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 "CUTACOMBS" are provided by the European Opendata Portal: CORDIS opendata.