ERC
Project PARAMTIGHT Parameterized complexity and
the search for tight complexity results
Overview
The PARAMTIGHT project uses the framework of parameterized
complexity to achieve optimal algorithmic results for hard
combinatorial problems. The goal is to obtain matching algorithmic and complexity results describing, for example, the precise way how the running time has to depend on various parameters of the problem instance.
The project is funded by an ERC Starting Grant from the European Research Council under the European Commission's Seventh Framework Programme (FP7/2007-2013).
The project started 2012-01-01 and finished 2017-06-30.
Selected recent publications
Homomorphisms are a good basis for counting small subgraphs. R. Curticapean, H. Dell, D. Marx.
Symposium on Theory of Computing (STOC 2017), 210-223, 2017.
Fine-Grained Complexity of Coloring Unit Disks and Balls. Cs. Biró,E. Bonnet, D. Marx, T. Miltzow, P. Rzazewski:
Symposium on Computational Geometry
(SOCG 2017), 18:1-18:1, 2017.
Peeling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related
Problems. D. Marx, T. Miltzow. Symposium on Computational Geometry (SOCG
2016), 52:1-52:16, 2017.
Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. R. Curticapean, D. Marx. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), 1650-1669, 2016.
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi
Diagrams. D. Marx, M. Pilipczuk. In Proceedings of the 23rd European Symposium on Algorithms (ESA 2015), 865-877, 2015.
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing
kernels. B. M. P. Jansen, D. Marx. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 616-629, 2015.
The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric
problems. D. Marx, A. Sidiropoulos. In Proceedings of the 30th International Symposium on Computational Geometry (SOCG 2014), 67-76, 2014.
Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover
Number Counts. D. Marx, R. Curticapean.
In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014), 130-139, 2014.