## Abstract

We study the CONNECTED η-TREEDEPTH DELETION problem, where the input instance is an undirected graph G, and an integer k and the objective is to decide whether there is a vertex set S⊆V(G) such that |S|≤k, every connected component of G−S has treedepth at most η and G[S] is a connected graph. As this problem naturally generalizes the well-studied CONNECTED VERTEX COVER problem, when parameterized by the solution size k, CONNECTED η-TREEDEPTH DELETION is known to not admit a polynomial kernel unless NP⊆coNP/poly. This motivates the question of designing approximate polynomial kernels for this problem.

In this paper, we show that for every fixed 0

In this paper, we show that for every fixed 0

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

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 48th International Workshop, WG 2022 |

Editors | Michael A. Bekos, Michael Kaufmann |

Publisher | Springer |

Pages | 201-214 |

Number of pages | 14 |

ISBN (Electronic) | 978-3-031-15914-5 |

ISBN (Print) | 978-3-031-15913-8 |

DOIs | |

Publication status | Published - 1 Oct 2022 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 13453 |