Lossy Kernels for Connected Dominating Set on Sparse Graphs

Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad +2

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^{\prime },k^{\prime })$ (of…