2017/07/31 by Sebastian Siebertz, Siebertz, Sebastian
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.1707.09819
arXiv admin note: substantial text overlap with arXiv:1706.09339
arxiv created 2017/07/31 · arxiv updated 2018/02/23
For α\colonℕ→ℝ, an α-approximate bi-kernel is a polynomial-time algorithm that takes as input an instance (I, k) of a problem Q and outputs an instance (I',k') of a problem Q' of size bounded by a function of k such that, for every c≥ 1, a c-approximate solution for the new instance can be turned into a c⋅α(k)-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov et al. We prove that for every nowhere dense class of graphs, every α>1 and r∈ℕ there exists a polynomial p (whose degree depends only on r while its coefficients depend on α) such that the connected distance-r dominating set problem with parameter k admits an α-approximate bi-kernel of size p(k). Furthermore, we show that this result cannot be extended to more general classes of graphs which are closed under taking subgraphs by showing that if a class C is somewhere dense and closed under taking subgraphs, then for some value of r∈ℕ there cannot exist an α-approximate bi-kernel for the (connected) distance-r dominating set problem on C for any function α\colonℕ→ℝ (assuming the Gap Exponential Time Hypothesis).