Essentially Tight Kernels for (Weakly) Closed Graphs
Tomohiro Koana, Christian Komusiewicz, Frank O. Sommer · Algorithmica · 2023
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 weak closure number $$\gamma $$ γ (Fox et al. SIAM J Comput 49(2):448–464, 2020) in addition to the standard parameter solution size k. The weak closure number $$\gamma $$ γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size $$k^{\mathcal {O}(\gamma )}$$ k O ( γ ) , $$k^{\mathcal {O}(\gamma )}$$ k O ( γ ) , and $$(\gamma k)^{\mathcal {O}(\gamma )}$$ ( γ k ) O ( γ ) , respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size $$k^{o(\gamma )}$$ k o ( γ ) by previous results on their kernelization complexity on degenerate graphs (Cygan et al. ACM Trans Algorithms 13(3):43:1–43:22, 2017). For Capacitated Vertex Cover, we show that even a kernel of size $$k^{o(c)}$$ k o ( c ) is unlikely. In contrast, for Connected Vertex Cover, we obtain a kernel with $$\mathcal {O}(ck^2)$$ O ( c k 2 ) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class $$\mathcal {G}$$ G admits a kernel of size $$k^{\mathcal {O}(\gamma )}$$ k O ( γ ) when $$\mathcal {G}$$ G contains all complete and all edgeless graphs. Finally, 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.