114 citations · 306 across the 50 of their papers we have counts for
20 papers · 1 filter
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1
We study the parameterized problem of satisfying ``almost all'' constraints of a given formula over a fixed, finite Boolean constraint language , with or without weights. Mo…
Towards exact structural thresholds for parameterized complexity
Falko Hegerfeld, Stefan Kratsch
Parameterized complexity seeks to use input structure to obtain faster algorithms for NP-hard problems. This has been most successful for graphs of low treewidth: Many problems adm…
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for N…
Assessing the Computational Complexity of Multi-Layer Subgraph Detection
Robert Bredereck, Christian Komusiewicz, Stefan Kratsch +3
Multi-layer graphs consist of several graphs (layers) over the same vertex set. They are motivated by real-world problems where entities (vertices) are associated via multiple type…
The Parameterized Complexity of the Minimum Shared Edges Problem
Till Fluschnik, Stefan Kratsch, Rolf Niedermeier +1
We study the NP-complete Minimum Shared Edges (MSE) problem. Given an undirected graph, a source and a sink vertex, and two integers p and k, the question is whether there are p pa…
Polynomial Kernels for Weighted Problems
Michael Etscheid, Stefan Kratsch, Matthias Mnich +1
Kernelization is a formalization of efficient preprocessing for NP-hard problems using the framework of parameterized complexity. Among open problems in kernelization it has been a…