Résumé
Let H be a graph class and k ∈ N. We say a graph G admits a k-identification to H if there is a partition P of some set X ⊆ V (G) of size at most k such that after identifying each part in P to a single vertex, the resulting graph belongs to H. The graph parameter id H is defined so that id H (G) is the minimum k such that G admits a k-identification to H, and the problem of Identification to H asks, given a graph G and k ∈ N, whether id H (G) ≤ k. If we set H to be the class F of acyclic graphs, we generate the problem Identification to Forest, which we show to be NP-complete. We prove that, when parameterized by the size k of the identification set, it admits a kernel of size 2k + 1. For our kernel we reveal a close relation of Identification to Forest with the Vertex Cover problem. We also study the combinatorics of the yes-instances of Identification to H, i.e., the class H (k) := {G | id H (G) ≤ k}, which we show to be minor-closed for every k when H is minor-closed. We prove that the minor-obstructions of F (k) are of size at most 2k + 4. We also prove that every graph G such that id F (G) is sufficiently big contains as a minor either a cycle on k vertices, or k disjoint triangles, or the k-marguerite graph, that is the graph obtained by k disjoint triangles by identifying one vertex of each of them into the same vertex.