Let be a graph class and . We say a graph admits a \emph{-identification to } if there is a partition of some set of size at most such that after identifying each part in to a single vertex, the resulting graph belongs to . The graph parameter is defined so that is the minimum such that admits a -identification to , and the problem of \textsc{Identification to $\mathcal{H}$} asks, given a graph and , whether . If we set to be the class of acyclic graphs, we generate the problem , which we show to be {\sf NP}-complete. We prove that, when parameterized by the size of the identification set, it admits a kernel of size . For our kernel we reveal a close relation of with the problem. We also study the combinatorics of the -instances of \textsc{Identification to $\mathcal{H}$}, i.e., the class , {which we show to be minor-closed for every } when is minor-closed. We prove that the minor-obstructions of are of size at most . We also prove that every graph such that is sufficiently big contains as a minor either a cycle on vertices, or disjoint triangles, or the \emph{-marguerite} graph, that is the graph obtained by disjoint triangles by identifying one vertex of each of them into the same vertex.

生成讲解博客的中文版本

生成AI智能校验的中文版本