Universität Bonn
Institute of Computer Science
Department of Theoretical Computer Science
Endenicher Allee 19a
D-53115 Bonn
Germany
mmnich---remove-this---@uni-bonn.de

• Lorentz Workshop "Scheduling meets Fixed-Parameter Tractability"
• DFG Project “Multivariate Algorithms for Scheduling”
• DFG Project “Kernelization for Big Data”, associated with DFG SPP 1736 "Algorithms for Big Data"
• PC Member for IJCAI-ECAI 2018
• PC Member for SWAT 2018
• MC Member for European Network for Game Theory

• Alexander Göke (PhD student at Bonn University), funded by DFG Project “Kernelization for Big Data” associated with DFG SPP 1736 "Algorithms for Big Data"
• Roland Vincze (PhD student at Maastricht University), co-supervised with André Berger
• Alisa Govzmann (MSc student at Bonn University)
• Damir Ferizovi (MSc student at Karlsruhe Institute of Technology), co-supervised with Demian Hespe and Sebastian Lamm

• Stefano Ugliano (PhD student), funded by DFG Project “Big Data Kernelization” associated with DFG SPP 1736 "Algorithms for Big Data"
• Simone Tummers (MSc, 2017)
• 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)

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

• Course "Allocations and Algorithms", Bachelor Course at Maastricht University

• Course "Operations Management", Bachelor Course at Maastricht University

• Course "Second Year Project Skills", Bachelor Course at Maastricht University

• Course "Management of Operations and Product Development", Bachelor Course at Maastricht University

• Course "Allocations and Algorithms", Bachelor Course at Maastricht University

• Course "Operations Management", Bachelor Course at Maastricht University

• Seminar "Advanced Algorithms", Graduate Course at Bonn University

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

• Course Lecture "Diskrete Mathematik", Undergraduate Course at TU Darmstadt
• Seminar "Proofs from THE BOOK", Undergraduate Course at TU Darmstadt

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

• Seminar "Graphs on Surfaces", Undergraduate Course at Saarland University

• Lecture "Exponential-Time Algorithms", Graduate Course at Saarland University

• Anna Adamaszek, Matthias Mnich, Katarzyna Paluch:
  New approximation algorithms for (1,2)-TSP
  ICALP 2018

• John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani:
  Reachability switching games
  ICALP 2018

• Martin Koutecký, Dusan Knop, Matthias Mnich:
  Combinatorial n-fold integer programming and applications
  ESA 2017

• Josh Alman, Matthias Mnich, Virginia Vassilevska Williams:
  Dynamic parameterized problems and algorithms
  ICALP 2017

• Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase:
  New algorithms for maximum disjoint paths based on tree-likeness
  ESA 2016

• Matthias Mnich, Virginia Vassilevska Williams, László A. Végh:
  A 7/3-approximation for feedback vertex sets in tournaments
  ESA 2016

• Zdeněk Dvořák, Matthias Mnich:
  Large independent sets in triangle-free planar graphs
  ESA 2014

• Matthias Mnich, Andreas Wiese:
  Scheduling and fixed-parameter tractability
  IPCO 2014

• Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
  Parameterized complexity of induced H-matching on claw-free graphs
  ESA 2012

• Robert Crowston, Mark Jones, Matthias Mnich:
  Max-cut parameterized above the Edwards-Erdős-bound
  ICALP 2012

• Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger:
  Domination when the stars are out
  ICALP 2011

• Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo:
  All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels
  ESA 2010

• Serge Gaspers, Matthias Mnich:
  Feedback vertex sets in tournaments
  ESA 2010

• Ross Kang, Matthias Mnich, Tobias Müller:
  Induced matchings in subcubic planar graphs
  ESA 2010

Publications with logo are freely accessible through Open Access.

• André Berger, László Kozma, Matthias Mnich, Roland Vincze:
  Time- and space-optimal algorithms for the many-visits TSP
  preprint

