Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
arxiv(2024)
摘要
For a fixed graph H, the H-SUBGRAPH HITTING problem consists in deleting
the minimum number of vertices from an input graph to obtain a graph without
any occurrence of H as a subgraph. This problem can be seen as a
generalization of VERTEX COVER, which corresponds to the case H = K_2. We
initiate a study of H-SUBGRAPH HITTING from the point of view of
characterizing structural parameterizations that allow for polynomial kernels,
within the recently active framework of taking as the parameter the number of
vertex deletions to obtain a graph in a "simple" class C. Our main
contribution is to identify graph parameters that, when H-SUBGRAPH HITTING is
parameterized by the vertex-deletion distance to a class C where any of these
parameters is bounded, and assuming standard complexity assumptions and that
H is biconnected, allow us to prove the following sharp dichotomy: the
problem admits a polynomial kernel if and only if H is a clique. These new
graph parameters are inspired by the notion of C-elimination distance
introduced by Bulian and Dawar [Algorithmica 2016], and generalize it in two
directions. Our results also apply to the version of the problem where one
wants to hit H as an induced subgraph, and imply in particular, that the
problems of hitting minors and hitting (induced) subgraphs have a substantially
different behavior with respect to the existence of polynomial kernels under
structural parameterizations.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要