Prof. Dr. Stefan Kratsch
Profil
Forschungsthemen6
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
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 /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/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
Mögliche Industrie-Partner10
Stand: 26.4.2026, 19:48:44 (Top-K=20, Min-Cosine=0.4)
- 128 Treffer61.0%
- Embodied Audition for RobotSP61.0%
- Embodied Audition for RobotS
- 137 Treffer57.4%
- Workshop Reliable Methods and Mathematical ModelingP57.4%
- Workshop Reliable Methods and Mathematical Modeling
- 84 Treffer57.3%
- Interfaces in opto-electronic thin film multilayer devicesP57.3%
- Interfaces in opto-electronic thin film multilayer devices
- 59 Treffer57.3%
- ILB: Entwicklung eines Produktions- und Pflanzverfahrens mit rohrförmigen WurzelhüllenP57.3%
- Entwicklung eines innovativen Kulturbegründungsverfahrens für Eichen zur Verbesserung der Wurzelentwicklung durch kompostierbare WurzelhüllenP49.8%
- ILB: Entwicklung eines Produktions- und Pflanzverfahrens mit rohrförmigen Wurzelhüllen
- 56 Treffer56.6%
- Gamification for Climate ActionP56.6%
- Gamification for Climate Action
- 48 Treffer56.0%
- Engineering of New-Generation Protein Secretion SystemsP56.0%
- Engineering of New-Generation Protein Secretion Systems
- 46 Treffer56.0%
- Engineering of New-Generation Protein Secretion SystemsP56.0%
- Engineering of New-Generation Protein Secretion Systems
- 47 Treffer56.0%
- Engineering of New-Generation Protein Secretion SystemsP56.0%
- Engineering of New-Generation Protein Secretion Systems
- 7 Treffer55.5%
- Zuwendung im Rahmen des Programms „exist – Existenzgründungen aus der Wissenschaft“ aus dem Bundeshaushalt, Einzelplan 09, Kapitel 02, Titel 68607, Haushaltsjahr 2026, sowie aus Mitteln des Europäischen Strukturfonds (hier Euro-päischer Sozialfonds Plus – ESF Plus) Förderperiode 2021-2027 – Kofinanzierung für das Vorhaben: „exist Women“T55.5%
- Zuwendung im Rahmen des Programms „exist – Existenzgründungen aus der Wissenschaft“ aus dem Bundeshaushalt, Einzelplan 09, Kapitel 02, Titel 68607, Haushaltsjahr 2026, sowie aus Mitteln des Europäischen Strukturfonds (hier Euro-päischer Sozialfonds Plus – ESF Plus) Förderperiode 2021-2027 – Kofinanzierung für das Vorhaben: „exist Women“
- 18 Treffer55.5%
- EU: Context Sensitive Multisensory Object Recognition (HBP)P55.5%
- EU: Context Sensitive Multisensory Object Recognition (HBP)
Publikationen25
Top 25 nach Zitationen — Quelle: OpenAlex (BAAI/bge-m3 embedded für Matching).
SIAM Journal on Discrete Mathematics · 229 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.
Information and Computation · 177 Zitationen · DOI
Lecture notes in computer science · 144 Zitationen · DOI
118 Zitationen · DOI
The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open problem in parameterized complexity. Recently, this was settled by the present authors (Kratsch and Wahlstrom, SODA 2012), with a randomized polynomial kernel for the problem, using matroid theory to encode How questions over a set of terminals in size polynomial in the number of terminals (rather than the total graph size, which may be superpolynomially larger). In the current work we further establish the usefulness of matroid theory to kernelization by showing applications of a result on representative sets due to Lovasz (Combinatorial Surveys 1977) and Marx (TCS 2009). We show how representative sets can be used to give a polynomial kernel for the elusive Almost 2-sat problem (where the task is to remove at most k clauses to make a 2-CNF formula satisfiable), solving a major open problem in kernelization. We further apply the representative sets tool to the problem of finding irrelevant vertices in graph cut problems, that is, vertices which can be made undeletable without affecting the status of the problem. This gives the first significant progress towards a polynomial kernel for the Multiway Cut problem; in particular, we get a polynomial kernel for Multiway Cut instances with a bounded number of terminals. Both these kernelization results have significant spin-off effects, producing the first polynomial kernels for a range of related problems. More generally, the irrelevant vertex results have implications for covering min-cuts in graphs. In particular, given a directed graph and a set of terminals, we can find a set of size polynomial in the number of terminals (a cut-covering set) which contains a minimum vertex cut for every choice of sources and sinks from the terminal set. Similarly, given an undirected graph and a set of terminals, we can find a set of vertices, of size polynomial in the number of terminals, which contains a minimum multiway cut for every partition of the terminals into a bounded number of sets. Both results are polynomial time. We expect this to have further applications; in particular, we get direct, reduction rule-based kernelizations for all problems above, in contrast to the indirect compression-based kernel previously given for Odd Cycle Transversal. All our results are randomized, with failure probabilities which can be made exponentially small in the size of the input, due to needing a representation of a matroid to apply the representative sets tool.
arXiv (Cornell University) · 116 Zitationen · DOI
We introduce a new technique for proving kernelization lower bounds, called cross-composition. A classical problem L cross-composes into a parameterized problem Q if an instance of Q with polynomially bounded parameter value can express the logical OR of a sequence of instances of L. Building on work by Bodlaender et al. (ICALP 2008) and using a result by Fortnow and Santhanam (STOC 2008) we show that if an NP-complete problem cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless the polynomial hierarchy collapses. Our technique generalizes and strengthens the recent techniques of using OR-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 (non-standard) parameterizations, e.g., Chromatic Number, Clique, and Weighted Feedback Vertex Set 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.
Journal of Computer and System Sciences · 99 Zitationen · DOI
Algorithmica · 88 Zitationen · DOI
ACM Transactions on Algorithms · 85 Zitationen · DOI
The Odd Cycle Transversal problem (OCT) asks whether a given undirected graph can be made bipartite by deleting at most k of its vertices. In a breakthrough result, Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a O (4 k kmn) time algorithm for it; this also implies that instances of the problem can be reduced to a so-called problem kernel of size O (4 k ). Since then, the existence of a polynomial kernel for OCT (i.e., a kernelization with size bounded polynomially in k ) has turned into one of the main open questions in the study of kernelization, open even for the special case of planar input graphs. This work provides the first (randomized) polynomial kernelization for OCT. We introduce a novel kernelization approach based on matroid theory, where we encode all relevant information about a problem instance into a matroid with a representation of size polynomial in k . This represents the first application of matroid theory to kernelization.
Algorithmica · 81 Zitationen · DOI
In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We consider two different measures for the problem. The first measure is a very natural multi-objective one for the use of evolutionary algorithms and takes into account the number of chosen vertices and the number of edges that remain uncovered. The second fitness function is based on a linear programming formulation and proves to give better results. We point out that both approaches lead to a kernelization for the Vertex Cover problem. Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e., the expected runtime is bounded by O(f(OPT)⋅n c ), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem.
Theoretical Computer Science · 73 Zitationen · DOI
Discrete Optimization · 67 Zitationen · DOI
65 Zitationen
Kernelization is a formalization of efficient preprocessing, aimed mainly at combinatorially hard problems. Empirically, preprocessing is highly suc-cessful in practice, e.g., in state-of-the-art SAT and ILP solvers. The notion of kernelization from parameterized complexity makes it possible to rigor-ously prove upper and lower bounds on, e.g., the maximum output size of a preprocessing in terms of one or more problem-specific parameters. This avoids the often-raised issue that we should not expect an efficient algorithm that provably shrinks every instance of any NP-hard problem. In this survey, we give a general introduction to the area of kernelization and then discuss some recent developments. After the introductory material we attempt a reasonably self-contained update and introduction on the fol-lowing topics: (1) Lower bounds for kernelization, taking into account the recent progress on the and-conjecture. (2) The use of matroids and repre-sentative sets for kernelization. (3) Turing kernelization, i.e., understanding preprocessing that adaptively or non-adaptively creates a large number of small outputs. 1
ACM Transactions on Computation Theory · 64 Zitationen · DOI
The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the polynomial hierarchy collapses to its third level, the following parameterized problems do not admit a polynomial-time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter: ---Edge Clique Cover, parameterized by the number of cliques, ---Directed Edge/Vertex Multiway Cut, parameterized by the size of the cutset, even in the case of two terminals, ---Edge/Vertex Multicut, parameterized by the size of the cutset, and --- k -Way Cut, parameterized by the size of the cutset.
Point Line Cover
2016ACM Transactions on Algorithms · 52 Zitationen · DOI
The input to the NP-hard point line cover problem (PLC) consists of a set P of n points on the plane and a positive integer k ; the question is whether there exists a set of at most k lines that pass through all points in P . By straightforward reduction rules, one can efficiently reduce any input to one with at most k 2 points. We show that this easy reduction is already essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, for any ϵ > 0, there is no polynomial-time algorithm that reduces every instance ( P , k ) of PLC to an equivalent instance with O ( k 2 −ϵ) points. This answers, in the negative, an open problem posed by Lokshtanov [2009]. Our proof uses the notion of a kernel from parameterized complexity, and the machinery for deriving lower bounds on the size of kernels developed by Dell and van Melkebeek [2010, 2014]. It has two main ingredients: We first show, by reduction from vertex cover , that—unless the polynomial hierarchy collapses—PLC has no kernel of total size O ( k 2 −ϵ) bits. This does not directly imply the claimed lower bound on the number of points , since the best-known polynomial-time encoding of a PLC instance with n points requires ω( n 2 ) bits. To get around this hurdle, we build on work of Alon [1986] and devise an oracle communication protocol of cost O ( n log n ) for PLC. This protocol, together with the lower bound on the total size (which also holds for such protocols), yields the stated lower bound on the number of points. While a number of essentially tight polynomial lower bounds on total sizes of kernels are known, our result is—to the best of our knowledge—the first to show a nontrivial lower bound for structural/secondary parameters. It is also the first example of a lower bound for kernelization that makes use of the full power of the oracle communication protocol lower bounds that can be obtained from the work of Dell and van Melkebeek. We combine the main abstract ideas of our proof to derive a general recipe that could be used to obtain such lower bounds for other problems with unknown or insufficiently strong encodings.
51 Zitationen · DOI
For an even integer t ≥ 2, the Matching Connectivity matrix Ht is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph Kt on t vertices; an entry Ht[M1,M2] is 1 if M1∪ M2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of Ht: We first show that Ht has rank exactly 2t/2-1 over GF(2) via an appropriate factorization that explicitly provides families of matchings Xt forming bases for Ht. Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings Xt induce permutation matrices within Ht. We use the factorization to derive an 1.888n nO(1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles modulo two in directed bipartite or undirected graphs in the same time bound. Moreover, we use the fast basis change algorithm from the second result to present a Monte Carlo algorithm that given an undirected graph on n vertices along with a path decomposition of width at most pw decides Hamiltonicity in (2+√2)pw nO(1) time. Finally, we use the third result to show that for every ε >0 this cannot be improved to (2+√2-ε)pwnO(1) time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of an O((2-ε')n) time algorithm for CNF-Sat.
Information and Computation · 49 Zitationen · DOI
Journal of Computer and System Sciences · 48 Zitationen · DOI
ACM Transactions on Algorithms · 44 Zitationen · DOI
The field of kernelization offers a rigorous way of studying the ubiquitous technique of data reduction and preprocessing for combinatorially hard problems. A widely accepted definition of useful data reduction is that of a polynomial kernelization where the output instance is guaranteed to be of size polynomial in some parameter of the input. The fairly recent development of a framework for kernelization lower bounds has made this notion even more attractive as we can now classify many problems into admitting or not admitting polynomial kernelizations. The central notion of the framework is that of a polynomial-time composition algorithm due to Bodlaender et al. (ICALP 2008, JSCC 2009): given t input instances, an or -composition algorithm returns a single-output instance with bounded parameter value that is yes if and only if one of t input instances is yes; it encodes the logical OR of the input instances. Based on a result of Fortnow and Santhanam (STOC 2008, JSCC 2011), Bodlaender et al. show that an or -composition for an NP-hard problem rules out polynomial kernelizations for it unless NP ⊆ coNP/poly (which is known to imply a collapse of the polynomial hierarchy). It is implicit in the work of Fortnow and Santhanam that even co-nondeterministic composition algorithms suffice to rule out polynomial kernelizations. This was first observed in unpublished work of Chen and Müller, and it is an explicit conclusion of recent results by Dell and van Melkebeek (STOC 2010). However, in contrast to the numerous applications of deterministic composition, the added power of co-nondeterminism has not yet been harnessed to obtain kernelization lower bounds. In this work, we present the first example of how co-nondeterminism can help to make a composition algorithm. We study the existence of polynomial kernels for a Ramsey-type problem where, given a graph G and an integer k , the question is whether G contains an independent set or a clique of size at least k . It was asked by Rod Downey whether this problem admits a polynomial kernelization with respect to k ; such a result would greatly speed up the computation of Ramsey numbers. We provide a co-nondeterministic composition based on embedding t instances into a single host graph H . The crux is that the host graph H needs to observe a bound of ℓ ∈ O (log t ) on both its maximum independent set and maximum clique size, while also having a cover of its vertex set by independent sets and cliques all of size ℓ; the co-nondeterministic composition is built around the search for such graphs. Thus, we show that, unless NP ⊆ coNP/poly, the problem does not admit a kernelization with polynomial size guarantee.
Journal of the ACM · 41 Zitationen · DOI
For an even integer t ≥ 2, the Matching Connectivity matrix H t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph on t vertices; an entry H t [ M 1 , M 2 ] is 1 if M 1 and M 2 form a Hamiltonian cycle and 0 otherwise. Motivated by applications for the Hamiltonicity problem, we show that H t has rank exactly 2 t /2−1 over GF(2). The upper bound is established by an explicit factorization of H t as the product of two submatrices; the matchings labeling columns and rows, respectively, of the submatrices therefore form a basis X t of H t . The lower bound follows because the 2 t /2−1 × 2 t /2−1 submatrix with rows and columns labeled by X t can be seen to have full rank. We obtain several algorithmic results based on the rank of H t and the particular structure of the matchings in X t . First, we present a 1.888 n n O (1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Second, we give a Monte Carlo algorithm that solves the problem in (2 + √ 2) pw n O (1) time when provided with a path decomposition of width pw for the input graph. Moreover, we show that this algorithm is best possible under the Strong Exponential Time Hypothesis, in the sense that an algorithm with running time (2 + √2 − ϵ) pw n O (1) , for any ϵ > 0, would imply the breakthrough result of a (2 − ϵ ′ ) n -time algorithm for CNF-Sat for some ϵ ′ > 0.
Journal of the ACM · 40 Zitationen · DOI
We continue the development of matroid-based techniques for kernelization, initiated by the present authors [47]. We significantly extend the usefulness of matroid theory in kernelization by showing applications of a result on representative sets due to Lovász [51] and Marx [53]. As a first result, we show how representative sets can be used to derive a polynomial kernel for the elusive ALMOST 2- SAT problem (where the task is to remove at most k clauses to make a 2- CNF formula satisfiable), solving a major open problem in kernelization. This result also yields a new O(√log OPT)-approximation for the problem, improving on the O(√log n)-approximation of Agarwal et al. [3] and an implicit O(log OPT)-approximation due to Even et al. [24]. We further apply the representative sets tool to the problem of finding irrelevant vertices in graph cut problems, that is, vertices that can be made undeletable without affecting the answer to the problem. This gives the first significant progress towards a polynomial kernel for the MULTIWAY CUT problem; in particular, we get a kernel of O( k s+1 ) vertices for MULTIWAY CUT instances with at most s terminals. Both these kernelization results have significant spin-off effects, producing the first polynomial kernels for a range of related problems. More generally, the irrelevant vertex results have implications for covering min cuts in graphs. For a directed graph G=(V,E) and sets S, T ⊆ V , let r be the size of a minimum ( S,T )-vertex cut (which may intersect S and T ). We can find a set Z ⊆ V of size O(|S| . |T| . r) that contains a minimum ( A,B )-vertex cut for every A ⊆ S , B ⊆ T . Similarly, for an undirected graph G=(V,E) , a set of terminals X ⊆ V , and a constant s , we can find a set Z ⊆ V of size O(|X| s+1 ) that contains a minimum multiway cut for every partition of X into at most s pairwise disjoint subsets. Both results are polynomial time. We expect this to have further applications; in particular, we get direct, reduction rule-based kernelizations for all problems above, in contrast to the indirect compression-based kernel previously given for ODD CYCLE TRANSVERSAL [47]. All our results are randomized, with failure probabilities that can be made exponentially small in n , due to needing a representation of a matroid to apply the representative sets tool.
SIAM Journal on Discrete Mathematics · 40 Zitationen · DOI
The Multicut problem, given a graph G, a set of terminal pairs $\mathcal{T}=\{(s_i,t_i)\ |\ 1\leq i\leq r\}$, and an integer $p$, asks whether one can find a cutset consisting of at most $p$ nonterminal vertices that separates all the terminal pairs, i.e., after removing the cutset, $t_i$ is not reachable from $s_i$ for each $1\leq i\leq r$. The fixed-parameter tractability of Multicut in undirected graphs, parameterized by the size of the cutset only, has been recently proved by Marx and Razgon [SIAM J. Comput., 43 (2014), pp. 355--388] and, independently, by Bousquet, Daligault, and Thomassé [Proceedings of STOC, ACM, 2011, pp. 459--468], after resisting attacks as a long-standing open problem. In this paper we prove that Multicut is fixed-parameter tractable on directed acyclic graphs when parameterized both by the size of the cutset and the number of terminal pairs. We complement this result by showing that this is implausible for parameterization by the size of the cutset only, as this version of the problem remains $W[1]$-hard.
Journal of Artificial Intelligence Research · 40 Zitationen · DOI
Assume that each of n voters may or may not approve each of m issues. If an agent (the lobby) may influence up to k voters, then the central question of the NP-hard Lobbying problem is whether the lobby can choose the voters to be influenced so that as a result each issue gets a majority of approvals. This problem can be modeled as a simple matrix modification problem: Can one replace k rows of a binary n x m-matrix by k all-1 rows such that each column in the resulting matrix has a majority of 1s? Significantly extending on previous work that showed parameterized intractability (W[2]-completeness) with respect to the number k of modified rows, we study how natural parameters such as n, m, k, or the "maximum number of 1s missing for any column to have a majority of 1s" (referred to as "gap value g") govern the computational complexity of Lobbying. Among other results, we prove that Lobbying is fixed-parameter tractable for parameter m and provide a greedy logarithmic-factor approximation algorithm which solves Lobbying even optimally if m < 5. We also show empirically that this greedy algorithm performs well on general instances. As a further key result, we prove that Lobbying is LOGSNP-complete for constant values g>0, thus providing a first natural complete problem from voting for this complexity class of limited nondeterminism.
Lecture notes in computer science · 40 Zitationen · DOI
Lecture notes in computer science · 38 Zitationen · DOI
Lecture notes in computer science · 34 Zitationen · DOI
Kooperationen2
Bestätigte Forscher↔Partner-Paare aus HU-FIS — Gold-Standard-Positive für das Matching.
GRK 2434/1: Facetten der Komplexität
university
GRK 2434/1: Facetten der Komplexität
university
Stammdaten
Identität, Organisation und Kontakt aus HU-FIS.
- Name
- Prof. Dr. Stefan Kratsch
- Titel
- Prof. Dr.
- Fakultät
- Mathematisch-Naturwissenschaftliche Fakultät
- Institut
- Institut für Informatik
- Arbeitsgruppe
- Algorithm Engineering
- Telefon
- +49 30 2093-41232
- HU-FIS-Profil
- Quelle ↗
- Zuletzt gescrapt
- 26.4.2026, 01:08:01