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 was hosted by the Institute for Computer Science and Control of the Hungarian Academy of Sciences (MTA SZTAKI)
• Principal investigator: Dániel Marx
• The project started 2012-01-01 and finished 2017-06-30.

Selected 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.

Team

Group members:

• Dániel Marx, principal investigator
• Gábor Bacsó, senior researerch (2015-2017)
• Édouard Bonnet, postdoc (2015-2017)
• Nick Brettell, postdoc (2015-2016),
• Yixin Cao, postdoc (2012-2014)
• Lin Chen, postdoc (2016)
• Radu Curticapean, postdoc (2015-2017)
• László Egri, postdoc (2012-2013)
• Andreas Feldmann, postdoc (2015-2016)
• Sylvain Guillemot, postdoc (2012-2014)
• O-joung Kwon, postdoc (2015-2016)
• Till Miltzow, postdoc (2015-2016)
• Valia Mitsou, postdoc (2015-2016)
• Sandeep R. B., (2016-2017)
• Pawel Rzazewski, postdoc (2016-2017)