Matthias Mnich

Contact Info

Max Planck Institut für Informatik
Cluster of Excellence Multimodal Computing and Interaction
Campus E1-7
Room 3.02
66123 Saarbrücken
Germany

Email: mmnich AT mpi-inf.mpg.de
Phone: +49 (681) 302 70789
Fax: +49 (681) 302 70155

Research Interests

exact algorithms for NP-hard problems,
parameterized complexity,
phylogenetic networks.

Teaching
List Of Publications

    To appear
  • Serge Gaspers and Matthias Mnich: Feedback Vertex Sets in Tournaments. To appear in Journal of Graph Theory.


    • 2012
  • Matthias Mnich, Rico Zenklusen: Bisections Parameterized Above Tight Lower Bound. Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG '12), to appear.
  • Robert Crowston, Mark Jones, Matthias Mnich: Max-Cut Parameterized Above the Edwards-Erdős-Bound.
    Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '12), to appear. preprint
  • Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo: Every Ternary Permutation Constraint Satisfaction Problem Parameterized Above Average Has a Kernel with a Quadratic Number of Variables. Journal of Computer and System Sciences 78(1), pp. 151-163.
    original publication


    • 2011
  • Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger. Domination When the Stars Are Out. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '11) 6755, pp. 462-473.
    original publication
  • Daniel Lokshtanov, Matthias Mnich, Saket Saurabh Planar k-Path in Subexponential Time and Polynomial Space. In Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG '11), Lecture Notes in Computer Science 6986, pp. 262-270.
    original publication
  • Matthias Mnich: Allemaal op een rijtje (Philips Prize Lecture 2010). Nieuw Archief voor Wiskunde 5(12), pp. 25-28.
  • Matthias Mnich: Book Review Exact Exponential Algorithms. Operations Research Letters 39(3), pp. 229-230.
    original publication


    • 2010
  • Matthias Mnich: Algorithms in Moderately Exponential Time. PhD thesis, Eindhoven University of Technology, Eindhoven, The Netherlands, 216 p.
    original publication
  • Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo: All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Polynomial Kernels. In Proceedings of the 18th European Symposium on Algorithms (ESA '10), Lecture Notes in Computer Science 6346, pp. 326-337.
    original publication
  • Serge Gaspers and Matthias Mnich: Feedback Vertex Sets in Tournaments. In Proceedings of the 18th European Symposium on Algorithms (ESA '10), Lecture Notes in Computer Science 6346, pp. 267-277.
    original publication
  • Ross Kang, Matthias Mnich, Tobias Müller: Induced Matchings in Subcubic Plane Graphs. In Proceedings of the 18th European Symposium on Algorithms (ESA '10), Lecture Notes in Computer Science 6347, pp. 112-122.
    original publication
  • Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, Saket Saurabh: Ranking and Drawing in Subexponential Time. In Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA '10), Lecture Notes in Computer Science 6460, pp. 337-348.
    original publication
  • Sylvain Guillemot and Matthias Mnich: Kernel and Fast Algorithm for Dense Triplet Inconsistency. In Proceedings of 7th Annual Conference Theory and Applications of Models of Computation (TAMC '10), Lecture Notes in Computer Sciene 6108, pp. 247-257.
    original publication
  • Daniel Lokshtanov, Matthias Mnich, Saket Saurah: Linear Kernel for Planar Connected Dominating Set. Theoretical Computer Science 412(23), pp. 2536-2543
    original publication
  • Gregory Gutin, Eun Jung Kim, Matthias Mnich, Anders Yeo: Betweenness Parameterized Above Tight Lower Bound. Journal of Computer and System Sciences 76(8), pp. 872-878.
    original publication
  • Leo van Iersel, Steven Kelk, Matthias Mnich: Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks. Journal of Bioinformatics and Computational Biology, 7(4):597-623, Imperial College Press 2009.
    original publication


    • 2009
  • Michael Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances Rosamond, Saket Saurabh: The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number. Theory Of Computing Systems, 45(4):822-848, Springer 2009.
    original publication
  • Daniel Lokshtanov, Matthias Mnich, Saket Saurabh: Linear Kernel for Planar Connected Dominating Set. In Proceedings of 6th Annual Conference Theory and Applications of Models of Computation (TAMC '09), Changsha, China. February 2009. Volume 5532 of Lecture Notes in Computer Science, pp. 281-290, Springer 2009.
    original publication


    • 2006
  • Matthias Mnich: Correlated Equilibria in Succinctly Representable Games. MSc thesis, The London School of Economics and Political Science, London, United Kingdom, August 2006.
Mathematics & Theatre

Theatre and the Arts have always fascinated me. I was involved in a Hungarian-German production The Mule, a play involving various nice mathematical bits. The production is supported by the German Federal Ministry of Education and Research, within the Year of Mathematics. The production featured at the Höhenrausch Festival in Rostock, performed in Frankfurt at the NAXOS-Halle and will soon be shown in Mainz. For exact dates and more information see here.