Matthias Mnich

Cluster of Excellence Multimodal Computing and Interaction
Campus E1-7
Room 3.02
66123 Saarbrücken
Germany

Email: mmnich AT mmci.uni-saarland.de
Phone: +49 (681) 302 70789
Fax: +49 (681) 302 70155

Max Planck Institut für Informatik
Campus E1-4
Room 3.28
66123 Saarbrücken
Germany

Email: mmnich AT mpi-inf.mpg.de
Phone: +49 (681) 9325 128

Research Interests

combinatorial optimization,
exact algorithms for NP-hard problems,
parameterized complexity,
discrete mathematics,
phylogenetic networks.

Teaching
List Of Publications



    2013
  • Sylvain Guillemot, Matthias Mnich: Kernel and Fast Algorithm for Dense Triplet Inconsistency. Theoretical Computer Science, to appear.
    original publication
  • Serge Gaspers, Matthias Mnich: Feedback Vertex Sets in Tournaments. Journal of Graph Theory 72(1), pp. 72-89.
    original publication


    • 2012
  • Ross Kang, Matthias Mnich, Tobias Müller: Induced Matchings in Subcubic Planar Graphs. SIAM Journal on Discrete Mathematics 26(3), pp. 1383-1411.
    original publication
  • Matthias Mnich, Geevarghese Philip, Saket Saurabh, Ondřey Suchý: Beyond Max-Cut: λ-Extendible Properties Parameterized Above Poljak-Turzík Bound. Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS '12), Leibniz International Proceedings in Informatics 18, pp. 412--423.
    original publication
  • Renè van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller: Interval Scheduling and Colorful Independent Sets. Proceedings of the International Symposium on Algorithms and Computation (ISAAC '12), Lecture Notes in Computer Science 7676, pp. 247-256.
    original publication
  • Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen. Parameterized Complexity of Induced H-Matching on Claw-Free Graphs. Proceedings of the European Symposium on Algorithms (ESA '12), Lecture Notes in Computer Science 7501, pp. 624-635.
    original publication
  • Matthias Mnich, Rico Zenklusen: Bisections Parameterized Above Tight Lower Bound. Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG '12), Lecture Notes in Computer Science 7551, pp. 184-193.
    original publication
  • 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), Lecture Notes in Computer Science 7391, pp. 242-253.
    original publication
  • 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), Lecture Notes in Computer Science 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), pp. 597-623.
    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), pp. 822-848.
    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.
    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.