6 papers
A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
Stefan Kratsch
A large number of NP-hard graph problems can be solved in time and space when the input graph is provided together with a tree decomposition of width , in many ca…
Tight Bounds for Feedback Vertex Set Parameterized by Clique-width
Narek Bojikian, Stefan Kratsch
We introduce a new notion of acyclicity representation in labeled graphs, and present three applications thereof. Our main result is an algorithm that, given a graph and a -…
Boundaried Kernelization
Leonid Antipov, Stefan Kratsch
The notion of a (polynomial) kernelization from parameterized complexity is a well-studied model for efficient preprocessing for hard computational problems. By now, it is quite we…
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. M…
Tight Bounds for some Classical Problems Parameterized by Cutwidth
Narek Bojikian, Vera Chekan, Stefan Kratsch
Cutwidth is a widely studied parameter that quantifies how well a graph can be decomposed along small edge-cuts. It complements pathwidth, which captures decomposition by small ver…
Efficient parameterized approximation
Stefan Kratsch, Pascal Kunz
Many problems are NP-hard and, unless P = NP, do not admit polynomial-time exact algorithms. The fastest known exact algorithms exactly usually take time exponential in the input s…