Stefan Kratsch

ORCID

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 89

Top Venues

Saarland University (PHD)

Education History

Saarland University

PHD

Publications

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Flow-augmentation II: Undirected Graphs. ACM Trans. Algorithms 20 (2) (2024)
Stefan Kratsch, Van Bang Le
On polynomial kernelization for Stable Cutset. CoRR (2024)
Narek Bojikian, Stefan Kratsch
A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width. ICALP (2024)
Narek Bojikian, Stefan Kratsch
Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width. CoRR (2024)
Stefan Kratsch, Pascal Kunz
Approximate Turing Kernelization and Lower Bounds for Domination Problems. IPEC (2023)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. SODA (2023)
Stefan Kratsch, Pascal Kunz
Approximate Turing kernelization and lower bounds for domination problems. CoRR (2023)
Falko Hegerfeld, Stefan Kratsch
Tight algorithms for connectivity problems parameterized by clique-width. CoRR (2023)
Narek Bojikian, Stefan Kratsch
A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width. CoRR (2023)
Falko Hegerfeld, Stefan Kratsch
Tight Algorithms for Connectivity Problems Parameterized by Clique-Width. ESA (2023)
Falko Hegerfeld, Stefan Kratsch
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth. CoRR (2023)
Narek Bojikian, Vera Chekan, Falko Hegerfeld, Stefan Kratsch
Tight Bounds for Connectivity Problems Parameterized by Cutwidth. STACS (2023)
Vera Chekan, Stefan Kratsch
Tight Algorithmic Applications of Clique-Width Generalizations. MFCS (2023)
Falko Hegerfeld, Stefan Kratsch
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth. WG (2023)
Stefan Kratsch, Florian Nelles
Efficient parameterized algorithms for computing all-pairs shortest paths. Discret. Appl. Math. 341 (2023)
Vera Chekan, Stefan Kratsch
Tight Algorithmic Applications of Clique-Width Generalizations. CoRR (2023)
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. SIAM J. Discret. Math. 36 (3) (2022)
Stefan Kratsch, Florian Nelles
Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width. CoRR (2022)
Narek Bojikian, Vera Chekan, Falko Hegerfeld, Stefan Kratsch
Tight Bounds for Connectivity Problems Parameterized by Cutwidth. CoRR (2022)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. CoRR (2022)
Stefan Kratsch, Florian Nelles, Alexandre Simon
On Triangle Counting Parameterized by Twin-Width. CoRR (2022)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Directed flow-augmentation. STOC (2022)
Falko Hegerfeld, Stefan Kratsch
Towards Exact Structural Thresholds for Parameterized Complexity. IPEC (2022)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Directed flow-augmentation. CoRR (2021)
Toni Böhnlein, Stefan Kratsch, Oliver Schaudt
Revenue maximization in Stackelberg Pricing Games: beyond the combinatorial setting. Math. Program. 187 (1) (2021)
Falko Hegerfeld, Stefan Kratsch
Towards exact structural thresholds for parameterized complexity. CoRR (2021)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Solving hard cut problems via flow-augmentation. SODA (2021)
Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge
Optimal Discretization is Fixed-parameter Tractable. SODA (2021)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Solving hard cut problems via flow-augmentation. CoRR (2020)
Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge
Optimal Discretization is Fixed-parameter Tractable. CoRR (2020)
Stefan Kratsch, Florian Nelles
Efficient parameterized algorithms for computing all-pairs shortest paths. CoRR (2020)
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. STACS (2020)
Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström
Multi-budgeted Directed Cuts. Algorithmica 82 (8) (2020)
Stefan Kratsch, Florian Nelles
Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths. STACS (2020)
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
Approximate Turing Kernelization for Problems Parameterized by Treewidth. CoRR (2020)
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
Approximate Turing Kernelization for Problems Parameterized by Treewidth. ESA (2020)
Stefan Kratsch, Magnus Wahlström
Representative Sets and Irrelevant Vertices: New Tools for Kernelization. J. ACM 67 (3) (2020)
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
Bipartite graphs of small readability. Theor. Comput. Sci. 806 (2020)
Falko Hegerfeld, Stefan Kratsch
Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space. CoRR (2020)
Falko Hegerfeld, Stefan Kratsch
Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space. STACS (2020)
Falko Hegerfeld, Stefan Kratsch
On adaptive algorithms for maximum matching. CoRR (2019)
Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge
The parameterized complexity of the minimum shared edges problem. J. Comput. Syst. Sci. 106 (2019)
Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson
The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. SIAM J. Discret. Math. 33 (4) (2019)
Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
Assessing the computational complexity of multilayer subgraph detection. Netw. Sci. 7 (2) (2019)
Eva-Maria C. Hols, Stefan Kratsch
On Kernelization for Edge Dominating Set under Structural Parameters. CoRR (2019)
Falko Hegerfeld, Stefan Kratsch
On Adaptive Algorithms for Maximum Matching. ICALP (2019)
Eva-Maria C. Hols, Stefan Kratsch
On Kernelization for Edge Dominating Set under Structural Parameters. STACS (2019)
Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. ESA (2019)
Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. CoRR (2019)
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. CoRR (2019)
Yann Disser, Stefan Kratsch, Manuel Sorge
The Minimum Feasible Tileset Problem. Algorithmica 81 (3) (2019)
Stefan Kratsch
A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. SIAM J. Discret. Math. 32 (3) (2018)
Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström
Multi-Budgeted Directed Cuts. IPEC (2018)
Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström
Multi-budgeted directed cuts. CoRR (2018)
Stefan Kratsch, Florian Nelles
Efficient and Adaptive Parameterized Algorithms on Modular Decompositions. ESA (2018)
Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson
The parameterized complexity of finding a 2-sphere in a simplicial complex. CoRR (2018)
Robert Bredereck, Jiehua Chen, Falk Hüffner, Stefan Kratsch
Parameterized complexity of team formation in social networks. Theor. Comput. Sci. 717 (2018)
Eva-Maria C. Hols, Stefan Kratsch
A Randomized Polynomial Kernel for Subset Feedback Vertex Set. Theory Comput. Syst. 62 (1) (2018)
Jérémy Barbay, Johannes Fischer, Stefan Kratsch, Srinivasa Rao Satti
Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). Dagstuhl Reports 8 (7) (2018)
Marek Cygan, Stefan Kratsch, Jesper Nederlof
Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM 65 (3) (2018)
Stefan Kratsch, Florian Nelles
Efficient and adaptive parameterized algorithms on modular decompositions. CoRR (2018)
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
Bipartite Graphs of Small Readability. COCOON (2018)
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
Bipartite Graphs of Small Readability. CoRR (2018)
Eva-Maria C. Hols, Stefan Kratsch
Smaller Parameters for Vertex Cover Kernelization. IPEC (2017)
Toni Böhnlein, Stefan Kratsch, Oliver Schaudt
Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting. ICALP (2017)
Stefan Kratsch, Pascal Schweitzer
Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Discret. Appl. Math. 216 (2017)
Stefan Kratsch, Martin Milanic
On the complexity of the identifiable subgraph problem, revisited. Discret. Appl. Math. 226 (2017)
Yann Disser, Stefan Kratsch
Robust and Adaptive Search. STACS (2017)
Hans L. Bodlaender, Stefan Kratsch, Vincent J. C. Kreuzen, O-joung Kwon, Seongmin Ok
Characterizing width two for variants of treewidth. Discret. Appl. Math. 216 (2017)
Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson
The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. STACS (2017)
Yann Disser, Stefan Kratsch
Robust and adaptive search. CoRR (2017)
Eva-Maria C. Hols, Stefan Kratsch
Smaller parameters for vertex cover kernelization. CoRR (2017)
Stefan Kratsch, Manuel Sorge
On Kernelization and Approximation for the Vector Connectivity Problem. Algorithmica 79 (1) (2017)
Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin
Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84 (2017)
Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
Assessing the Computational Complexity of Multi-layer Subgraph Detection. CIAC (2017)
Stefan Kratsch
On polynomial kernels for sparse integer linear programs. J. Comput. Syst. Sci. 82 (5) (2016)
Eva-Maria C. Hols, Stefan Kratsch
A Randomized Polynomial Kernel for Subset Feedback Vertex Set. STACS (2016)
Stefan Kratsch
A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. ESA (2016)
Gregory Z. Gutin, Stefan Kratsch, Magnus Wahlström
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem. Algorithmica 75 (2) (2016)
Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, Vuong Anh Quyen
Preprocessing Under Uncertainty: Matroid Intersection. MFCS (2016)
Stefan Kratsch
A randomized polynomial kernelization for Vertex Cover with a smaller parameter. CoRR (2016)
Stefan Kratsch, Martin Milanic
On the complexity of the identifiable subgraph problem, revisited. CoRR (2016)
Stefan Fafianie, Stefan Kratsch, Vuong Anh Quyen
Preprocessing Under Uncertainty. STACS (2016)
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
Finding Shortest Paths Between Graph Colourings. Algorithmica 75 (2) (2016)
Stefan Kratsch, Dániel Marx, Magnus Wahlström
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. ACM Trans. Comput. Theory 8 (1) (2016)
Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge
The Parameterized Complexity of the Minimum Shared Edges Problem. CoRR (2016)
Stefan Kratsch, Geevarghese Philip, Saurabh Ray
Point Line Cover: The Easy Kernel is Essentially Tight. ACM Trans. Algorithms 12 (3) (2016)
Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
Assessing the Computational Complexity of Multi-Layer Subgraph Detection. CoRR (2016)
Robert Bredereck, Jiehua Chen, Falk Hüffner, Stefan Kratsch
Parameterized Complexity of Team Formation in Social Networks. AAIM (2016)
Stefan Kratsch, Manuel Sorge
On Kernelization and Approximation for the Vector Connectivity Problem. IPEC (2015)
Stefan Fafianie, Stefan Kratsch
A shortcut to (sun)flowers: Kernels in logarithmic space or linear time. CoRR (2015)
Bart M. P. Jansen, Stefan Kratsch
A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity. ESA (2015)
Stefan Fafianie, Stefan Kratsch
An Experimental Analysis of a Polynomial Compression for the Steiner Cycle Problem. SEA (2015)
Bart M. P. Jansen, Stefan Kratsch
A structural approach to kernels for ILPs: Treewidth and Total Unimodularity. CoRR (2015)
Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. SIAM J. Discret. Math. 29 (1) (2015)
Eva-Maria C. Hols, Stefan Kratsch
A randomized polynomial kernel for Subset Feedback Vertex Set. CoRR (2015)
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243 (2015)
René van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger
Approximability and parameterized complexity of multicover by c-intervals. Inf. Process. Lett. 115 (10) (2015)
Stefan Fafianie, Stefan Kratsch
A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time. MFCS (2) (2015)
Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge
The Parameterized Complexity of the Minimum Shared Edges Problem. FSTTCS (2015)

Stefan Kratsch.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Stefan Kratsch