Essentially tight kernels for (weakly) closed graphs

DOI10.1007/S00453-022-01088-7arXiv2103.03914OpenAlexW3133677238MaRDI QIDQ6103524

Author name not available (Why is that?)

Publication date: 5 June 2023

Published in: (Search for Journal in Brave)

Abstract: We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number $c$ and the weak closure number $gamma$ [Fox et al., SICOMP 2020] in addition to the standard parameter solution size $k$. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size $k^{mathcalO(gamma)}$ and $(gammak{)}^{mathcalO(gamma)}$, respectively, thus extending previous kernelization results on degenerate graphs. The kernels are essentially tight, since these problems are unlikely to admit kernels of size $k^{o(gamma)}$ by previous results on their kernelization complexity in degenerate graphs [Cygan et al., ACM TALG 2017]. In addition, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number~$c$ and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs.

Full work available at URL: https://arxiv.org/abs/2103.03914

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Essentially tight kernels for (weakly) closed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103524)