Approximate Turing kernelization for problems parameterized by treewidth

We extend the notion of lossy kernelization, introduced by Lokshtanov et al. (2017) 19, to approximate Turing kernelization. An α-approximate Turing kernelization for a parameterized optimization problem is a polynomial-time algorithm that, when given access to an oracle that outputs c-approximate solutions in 𝒪(1)time, computes an α·c approximate solution to the considered problem, using calls to the oracle of size at most f(k)for some function fthat only depends on the parameter. Using this definition, we show that Independent Set parameterized by treewidth ℓhas a (1+ε)-approximate Turing kernelization with 𝒪(ℓ²/ε)vertices, answering an open question posed by Lokshtanov et al. (2017) 19. Furthermore, we give (1+ε)-approximate Turing kernelizations for the following graph problems parameterized by treewidth: Vertex Cover, Edge Clique Cover, Edge-Disjoint Triangle Packing, and Connected Vertex Cover. We generalize the result for Independent Set and Vertex Cover by showing that all graph problems that we will call friendly admit (1+ε)-approximate Turing kernelizations of polynomial size when parameterized by treewidth. We use this to establish approximate Turing kernelizations for Vertex-Disjoint H-packing for connected graphs H, Clique Cover, Feedback Vertex Set, and Edge Dominating Set.