Stefan Kratsch

How to reach me
photo of Stefan Kratsch

Head of Emmy Noether junior research group

Algorithmik und Komplexitätstheorie
Institut für Softwaretechnik und Theoretische Informatik
Technische Universität Berlin
Sekr. TEL 5-1
Ernst Reuter Platz 7
D-10587 Berlin

Phone: +49 30 314 25312
Fax: +49 30 314 23516
Room: TEL 509 D

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

E-mail: firstname DOT lastname AT tu MINUS berlin DOT de

Research interests
  • Parameterized complexity, especially kernelization
  • Graph problems
  • Constraint satisfaction problems
  • Computational complexity
  • Communication complexity
Supported by
TU Berlin Technical University Berlin



DFG Emmy Noether program Emmy Noether program of the DFG

What can I do for you?

Students of TU Berlin
Topics and supervision for master/bachelor theses
  • Sure, just send me an email or come by my office. I will try to find something that matches your interests.
Jobs as student research assistant
  • Contact me. I have some things in mind that could do with some student assistance.
Researchers (PhD students, postdocs,...)
Visiting me and the algorithms and complexity group of Prof. Niedermeier?
  • Gladly! We welcome visitors. Berlin is always worth a visit!
  • In particular, PhD students interested in 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?
  • This is just a small group so positions are limited. 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 tell me as far ahead of time as possible and we can see if we can attract funding for you.
  • I may also be willing to serve as host if you want to apply for PhD/postdoc funding yourself, e.g., through some stipend.
Internships for students
  • I am not offering any internships for students.

Teaching

Current
  • Summer 2014 "Computational complexity" at TU Berlin.
    We will have two lectures and one exercise meeting per week in room 512 in the TEL building at Ernst-Reuter-Platz. The lecture is given in English.
Previous lectures
  • 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
Previous
Editorial work
Special Issues

Publications

2014
Conference articles
  • Stefan Kratsch and Geevarghese Philip and Saurabh Ray.
    Point Line Cover: The Easy Kernel is Essentially Tight.
    In SODA 2014.
Journal articles
  • Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch.
    Kernelization Lower Bounds by Cross-Composition.
    In SIAM 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 SIAM 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.