News: I have moved to TU Berlin on November 1 2012 where I am now leading a junior research group funded by the Emmy Noether program of DFG (German Research Foundation).
Email: stefan (dot) kratsch (at) tu (minus) berlin (dot) de Email(2): skratsch (at) mpi (minus) inf (dot) mpg (dot) de Phone:
+49 30 314 25312 Fax: +49 30 314 23516
October 2002 - February 2008:
Studies in Computer Science at the Friedrich-Schiller University in Jena
Title of Master's Thesis (Diplomarbeit): Problem kernels for NP-hard
edge modification problems: Chain Deletion and Chordal Completion
(supervisor: Prof. Dr. Rolf Niedermeier)
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. To appear in Theoretical Computer Science, Elsevier. Available online: http://dx.doi.org/10.1016/j.tcs.2012.03.013.
Stefan Kratsch. Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP. In Algorithmica, Springer, 2012.
Publications in conference proceedings (see also dblp):
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.
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.
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. WG 2011.
S. Kratsch and D. Marx and W. Wahlström. Parameterized Complexity
and Kernelizability of Max Ones and Exact Ones Problems. In MFCS
2010.
S. Kratsch and M. Wahlström. Preprocessing
of Min Ones Problems:
A Dichotomy. In ICALP 2010
S. Kratsch and P. K. Lehre and F. Neumann and P. S. Oliveto.
Fixed Parameter Evolutionary
Algorithms and Maximum Leaf Spanning
Trees: A Matter of Mutation. In PPSN 2010.
S. Kratsch and P. Schweitzer. Isomorphism
of Graphs of Bounded
Feedback Vertex Set Number. In SWAT 2010.
K. Jansen and S. Kratsch and D. Marx and I. Schlotter. Bin
Packing with Fixed Number of Bins Revisited. In SWAT 2010.
S. Kratsch and M. Wahlström. Two
Edge Modification Problems
Without Polynomial Kernels. In IWPEC
2009.
S. Kratsch and F. Neumann. Fixed-Parameter
Evolutionary
Algorithms and the Vertex Cover Problem. In GECCO 2009. (Best
Paper Award).
S. Kratsch. Polynomial
Kernelizations for MIN F^+Pi_1 and MAX NP.
In STACS 2009.