114 citations · 306 across the 50 of their papers we have counts for
47 papers · 1 filter
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…
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…
On polynomial kernelization for Stable Cutset
Stefan Kratsch, Van Bang Le
A stable cutset in a graph is a set such that vertices of are pairwise non-adjacent and such that is disconnected, i.e., it is both stable (or indep…