MPI-INF Logo
Homepage of Dániel Marx

Contact

Firstname Lastname

Dániel Marx

Head of the Parameterized Algorithms & Complexity Group

Max-Planck-Institut für Informatik
Department 1: Algorithms & Complexity
 office: Campus E1 4, Room 304
Saarland Informatics Campus
66123 Saarbrücken
Germany
 email: Get my email address via email
 phone: +49 681 9325 1004
 fax: +49 681 9325 199

News

Postdoc positions are available in algorithms & complexity at Max-Planck-Institut für Informatik, Saarbrücken, Germany, supported by the ERC Consolidator Grant SYSTEMATICGRAPH.


Read more

Research Interests

The main focus of my research is reaching the ultimate limits of algorithmic techniques for solving hard computational problems. I am equally interested in working on problems of algorithm design and in using computational complexity to discover the fundamental limitations of efficient algorithms. A large part of my work uses the framework of parameterized complexity to obtain a more fine-grained understanding of problem complexity. I have worked on a wide range of combinatorial problems coming from algorithmic graph theory, combinatorial optimization, constraint satisfaction problems (CSP), and other areas.

Publications

Selected publications:

  • Closest substring problems with small distances.
    D. Marx. SIAM Journal on Computing, 38(4):1382-1410, 2008. (Conference version in FOCS 2005.)
  • Approximation schemes for Steiner Forest on planar graphs and graphs of bounded treewidth.
    M. Bateni, M. Hajiaghayi. D. Marx. Journal of the ACM, 58(5):21, 2011. (Conference version in STOC 2010.)
  • Tractable hypergraph properties for constraint satisfaction and conjunctive queries.
    D. Marx. Journal of the ACM, 60(6):42, 2013. (Conference version in STOC 2010.)
  • The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable.
    M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), 197-206, 2013.
  • Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs.
    M. Grohe, D. Marx. SIAM Journal on Computing, 44(1):114-159, 2015. (Conference version in STOC 2012.)

Projects

  • ERC Starting Grant PARAMTIGHT:
    "Parameterized complexity and the search for tight complexity results"
  • ERC Consolidator Grant SYSTEMATICGRAPH:
    "Systematic mapping of the complexity landscape of hard algorithmic graph problems"

CV

See full CV here.

Tutorials