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 lasts until 2016-12-31
Selected recent publications
Peeling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related
Problems. D. Marx, T. Miltzow. To appear in Proceedings of the 32nd International Symposium on Computational Geometry (SOCG 2016).
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.