Essentially Tight Kernels For (Weakly) Closed Graphs
| Autor: | Tomohiro Koana, Christian Komusiewicz, Frank Sommer |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Ramsey numbers General Computer Science Applied Mathematics Theory of computation ��� Graph algorithms analysis Independent Set Induced Matching Dominating Set c-closure Connected Vertex Cover Computer Science Applications weak ��-closure Fixed-parameter tractability Computer Science - Data Structures and Algorithms kernelization Data Structures and Algorithms (cs.DS) Theory of computation ��� Parameterized complexity and exact algorithms MathematicsofComputing_DISCRETEMATHEMATICS |
| DOI: | 10.4230/lipics.isaac.2021.35 |
| Popis: | 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 �� [Fox et al., SICOMP 2020] in addition to the standard parameter solution size k. The weak closure number �� 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^����(��), k^����(��), and (��k)^����(��), 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(��) by previous results on their kernelization complexity in degenerate graphs [Cygan et al., ACM TALG 2017]. For Capacitated Vertex Cover, we show that even a kernel of size k^o(c) is unlikely. In contrast, for Connected Vertex Cover, we obtain a problem kernel with ����(ck��) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class ���� admits a kernel of size k^����(��) when ���� 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. LIPIcs, Vol. 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021), pages 35:1-35:15 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|