**Lossy Kernels for Connected Dominating Set on Sparse Graphs.** / Eiben, Eduard; Kumar, Mithilesh; Mouawad, Amer E.; Panolan, Fahad; Siebertz, Sebastian.

Research output: Contribution to journal › Article › peer-review

Published

- http://arxiv.org/abs/1706.09339
Accepted author manuscript

For $\alpha > 1$, an $\alpha$-approximate (bi)kernel is a polynomial-time algorithm that takes as input an instance $(I, k)$ of a problem $\mathcal{Q}$ and outputs an instance $(I',k')$ (of a problem $\mathcal{Q}'$) of size bounded by a function of $k$ such that, for every $c\geq 1$, a $c$-approximate solution for the new instance can be turned into a $(c\cdot\alpha)$-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov and co-authors. We study Connected Dominating Set (and its distance-$r$ variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every $\alpha>1$, Connected Dominating Set admits a polynomial-size $\alpha$-approximate (bi)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on $2$-degenerate graphs and graphs of bounded expansion, unless ${NP} \subseteq \textsf{coNP/poly}$. We complement our results by the following conditional lower bound. We show that if a class $\mathcal{C}$ is somewhere dense and closed under taking subgraphs, then for some value of $r\in \mathbb{N}$ there cannot exist an $\alpha$-approximate bi-kernel for the (Connected) Distance-$r$ Dominating Set problem on $\mathcal{C}$ for any $\alpha>1$ (assuming ${FPT}\neq{W}[1]$).

Original language | English |
---|---|

Pages (from-to) | 1743-1771 |

Number of pages | 29 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 33 |

Issue number | 3 |

DOIs | |

Publication status | Published - 26 Sep 2019 |

This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 39381317