Answers are grounded in this paper and cite their sources.
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 .
No takes yet. Share an insight, caveat, or question.
Hols et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: