University of Bonn · Institute of Computer Science · Theoretical Computer Science

Sidebar

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

Preprints

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

2017

  • Michael Etscheid, Matthias Mnich:
    Linear Kernels and Linear-Time Algorithms for Finding Large Cuts.
    Algorithmica , to appear.
  • Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase: New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness.
    Mathematical Programming, Series A , to appear
    preprint
  • Matthias Mnich, Tobias Mömke:
    Improved Integrality Gap Upper Bounds for TSP with Distances One and Two.
    European Journal of Operational Research , to appear
    preprint
  • Matthias Mnich:
    Big Data Algorithms Beyond Machine Learning.
    KI - Künstliche Intelligenz , to appear.
  • 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,
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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),
    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.
    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.
    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.
    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

Imprint/Impressum