Approximate Turing kernelization for problems parameterized by treewidth
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse · Journal of Computer and System Sciences · 2025
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 O ( 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 f that only depends on the parameter. Using this definition, we show that Independent Set parameterized by treewidth ℓ has a ( 1 + ε ) -approximate Turing kernelization with O ( ℓ 2 ε ) 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 .