Prof. Dr. Stefan Kratsch

Prof. Kratsch erforscht die Komplexität von Algorithmen für schwere Rechenproblemen, insbesondere wie man solche Probleme durch intelligente Vorverarbeitung und strukturelle Eigenschaften von Graphen (wie Baumzerlegung oder Clique-Breite) effizient lösen kann. Sein aktueller Fokus liegt auf Kernelisierung – Techniken zur Datenkompression vor der eigentlichen Berechnung – sowie auf parametrisierter Approximation, um auch bei großen Instanzen praktisch lösbar zu bleiben. Diese Methoden sind relevant für Optimierungsprobleme in Logistik, Netzwerkdesign und Planung, wo exakte Lösungen sonst unmöglich wären. Er entwickelt sowohl theoretische Komplexitätsgrenzen als auch konkrete Algorithmen, die zeigen, wann und wie Vorverarbeitung hilft.

🔒 Das System hat 713 mögliche Industrie-Partner gefunden — Firmen, Scores und Begründungen sind nur für eingeloggte Nutzer:innen sichtbar. Anmelden

• NW /2: Effiziente Vorverarbeitung für schwere Probleme: neue Techniken und präzise Modelle für Datenreduktion

  Quelle ↗

  Förderer: DFG Nachwuchsgruppe Zeitraum: 09/2017 - 08/2019 Projektleitung: Prof. Dr. Stefan Kratsch

• NW/1: Effiziente Vorverarbeitung für schwere Probleme: neue Techniken und präzise Modelle für Datenreduktion

  Quelle ↗

  Förderer: DFG Nachwuchsgruppe Zeitraum: 09/2017 - 04/2018 Projektleitung: Prof. Dr. Stefan Kratsch

• NW/3: Effiziente Vorverarbeitung für schwere Probleme: Neue Techniken und präzise Modelle zur Datenreduktion

  Quelle ↗

  Förderer: DFG Nachwuchsgruppe Zeitraum: 10/2018 - 09/2021 Projektleitung: Prof. Dr. Stefan Kratsch

• Kernelization Lower Bounds by Cross-Composition

  2014

  SIAM Journal on Discrete Mathematics · DOI

  We introduce the framework of cross-composition for proving kernelization lower bounds. A classical problem $L$ \and/or-cross-composes into a parameterized problem $\mathcal{Q}$ if it is possible to efficiently construct an instance of $\mathcal{Q}$ with polynomially bounded parameter value that expresses the logical and or or of a sequence of instances of $L$. Building on work by Bodlaender et al. and using results of Fortnow and Santhanam, Dell and van Melkebeek, and Drucker, we show that if an NP-hard problem and/or-cross-composes into a parameterized problem $\mathcal{Q}$, then $\mathcal{Q}$ does not admit a polynomial kernel unless $\mbox{NP}\subseteq \mbox{coNP/poly}$ and the polynomial hierarchy collapses. Our technique generalizes and strengthens the techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (nonstandard) parameterizations, e.g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. We have similar lower bounds for Feedback Vertex Set and Odd Cycle Transversal under structural parameterizations. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of or-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size.

• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth