Dr. Matthias Mnich

OfficeUniversity of Bonn
Institute of
Computer Science, Dept. V
Room E.
Friedrich-Ebert-Allee 144
D-53113 Bonn
Phone
Fax +49 (228) 73 - 4321
Email mmnich@uni-bonn.de
Office HoursBy appointment

Research Group

Current Students

  • Alexander Göke (PhD student at Bonn University), funded by DFG Project “Big Data Kernelization” associated with DFG SPP 1736 "Algorithms for Big Data"
  • Waldemar Laube (PhD student at Maastricht University)
  • Roland Vincze (PhD student at Maastricht University), co-supervised with André Berger
  • Alisa Govzmann (MSc student at Bonn University)
  • Russell Dahlke (MSc student at Maastricht University)
  • Simone Tummers (MSc student at Maastricht University)

Former Students

  • Stefano Ugliano (PhD student), funded by DFG Project “Big Data Kernelization” associated with DFG SPP 1736 "Algorithms for Big Data"
  • René Wittmann (MSc, 2016)
  • Eva-Lotta Teutrine (MSc, 2016), awarded the Thesis Prize by the Bonner Informatik Gesellschaft e.V.
  • René Wittmann (BSc, 2014)
  • Alexandra Stern (BSc, 2014)
  • Lars Burghardt (BSc, 2014)
  • Christopher Brozek (BSc, 2014)
  • Antonia Eckhardt (BSc, 2014)
  • Robin Adner (BSc, 2014)
  • Oliver Déjon (MSc, 2013)

Research Interests

  • combinatorial optimization
  • scheduling
  • social choice theory
  • parameterized complexity
  • discrete mathematics

Current Teaching

Summer Term 2017

Winter Term 2016

Winter Term 2015/2016

Winter Term 2014/2015

  • Core Lecture “Pearls of Algorithms”, Graduate Course at Bonn University

Winter Term 2013/2014

Summer Term 2013

  • Core Lecture "Optimization", Undergraduate Course at Saarland University

Winter Term 2012/2013

Summer Term 2012

List of Publications

Publications with Open Access logo are freely accessible through Open Access.

Preprints

  • Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems.
    Open Access preprint
  • John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani: Reachability Switching Games.
    Open Access preprint