• Aida Abiad, Sander Gribling, Domenico Lahaye, Matthias Mnich, Guus Regts, Lluis Vena, Gerard Verweij, Peter Zwaneveld:
  On the complexity of solving a decision problem with flow-depending costs: the case of the IJsselmeer dikes
  preprint

• Karthekeyan Chandrasekaran, Matthias Mnich, Sahand Mozaffari:
  Odd multiway cut in directed acyclic graphs
  preprint

• Matthias Mnich, René van Bevern:
  Parameterized complexity of machine scheduling: 15 open problems
  preprint

• Matthias Mnich, Heiko Röglin, Clemens Rösner:
  New deterministic algorithms for solving parity games
  Discrete Optimization , to appear.
  preprint
  original publication

• Anna Adamaszek, Matthias Mnich, Katarzyna Paluch:
  New approximation algorithms for (1,2)-TSP
  Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '18), Leibniz International Proceedings in Informatics 107, pp. 9:1–9:14.
  original publication

• John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani:
  Reachability switching games
  Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '18), Leibniz International Proceedings in Informatics 107, pp. 124:1–124:14.
  original publication
  preprint

• Martin Koutecký, Dusan Knop, Matthias Mnich:
  A unifying framework for manipulation problems
  Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS '18), pp. 256–264.
  original publication
  preprint

• Matthias Mnich, Tobias Mömke:
  Improved integrality gap upper bounds for TSP with distances one and two
  European Journal of Operational Research 266(2), pp. 436-457.
  original publication

• Matthias Mnich, Ignaz Rutter, Jens Schmidt:
  Linear-time recognition of map graphs with outerplanar witness
  Discrete Optimization 28, pp. 63-77.
  original publication

• Matthias Mnich, Eva-Lotta Teutrine:
  Improved bounds for minimal feedback vertex sets in tournaments
  Journal of Graph Theory 88(3), pp. 482-506.
  original publication

• Michael Etscheid, Matthias Mnich:
  Linear kernels and linear-time algorithms for finding large cuts
  Algorithmica 80(9), pp. 2574–2615.
  original publication

• Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase:
  New algorithms for maximum disjoint paths based on tree-likeness
  Mathematical Programming, Series A , to appear
  original publication

• Matthias Mnich:
  Big Data algorithms beyond machine learning
  KI - Künstliche Intelligenz 32(1), pp. 9–17.
  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
  arXiv version

• Martin Koutecký, Dusan Knop, Matthias Mnich:
  Combinatorial n-fold integer programming and applications
  Proceedings of the European Symposium on Algorithms (ESA '17), Leibniz International Proceedings in Informatics 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), Leibniz International Proceedings in Informatics 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), Leibniz International Proceedings in Informatics 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
  arXiv version

• 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
  arXiv version

• 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), Leibniz International Proceedings in Informatics 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), Leibniz International Proceedings in Informatics 63, pp. 24:1–24: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), Leibniz International Proceedings in Informatics 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), Leibniz International Proceedings in Informatics 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), Leibniz International Proceedings in Informatics 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), Leibniz International Proceedings in Informatics 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
  arXiv version

• 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), Leibniz International Proceedings in Informatics 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

• 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
  arXiv version

• 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

• Matthias Mnich, Andreas Wiese:
  Scheduling and fixed-parameter tractability
  Mathematical Programming Series B 154(1), pp. 533-562.
  original publication
  arXiv version

• 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
  arXiv version

• Robert Crowston, Mark Jones, Matthias Mnich:
  Max-cut parameterized above the Edwards-Erdős bound
  Algorithmica 72(3), pp. 734-757.
  original publication
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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
  arXiv version

• 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.
  original publication

• Matthias Mnich:
  Book Review Exact Exponential Algorithms
  Operations Research Letters 39(3), pp. 229-230.
  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

• 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
  arXiv version

• 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
  arXiv version

• 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

• 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
  arXiv version

• 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

• 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

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