Stefan Kratsch

news: I have moved to University of Bonn on January 1, 2015. This webpage is no longer updated as of April 2015.

How to reach me
photo of Stefan Kratsch

Professor for theoretical computer science

Stefan Kratsch
Theoretische Informatik und formale Methoden
Institut für Informatik
Universität Bonn
Friedrich-Ebert-Allee 144
D-53113 Bonn

Phone: +49 228 73 4554
Fax: +49 228 73 4321
Room: II.60 (LBH)

Office hours: There are no consultation hours. Feel free to make appointments by email or phone. Also feel free to just come by (with a small risk of waiting for a moment, and a very small risk of just getting an appointment for later).

E-mail: lastname AT cs DOT uni MINUS bonn DOT de
E-mail: firstname DOT lastname AT uni MINUS bonn DOT de

Research interests
  • Parameterized complexity, especially kernelization
  • Graph problems
  • Constraint satisfaction problems
  • Computational complexity
Supported by
University of Bonn University of Bonn



DFG Emmy Noether program Emmy Noether program of the DFG
Previously supported by
TU Berlin Technical University Berlin

What can I do for you?

Students of University of Bonn
What can we expect from you?
  • I will contribute to the standard theoretical computer science lectures.
  • I will offer specialized lectures on topics of parameterized complexity and exact algorithms for NP-hard problems.
  • I am offering master and bachelor thesis topics, research and teaching assistant jobs.
  • I can also offer opinions on the question of whether or not to pursue a PhD and where to do so.
Topics and supervision for master/bachelor theses
  • Sure. Send me an email with some research interests and I will suggest one or more topics.
Jobs as student research assistant
  • Contact me. I have some things in mind that could do with some student assistance.
Students of TU Berlin
Can I still take the oral exam for lectures that you gave at TU Berlin?
  • I am no longer at TU Berlin and formally cannot hold exams for TUB students. Prof. Niedermeier will hold all necessary exams.
Researchers (PhD students, postdocs,...)
Visiting me and departments I and V at University of Bonn?
  • Gladly! We welcome visitors. Bonn is a nice place to visit and reachable via Cologne/Bonn airport!
  • In particular, PhD students working on parameterized complexity are encouraged to get in contact regarding a research visit.
You need a full version of one of my papers?
Scientific community
Reviews for conferences and journals
  • By all means. I review for all publishers and venues so long as the work in question is within my expertise and interest.
  • There is a stack limit regarding the number of parallel requests that I'm willing to accept.
Grant proposal reviews and related things
  • Again, by all means. I am sure to make time for these important matters.
Applicants for positions
Do you have a vacant PhD or postdoc position?
  • All vacancies are announced on the DMANET mailing list; it is generally a good idea to follow that list if you are interested in discrete mathematics and theoretical computer science.
Will there be a position in x months?
  • If you are strongly interested in working with me then contact me and we can check if something can be done. Generally it is a better idea to apply for jobs that are already fully funded because third party funding always takes time to be decided and is never guaranteed.
  • I may also be willing to serve as host if you want to apply for PhD/postdoc funding yourself, e.g., through some stipend. These should usually process faster.
  • General advice: Start thinking about your PhD or industry job when you start on your master thesis!
Internships for students
  • I am not offering any internships for students.
  • If you think that you are an exception then my advice would be to write a *very* compelling email with solid evidence of your interest in my work and the field of parameterized complexity as a whole. (I will probably not look at attachments that I did not specifically request.)

Teaching

Current
  • Summer 2015 "Parameterized complexity" at University of Bonn.
Previous lectures
  • Summer 2014 "Computational complexity" at TU Berlin.
  • Winter 2013/14 "Parameterized complexity" at TU Berlin.
  • Summer 2012 "Algorithms and Networks" jointly with Hans L. Bodlaender at Utrecht University
  • Summer 2011 "Algorithms and Networks" jointly with Hans L. Bodlaender at Utrecht University

Recent Positions

Education

Scientific activities

Program committee participation
Current
  • PC member of IPEC 2015
Previous

Publications

