114 citations · 306 across the 50 of their papers we have counts for
4 papers · 1 filter
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…