2017

  • Matthias Mnich, Eva-Lotta Teutrine:
    Improved Bounds for Minimal Feedback Vertex Sets in Tournaments.
    Journal of Graph Theory , to appear.
  • Michael Etscheid, Matthias Mnich:
    Linear Kernels and Linear-Time Algorithms for Finding Large Cuts.
    Algorithmica , to appear.
    Open Access original publication
  • Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase: New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness.
    Mathematical Programming, Series A , to appear
    Open Access original publication
  • Matthias Mnich, Tobias Mömke:
    Improved Integrality Gap Upper Bounds for TSP with Distances One and Two.
    European Journal of Operational Research , to appear
    original publication
  • Matthias Mnich:
    Big Data Algorithms Beyond Machine Learning.
    KI - Künstliche Intelligenz , to appear
    Open Access original publication
  • Matthias Mnich, Ildikó Schlotter:
    Stable Marriage with Covering Constraints: A Complete Computational Trichotomy.
    Proceedings of the International Symposium on Algorithmic Game Theory (SAGT '17) Lecture Notes in Computer Science 10504, pp. 320–332.
    original publication
  • Martin Koutecky, Dusan Knop, Matthias Mnich:
    Combinatorial n-fold Integer Programming and Applications.
    Proceedings of the European Symposium on Algorithms (ESA '17), LIPIcs 87, pp. 54:1–54:14,
    Open Access original publication
  • Josh Alman, Matthias Mnich, Virginia Vassilevska Williams:
    Dynamic Parameterized Problems and Algorithms.
    Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '17), LIPIcs 80, pp. 41:1–41:16.
    Open Access original publication
  • Matthias Mnich, Erik Jan van Leeuwen:
    Polynomial Kernels for Deletion to Classes of Acyclic Digraphs.
    Discrete Optimization 25, pp. 48-76.
    original publication
  • Martin Koutecky, Dusan Knop, Matthias Mnich:
    Voting and Bribing in Single Exponential Time.
    Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS '17), LIPIcs 66, pp. 46:1–46:14.
    Open Access original publication
  • Zdenek Dvorak, Matthias Mnich:
    Large Independent Sets in Triangle-Free Planar Graphs
    SIAM Journal on Discrete Mathematics 31(2), pp. 1355-1373.
    original publication

2016

  • Michael Etscheid, Matthias Mnich:
    Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
    Proceedings of the International Symposium on Algorithms and Computation (ISAAC '16), LIPIcs 64, pp. 31:1–31:13.
    Open Access original publication
  • Matthias Mnich, Eva-Lotta Teutrine:
    Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
    Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC '16), LIPIcs 63, pp. 24:1–24:10.
    Open Access original publication
  • Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin:
    Polynomial Kernels for Weighted Problems
    Journal of Computer and System Sciences 84, pp. 1-10.
    original publication
  • Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase:
    New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness.
    Proceedings of the European Symposium on Algorithms (ESA '16), LIPIcs 57, pp. 42:1–42:17.
    Open Access original publication
  • Matthias Mnich, Virginia Vassilevska Williams, László A. Végh:
    A 7/3-Approximation for Feedback Vertex Sets in Tournaments.
    Proceedings of the European Symposium on Algorithms (ESA '16), LIPIcs 57, pp. 67:1–67:14.
    Open Access original publication
  • Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski:
    On Routing Disjoint Paths in Bounded Treewidth Graphs.
    Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '16), LIPIcs 53, pp. 15:1-15:15.
    Open Access original publication
  • Matthias Mnich, Ignaz Rutter, Jens M. Schmidt:
    Linear-Time Recognition of Map Graphs with Outerplanar Witness.
    Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '16), LIPIcs 53, pp. 5:1-5:14.
    Open Access original publication
  • Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
    Parameterized Complexity Dichotomy for Steiner Multicut.
    Journal of Computer and System Sciences 82(6), pp. 1020-1043.
    original publication
  • Anna Adamaszek, Michal Adamaszek , Matthias Mnich, Jens M. Schmidt:
    Lower Bounds for Locally Highly Connected Graphs
    Graphs and Combinatorics 32(5), pp. 1641-1650.
    original publication
  • Matthias Mnich, Erik Jan van Leeuwen:
    Polynomial Kernels for Deletion to Acyclic Digraphs.
    Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS '16), LIPIcs 47, pp. 55:1-55:13.
    Open Access original publication
  • Matthias Mnich, Heiko Röglin, Clemens Rösner:
    New Deterministic Algorithms for Solving Parity Games.
    Proceedings of the Latin American Theoretical Informatics Symposium (LATIN '16), Lecture Notes in Computer Science 9644, pp. 634-645.
    original publication
  • Matthias Mnich:
    Large Independent Sets in Subquartic Planar Graphs.
    Proceedings of the International Workshop on Algorithms and Computation (WALCOM '16), Lecture Notes in Computer Science 9627, pp. 1-13.
    original publication

2015

  • Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin:
    Polynomial Kernels for Weighted Problems.
    Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS '15), Lecture Notes in Computer Science 9235, pp. 287-298.
    original publication
  • Matthias Mnich, Yash Raj Shrestha, Yongjie Yang:
    When Schwartz' Conjecture Holds.
    Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI '15),
    Open Access original publication
  • Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
    Parameterized Complexity Dichotomy for Steiner Multicut.
    Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS '15), Leibniz International Proceedings in Informatics 30, pp. 157-170.
    Open Access original publication

2014

  • Matthias Mnich, Andreas Wiese:
    Scheduling and Fixed-Parameter Tractability.
    Mathematical Programming Series B 154(1), pp. 533-562.
    original publication
  • René van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller:
    Interval Scheduling and Colorful Independent Sets.
    Journal of Scheduling 18(5), pp. 449-469,
    original publication
  • Zdeněk Dvořák, Matthias Mnich:
    Large Independent Sets in Triangle-Free Planar Graphs.
    Proceedings of the European Symposium on Algorithms (ESA '14), Lecture Notes in Computer Science 8737, pp. 346-357.
    original publication
  • Riko Jacob, Tobias Lieber, Matthias Mnich:
    Treewidth Computation and Kernelization in the Parallel External Memory Model.
    Proceedings of Theoretical Computer Science (TCS '14), Lecture Notes in Computer Science 8705, pp. 78-89.
    original publication
  • Henning Fernau, Fedor Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, Saket Saurabh:
    Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems.
    Tsinghua Science and Technology 19(4), pp. 374-386.
    original publication
  • Matthias Mnich, Geevarghese Philip, Saket Saurabh, Ondřey Suchý:
    Beyond Max-Cut: λ-Extendible Properties Parameterized Above Poljak-Turzík Bound.
    Journal of Computer and System Sciences 80(7), pp. 1384-1403.
    original publication
  • Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
    Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs.
    Algorithmica 70(3), pp. 513-560.
    original publication
  • Matthias Mnich, Andreas Wiese:
    Scheduling and Fixed-Parameter Tractability.
    Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO '14), Lecture Notes in Computer Science 8494, pp. 381-392.
    original publication
  • Robert Crowston, Mark Jones, Matthias Mnich:
    Max-Cut Parameterized Above the Edwards-Erdős-Bound. Algorithmica 72(3), pp. 734-757.
    original publication

2013

  • Sylvain Guillemot, Matthias Mnich:
    Kernel and Fast Algorithm for Dense Triplet Inconsistency.
    Theoretical Computer Science 494, pp. 134-143.
    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.
    Open Access 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.
    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.
    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.
    Open Access original publication
  • Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo:
    All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Polynomial Kernels.
    Proceedings of the 18th European Symposium on Algorithms (ESA '10), Lecture Notes in Computer Science 6346, pp. 326-337.
    original publication
  • Serge Gaspers, Matthias Mnich:
    Feedback Vertex Sets in Tournaments.
    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 Planar Graphs.
    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.
    Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA '10), Lecture Notes in Computer Science 6460, pp. 337-348.
    original publication
  • Sylvain Guillemot, Matthias Mnich:
    Kernel and Fast Algorithm for Dense Triplet Inconsistency.
    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.
    Proceedings of 6th Annual Conference Theory and Applications of Models of Computation (TAMC '09), Lecture Notes in Computer Science 5532, 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.

Page Tools