Prof. Dr. Stefan Kratsch

Profil

Zusammenfassung

Stefan Kratsch forscht zu effizienten Algorithmen für schwere Optimierungsprobleme, insbesondere zur Vorverarbeitung und Datenreduktion durch Kernelisierung. Er entwickelt theoretische Methoden, um zu beweisen, wann und wie sich Probleme effizient vereinfachen lassen, und kombiniert dabei Techniken aus der parametrisierten Komplexitätstheorie mit praktischen Algorithmen. Seine Arbeiten helfen zu verstehen, welche Grenzen es bei der automatischen Problemvereinfachung gibt und wie man diese Grenzen formal nachweist.

Skills

Name

Prof. Dr. Stefan Kratsch

Titel

Prof. Dr.

Fakultät

Mathematisch-Naturwissenschaftliche Fakultät

Institut

Institut für Informatik

Arbeitsgruppe

Algorithm Engineering

E-Mail

🔒 nur für eingeloggte sichtbarAnmelden

Telefon

🔒 nur für eingeloggte sichtbarAnmelden

HU-FIS-Profil

Quelle ↗

Zuletzt gescrapt

28.6.2026, 01:08:29

• GRK 2434/1: Facetten der Komplexität

  Quelle ↗

  Förderer: DFG Graduiertenkolleg Zeitraum: 04/2018 - 09/2022 Projektleitung: Prof. Dr. Nicole Schweikardt, Prof. Dr. Stefan Kratsch

• GRK 2434/3: Komplexität Auslauffinanzierung

  Quelle ↗

  Förderer: DFG Graduiertenkolleg Zeitraum: 10/2022 - 03/2024 Projektleitung: Prof. Dr. Stefan Kratsch

• Mehr als Kernelisierung – Mehr Allgemeinheit für effiziente Vorverarbeitung

  Quelle ↗

  Förderer: DFG Sachbeihilfe Zeitraum: 10/2023 - 08/2027 Projektleitung: Prof. Dr. Stefan Kratsch

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

• Kernelization Lower Bounds by Cross-Composition

  2014

  SIAM Journal on Discrete Mathematics · 230 Zitationen · 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

  2014

  Information and Computation · 178 Zitationen · DOI

• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

  2013

  Lecture notes in computer science · 145 Zitationen · DOI

• Freie Universität Berlin

  GRK 2434/1: Facetten der Komplexität

  university

• Technische Universität Berlin

  GRK 2434/1: Facetten der Komplexität

  university