2023/07/05 by Stefan Kratsch, Kratsch, Stefan, Pascal Kunz +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Graph #Kernelization #Line graph #Mathematics #Parameterized complexity #Pathwidth #Time complexity #Treewidth #Vertex (graph theory) #Vertex cover #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2307.02241
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/07/05 · openalex created_date 2023/07/07 · openalex updated_date 2026/07/28
An α-approximate polynomial Turing kernelization is a polynomial-time algorithm that computes an (αc)-approximate solution for a parameterized optimization problem when given access to an oracle that can compute c-approximate solutions to instances with size bounded by a polynomial in the parameter. Hols et al. [ESA 2020] showed that a wide array of graph problems admit a (1+ε)-approximate polynomial Turing kernelization when parameterized by the treewidth of the graph and left open whether Dominating Set also admits such a kernelization. We show that Dominating Set and several related problems parameterized by treewidth do not admit constant-factor approximate polynomial Turing kernelizations, even with respect to the much larger parameter vertex cover number, under certain reasonable complexity assumptions.On the positive side, we show that all of them do have a (1+ε)-approximate polynomial Turing kernelization for every ε>0 for the joint parameterization by treewidth and maximum degree, a parameter which generalizes cutwidth, for example.