2014
Conference articles
  • Gregory Gutin and Stefan Kratsch and Magnus Wahlström.
    Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem.
    In IPEC 2014.
  • Vuong Anh Quyen and Stefan Kratsch.
    On kernels for covering and packing ILPs with small coefficients.
    In IPEC 2014.
  • Matthew Johnson and Dieter Kratsch and Stefan Kratsch and Viresh Patel and Daniel Paulusma.
    Finding Shortest Paths between Graph Colourings.
    In IPEC 2014.
  • Yann Disser and Stefan Kratsch and Manuel Sorge.
    The Minimum Feasible Tileset problem.
    In WAOA 2014.
  • Stefan Fafianie and Stefan Kratsch.
    Streaming Kernelization.
    In MFCS 2014.
  • Stefan Kratsch and Geevarghese Philip and Saurabh Ray.
    Point Line Cover: The Easy Kernel is Essentially Tight.
    In SODA 2014.
Journal articles
  • Stefan Kratsch.
    Co-Nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-Type Problem.
    In Transactions on Algorithms, ACM, 2014.
  • Stefan Kratsch and Magnus Wahlström.
    Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal.
    In Transactions on Algorithms, ACM, 2014.
  • Stefan Kratsch.
    Recent developments in kernelization: A survey.
    In Bulletin of the EATCS, 2014. (pdf)
  • Marek Cygan and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Magnus Wahlström.
    Clique Cover and Graph Separation: New Incompressibility Results.
    In Transactions on Computation Theory, ACM, 2014.
  • Robert Bredereck and Jiehua Chen and Sepp Hartung and Stefan Kratsch and Rolf Niedermeier and Ondrej Suchy and Gerhard J. Woeginger.
    A Multivariate Complexity Analysis of Lobbying in Multiple Referenda.
    In Journal of Artificial Intelligence Research, 2014.
  • Fedor V. Fomin and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Yngve Villanger.
    Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters.
    In Journal of Computer and System Sciences, Elsevier, 2014.
  • Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch.
    Kernelization Lower Bounds by Cross-Composition.
    In Journal on Discrete Mathematics, SIAM, 2014.
2013
Conference articles
  • Dieter Kratsch and Stefan Kratsch.
    The Jump Number Problem: Exact and Parameterized.
    In IPEC 2013.
  • Danny Hermelin and Stefan Kratsch and Karolina Soltys and Magnus Wahlström and Xi Wu.
    A Completeness Theory for Polynomial (Turing) Kernelization.
    In IPEC 2013.
  • Stefan Kratsch.
    On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility.
    In ESA 2013.
  • Hans L. Bodlaender and Stefan Kratsch and Vincent J. C. Kreuzen.
    Fixed-Parameter Tractability and Characterizations of Small Special Treewidth.
    In WG 2013.
  • Noga Alon and Robert Bredereck and Jiehua Chen and Stefan Kratsch and Rolf Niedermeier and Gerhard J. Woeginger.
    How to Put Through Your Agenda in Collective Binary Decisions.
    In ADT 2013.
  • Hans L. Bodlaender and Marek Cygan and Stefan Kratsch and Jesper Nederlof.
    Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth.
    In ICALP 2013.
  • Marek Cygan and Stefan Kratsch and Jesper Nederlof.
    Fast Hamiltonicity checking via bases of perfect matchings.
    In STOC 2013.
  • Stefan Kratsch.
    On Polynomial Kernels for Sparse Integer Linear Programs.
    In STACS 2013.
  • Fedor V. Fomin and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Yngve Villanger.
    Tight bounds for Parameterized Complexity of Cluster Editing.
    In STACS 2013.
Journal articles
  • Stefan Kratsch and Magnus Wahlström.
    Two edge modification problems without polynomial kernels.
    In Discrete Optimization, Elsevier, 2013.
  • Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch.
    Kernel bounds for path and cycle problems.
    In Theoretical Computer Science, Elsevier, 2013.
  • Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch.
    Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.
    In Journal on Discrete Mathematics, SIAM, 2013.
  • Stefan Kratsch and Frank Neumann.
    Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem.
    In Algorithmica, Springer, 2013.
  • Danny Hermelin and Chien-Chung Huang and Stefan Kratsch and Magnus Wahlström.
    Parameterized Two-Player Nash Equilibrium.
    In Algorithmica, Springer, 2013.
  • Klaus Jansen and Stefan Kratsch and Daniel Marx and Ildiko Schlotter.
    Bin Packing with Fixed Number of Bins Revisited.
    In Journal of Computer and System Sciences, Elsevier, 2013.
  • Pinar Heggernes and Pim van 't Hof and Bart M. P. Jansen and Stefan Kratsch and Yngve Villanger.
    Parameterized Complexity of Vertex Deletion into Perfect Graph Classes.
    In Theoretical Computer Science, Elsevier, 2013.
2012
Conference articles
  • Stefan Kratsch and Magnus Wahlström.
    Representative Sets and Irrelevant Vertices: New Tools for Kernelization.
    In FOCS 2012.
  • Stefan Kratsch and Pascal Schweitzer.
    Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs.
    In WG 2012.
  • Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch.
    Kernel Bounds for Structural Parameterizations of Pathwidth.
    In SWAT 2012.
  • Stefan Kratsch and Marcin Pilipczuk and Ashutosh Rai and Venkatesh Raman.
    Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs.
    In SWAT 2012.
  • Robert Bredereck and Jiehua Chen and Sepp Hartung and Stefan Kratsch and Rolf Niedermeier and Ondrej Suchy.
    A Multivariate Complexity Analysis of Lobbying in Multiple Referenda.
    In AAAI 2012.
  • Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Magnus Wahlström.
    Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.
    In ICALP 2012.
  • Marek Cygan and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Magnus Wahlström.
    Clique Cover and Graph Separation: New Incompressibility Results.
    In ICALP 2012.
  • Stefan Kratsch and Magnus Wahlström.
    Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal.
    In SODA 2012.
  • Stefan Kratsch.
    Co-nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-type Problem.
    In SODA 2012.
Journal articles
  • Stefan Kratsch.
    Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP.
    In Algorithmica, Springer, 2012.
2011
Conference articles
  • Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch.
    Kernel Bounds for Path and Cycle Problems.
    In IPEC 2011.
  • Jiong Guo and Iyad Kanj and Stefan Kratsch.
    Safe approximation and its relation to kernelization.
    In IPEC 2011.
  • Bart M. P. Jansen and Stefan Kratsch.
    On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal.
    In IPEC 2011.
  • Bart M. P. Jansen and Stefan Kratsch.
    Data Reduction for Graph Coloring Problems. In FCT 2011.
  • Pinar Heggernes and Pim van 't Hof and Bart Jansen and Stefan Kratsch and Yngve Villanger.
    Parameterized Complexity of Vertex Deletion into Perfect Graph Classes. FCT 2011.
  • Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch.
    Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.
    ICALP 2011.
  • Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch.
    Cross-Composition: A New Technique for Kernelization Lower Bounds. STACS 2011.
  • Danny Hermelin and Chien-Chung Huang and Stefan Kratsch and Magnus Wahlström.
    Parameterized Two-Player Nash Equilibrium.
    In WG 2011.
2010
Conference articles
  • Stefan Kratsch and Daniel Marx and Magnus Wahlström.
    Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems.
    In MFCS 2010.
  • Stefan Kratsch and Magnus Wahlström.
    Preprocessing of Min Ones Problems: A Dichotomy.
    In ICALP 2010
  • Stefan Kratsch and Per Kristian Lehre and Franl Neumann and Pietro Simone Oliveto.
    Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutation.
    In PPSN 2010.
  • Stefan Kratsch and Pascal Schweitzer.
    Isomorphism of Graphs of Bounded Feedback Vertex Set Number.
    In SWAT 2010.
  • Klaus Jansen and Stefan Kratsch and Daniel Marx and Ildiko Schlotter.
    Bin Packing with Fixed Number of Bins Revisited.
    In SWAT 2010.
2009
Conference articles
  • Stefan Kratsch and Magnus Wahlström.
    Two Edge Modification Problems Without Polynomial Kernels.
    In IWPEC 2009.
  • Stefan Kratsch and Frank Neumann.
    Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem.
    In GECCO 2009. (Best Paper Award).
  • Stefan Kratsch.
    Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP.
    In STACS 2009.