Approximate Turing Kernelization for Problems Parameterized by Treewidth

Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse

We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An $\alpha$-approximate Turing kernel for a parameterized…