Vertex identification to a forest

Laure Morelle, Ignasi Sau, Dimitrios Thilikos

► To cite this version:

Laure Morelle, Ignasi Sau, Dimitrios Thilikos. Vertex identification to a forest. Discrete Mathematics, 2026, 349 (1), pp.114699. 10.1016/j.disc.2025.114699. lirmm-05386273

HAL Id: lirmm-05386273

https://hal-lirmm.ccsd.cnrs.fr/lirmm-05386273v1

Submitted on 27 Nov 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Vertex identification to a forest*

Laure Morelle†

Ignasi Sau†

Dimitrios M. Thilikos†

September 16, 2024

**Abstract**

Let $\mathcal{H}$ be a graph class and $k \in \mathbb{N}$. We say a graph $G$ admits a $k$-identification to $\mathcal{H}$ if there is a partition $\mathcal{P}$ of some set $X \subseteq V(G)$ of size at most $k$ such that after identifying each part in $\mathcal{P}$ to a single vertex, the resulting graph belongs to $\mathcal{H}$. The graph parameter $\text{id}_{\mathcal{H}}$ is defined so that $\text{id}_{\mathcal{H}}(G)$ is the minimum $k$ such that $G$ admits a $k$-identification to $\mathcal{H}$, and the problem of IDENTIFICATION TO $\mathcal{H}$ asks, given a graph $G$ and $k \in \mathbb{N}$, whether $\text{id}_{\mathcal{H}}(G) \le k$. If we set $\mathcal{H}$ to be the class $\mathcal{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 $\mathcal{H}$, i.e., the class $\mathcal{H}^{(k)} := \{G \mid \text{id}_{\mathcal{H}}(G) \le k\}$, which we show to be minor-closed for every $k$ when $\mathcal{H}$ is minor-closed. We prove that the minor-obstructions of $\mathcal{F}^{(k)}$ are of size at most $2k+4$. We also prove that every graph $G$ such that $\text{id}_{\mathcal{F}}(G)$ is sufficiently big contains as a minor either a cycle on $k$ vertices, or $k$ disjoint triangles, or the $k$-marquerite graph, that is the graph obtained by $k$ disjoint triangles by identifying one vertex of each of them into the same vertex.

**Keywords.** Vertex identification, Forests, Vertex Cover, Graph minors, Parameterized Algorithms, Kernelization, Obstructions, Universal Obstructions.

# 1 Introduction

A considerable part of parameterized algorithms has been dedicated to the study of *graph modification problems*. The general scheme for a graph modification problem consists of some modification operation, accompanied by some a measure on the “cost” of this modification, and a target property. The question is, given a graph $G$ and a non-negative integer $k$, whether it is possible to apply to $G$ a modification operation with cost at most $k$ so that the resulting graph has the target property. A graph modification problem can be seen as a way to define some notion of “distance from triviality” [13], where the distance is expressed by the measure of the modification operation and the triviality is expressed by the target class. Most graph modification problems are known to be NP-complete [20, 31]. A well-studied graph modification operation is vertex deletion and the most

<footnote>*The first and the third author were supported by the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027) and the Franco-Norwegian project PHC AURORA 2024 (Projet n° 51260WL). The second author was supported by ANR project ELIT (ANR-20-CE48-0008).</footnote>

<footnote>†LIRMM, Université de Montpellier, CNRS, Montpellier, France. Emails: laure.morelle@lirmm.fr, ignasi.sau@lirmm.fr, sedthilk@thilikos.info.</footnote>
typical measure is the number of vertices to be deleted. A general family of problems of this type is $\mathcal{H}$-DELETION where $\mathcal{H}$ is a graph class and where we look for a vertex set $S \subseteq V(G)$ of at most $k$ vertices such that $G-S$ is a graph in $\mathcal{H}$. There are many problems that can be expressed in this way and also many results identifying instantiations of $\mathcal{H}$ where $\mathcal{H}$-DELETION, parameterized by $k$, admits a fixed-parameter algorithm (in short FPT-algorithm), that is, an algorithm running in time $f(k) \cdot |G|^{O(1)}$, for some function $f$. Two of the most classical and widely studied problems of this type are VERTEX COVER, where $\mathcal{H}$ is the class of edgeless graphs, and FEEDBACK VERTEX SET, where $\mathcal{H}$ is the class of acyclic graphs. Alternative measures of the vertex removal modification have been considered in [9] (see also [30]).

Another line of research on modification problems is to consider other modification operations. Such operations may include edge removals or additions (see [5] for an extended survey), edge contractions [14, 15], or other modification operations such as subgraph complementations [12]. We should stress that the existing results on the parameterized complexity of such alternative modification operations are also many but not as abundant as in the case of vertex deletion.

Another modification operation called *vertex fusion* was introduced in [4]. The vertex fusion of a vertex set $S$ in a graph $G$ consists in deleting $S$ from $G$ and adding instead a new vertex $s$ adjacent to every vertex of $G-S$ that was adjacent to a vertex of $S$. In other words, the set $S$ is fused (or identified, using our terminology) to a single vertex $s$. This setting has real life applications. Indeed, consider a communication network represented by a graph $G$. The goal is that the vertices communicate as fast as possible through the edges of $G$. A natural problem is hence to ask whether it is possible to perform a small amount of modification to $G$ so that its diameter becomes small. Usually, the modification considered to reduce the diameter of a graph is to add edges. Instead, this article [4] proposes the vertex fusion operation. Such a fusion corresponds to adding a new, more modern and perhaps more expansive, communication network on a small vertex set $S$ that would allow for instantaneous (or just much faster) communication among the nodes in $S$. The authors prove that, given a graph $G$ and $k, d \in \mathbb{N}$, asking for a set of size $S$ at most $k$ whose fusion gives a graph of diameter (or radius or eccentricity) at most $d$ is NP-complete, and $W[1]$-hard parameterized by $k$.

**Identification to a graph property.** In this paper, we reinitiate a study of vertex fusion in a more general setting, and call our modification operation *vertex identification*.

We use $\mathcal{G}_{\text{all}}$ for the class of all graphs. Let $\mathcal{H} \subseteq \mathcal{G}_{\text{all}}$ be some graph class, expressing some graph property. We say that a graph $G$ admits a $k$-identification to $\mathcal{H}$ if there is a partition $\mathcal{P} = \{S_1, \dots, S_r\}$ of some subset $S$ of $k$ vertices of $G$ such that if, for every $i \in [r]$, we identify the vertices of $S_i$ to a single vertex, we obtain a graph in $\mathcal{H}$ (this operation is defined more formally in Subsection 2.2). That way, $k$-identification to $\mathcal{H}$ defines a measure of “distance from triviality” from the property $\mathcal{H}$. Note that the fusion operation of [4] corresponds to the particular case of our operation where the partition consists of a single set. This gives rise to the graph parameter $\text{id}_{\mathcal{H}} : \mathcal{G}_{\text{all}} \to \mathbb{N}$ where, given a graph $G$, $\text{id}_{\mathcal{H}}(G)$ is the minimum $k$ for which $G$ admits a $k$-identification to $\mathcal{H}$. The general problem is the following.

IDENTIFICATION TO $\mathcal{H}$

Input: A graph $G$ and $k \in \mathbb{N}$.

Question: Does $G$ admit a $k$-identification to $\mathcal{H}$?

We say that $G$ admits an *identification to $\mathcal{H}$* if it admits a $k$-identification to $\mathcal{H}$ for some $k \in \mathbb{N}$.
Although we will not dwell on the subject, those familiar with quotient graphs or homomorphisms may observe the following equivalence: $G$ admits an identification to $\mathcal{H}$ if and only if $G$ admits a quotient graph that belongs to $\mathcal{H}$ if and only if there is a surjective homomorphism from $G$ to a graph in $\mathcal{H}$ (sometimes called $\mathcal{H}$-coloring [2]). However, we are not aware of any optimization version of graph homomorphism (or graph quotient) to a fixed graph class that would fit our setting.

Suppose now that $\mathcal{H}$ is some minor-closed property, i.e., $\mathcal{H}$ contains all minors<fnref n="1" /> of its graphs. We also denote by $\text{obs}(\mathcal{H})$ the set of minor-minimal graphs that do not belong to $\mathcal{H}$ and observe that $G \in \mathcal{G}$ iff $G$ does not contain as a minor any of the graphs in $\text{obs}(\mathcal{H})$. We call the graphs in $\text{obs}(\mathcal{H})$ the minor obstructions of $\mathcal{H}$. Keep also in mind that, according to Robertson and Seymour's theorem [26], if $\mathcal{H}$ is minor-closed, then $\text{obs}(\mathcal{H})$ is finite. Also, according to [25, 27, 28], checking whether a graph $H$ is a minor of a graph $G$ can be done in time<fnref n="2" /> $O_{|H|}(|G|^3)$. This running time has been improved in [17] to a quadratic one and very recently in [18] to an almost linear one, i.e., $O_{|H|}(|G|^{1+\varepsilon})$.

Our first observation is that the minor-closedness of $\mathcal{H}$ implies that, for every $k \in \mathbb{N}$, the graph class $\mathcal{H}^{(k)} := \{G \mid \text{id}_{\mathcal{H}}(G) \le k\}$ is also minor-closed (Lemma 1). Therefore, because of the aforementioned results, for every minor-closed $\mathcal{H}$, the problem IDENTIFICATION TO $\mathcal{H}$ admits an FPT-algorithm, in particular, an algorithm running in time $O_k(|G|^{1+\varepsilon})$. Note that this does not contradict the $W[1]$-hardness result of [4] (even if the model is not the same) because the class of graphs of diameter at most $d$ is not minor-closed. Unfortunately, given that we have no upper bound on the size of the set $\text{obs}(\mathcal{H}^{(k)})$, the parametric dependence hidden in the "$O_k$" notation is not constructive. Actually, it can become constructive because of the recent results in [29]. However, this dependence still remains huge and it is an open challenge to design FPT-algorithms with reasonable parametric dependencies for particular instantiations of $\mathcal{H}$. As a first step in this direction, we consider the problem IDENTIFICATION TO FOREST, that is, IDENTIFICATION TO $\mathcal{H}$ where $\mathcal{H}$ is the class $\mathcal{F}$ of acyclic graphs. Note that this is the first non-trivial natural minor-closed class that one may consider, as if we take $\mathcal{H}$ to be the class of edgeless graphs, then the problem can be trivially solved in polynomial time. As we observe in Section 3, IDENTIFICATION TO FOREST is an NP-complete problem (see Lemma 6).

A problem that is similar to IDENTIFICATION TO FOREST is CONTRACTION TO FOREST, asking whether it is possible to contract $k$ edges in a graph $G$ so to obtain an acyclic graph. According to the results by Heggernes, van 't Hof, Lokshtanov, and Paul in [14], this problem can be solved in time $4.98^k \cdot |G|^{O(1)}$. As edge contractions are special cases of vertex identifications, if $(G, k)$ is a yes-instance of CONTRACTION TO FOREST then $(G, 2k)$ is also a yes-instance of IDENTIFICATION TO FOREST. However, vertex identifications may not be edge contractions, and it is certainly possible that a yes-instance of IDENTIFICATION TO FOREST is certified by the identifications of non-adjacent vertices that cannot be simulated by a small number of edge contractions. More generally, if $\mathcal{H}$ is some minor-closed graph class and $\mathcal{H}^{[k]}$ is the set of all graphs containing an edge set of size at most $k$ whose contraction creates a graph in $\mathcal{H}$, then $\mathcal{H}^{[k]}$ is not necessarily a minor-closed graph class, for any $k \ge 1$ (see Section 6). This indicates that the identification operation behaves better than the contraction operation from the structural point of view, and this motivates the definition and study of IDENTIFICATION TO $\mathcal{H}$ for minor-closed $\mathcal{H}$'s. To the authors' knowledge, no study of IDENTIFICATION TO $\mathcal{H}$ has been done from the parameterized complexity point of view, for any instantiation of $\mathcal{H}$.

<footnote n="1">¹A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from a subgraph of $G$ after contracting edges.</footnote>

<footnote n="2">²Given two functions $\chi, \psi: \mathbb{N} \to \mathbb{N}$, we write $\chi(n) = O_x(\psi(n))$ to denote that there exists a computable function $f: \mathbb{N} \to \mathbb{N}$ such that $\chi(n) = O(f(x) \cdot \psi(n))$.</footnote>
**A linear kernel.** Our first result is to prove that IDENTIFICATION TO FOREST admits a linear kernel of size $2k + 1$. In formal terms, we prove the following:

**Theorem 1.** There is an algorithm that, given an instance $(G, k)$ of IDENTIFICATION TO FOREST, outputs in polynomial time an equivalent instance $(G', k')$ where $|G'| \le 2k + 1$ and $k' \le k + 1$.

The algorithm of Theorem 1 is based on a structural result revealing a strong connection between IDENTIFICATION TO FOREST and the VERTEX COVER problem. We use `idf` as a shortcut of the graph parameter $id_F$ (recall that $\mathcal{F}$ is the class of forests), and we use $\text{vc}(G)$ for the minimum size of a vertex cover of $G$, i.e., the minimum number of vertices whose removal from $G$ yields an edgeless graph. Given a graph $G$, we denote by $G^b$ the graph obtained from $G$ after removing all bridges (edges whose removal increases the number of components). The relation between $\text{vc}$ and `idf` is given by the fact that, for every graph $G$, $idf(G) = \text{vc}(G^b)$ (Lemma 4). We also prove that, for every graph $G$, there is a bridgeless graph $G'$ on $|G| + 1$ vertices such that $\text{vc}(G) = \text{vc}(G')$ (Lemma 5). Theorem 1 follows as a consequence of these two facts and the known kernelization algorithm for VERTEX COVER (see Section 3).

**Obstructions for $\mathcal{F}^{(k)}$.** Recall that, for every $k \in \mathbb{N}$, $\mathcal{F}^{(k)}$ is defined as the set of all graphs that admit a $k$-identification to a forest. Clearly, $\mathcal{F}^{(k)}$ is determined by the finite set $\text{obs}(\mathcal{F}^{(k)})$. Identifying $\text{obs}(\mathcal{F}^{(k)})$, for every $k$, requires an upper bound on the size of its elements. This upper bound is not given by the general result of [26]. Our next result is to provide such a bound.

**Theorem 2.** Let $k \in \mathbb{N}$. For any obstruction $G \in \text{obs}(\mathcal{F}^{(k)})$, $|V(G)| \le 2k + 4$.

A linear upper bound as the above is known for the obstructions of the class $\mathcal{V}_k = \{G \mid \text{vc}(G) \le k\}$: Dinneen and Lai proved that $2k+2$ is an upper bound on the size of the graphs in $\text{obs}(\mathcal{V}_k)$ [7,8]. The proof of Theorem 2 is based on a procedure to construct all obstructions of $\mathcal{F}^{(k)}$ using the obstructions of $\mathcal{V}_k$ as a starting point. Then Theorem 2 follows by the upper bound in [8].

**Universal obstruction of idf.** A parametric graph is a minor-monotone sequence $G = \langle G_k \rangle_{k \in \mathbb{N}}$ of graphs, i.e., for every $k \in \mathbb{N}$, $G_k \le G_{k+1}$, where '$\le$' denotes the minor relation. We say that two parametric graphs $G^1$ and $G^2$ are comparable if every graph in $G^1$ is a minor of a graph in $G^2$ or every graph in $G^1$ is a minor of a graph in $G^2$. Given a minor-monotone$^3$ graph parameter $\mathbf{p}: \mathcal{G}_{\text{all}} \to \mathbb{N}$, and a finite set $\mathcal{G} = \{G^1, \dots, G^r\}$ of pairwise non-comparable parametric graphs, we say that $\mathcal{G}$ is a universal obstruction of $\mathbf{p}$ if there is a function $f: \mathbb{N} \to \mathbb{N}$ (we refer to $f$ as the gap function) such that

* for every $k \in \mathbb{N}$, if $G$ excludes all graphs in $\{G_k^1, \dots, G_k^r\}$ as a minor, then $\mathbf{p}(G) \le f(k)$.

* $\mathbf{p}(G_k^j) \ge f(k)$, for every $j \in [r]$.

Universal obstructions serve as asymptotic characterizations of graph parameters, as they identify the typical patterns of graphs that should appear whenever the value of a parameter becomes sufficiently big. Several structural dualities on graph parameters can be described using universal obstructions, and it has been conjectured that for every minor-monotone parameter there always exists some *finite* universal obstruction [23]. (For a survey on universal obstructions see [24].)

<footnote>$^3$We say that a graph parameter $\mathbf{p}: \mathcal{G}_{\text{all}} \to \mathbb{N}$ is *minor-monotone* if, for every two graphs $G, G'$, if $G$ is a minor of $G'$, then $\mathbf{p}(G) \le \mathbf{p}(G')$.</footnote>
Let us give two examples of universal obstructions. A universal obstruction for vc is the set $\{\langle k \cdot K_2 \rangle_{k \in \mathbb{N}}\}^4$ with linear gap function $f(k) = O(k)$. Another example is the universal obstruction for the parameter fvs, where fvs($G$) is the minimum size of a vertex set of $G$ whose removal yields an acyclic graph. An interpretation of the Erdős-Pósa's theorem [10] is that $\{\langle k \cdot K_3 \rangle_{k \in \mathbb{N}}\}$ is a universal obstruction for fvs with gap function $f(k) = O(k \cdot \log k)$. Notice that idf can be seen as the analogue of fvs where now, instead of removing vertices, we pick a set of vertices and apply identifications to them.

Our next result is a universal obstruction for idf. We use $C_k$ for the cycle on $k$ vertices and $k \cdot K_3$ for the $k$- marguerite graph, that is, the graph obtained from $k \cdot K_3$ by selecting one vertex from each connected component and identifying all selected vertices into a single one.

**Theorem 3.** *The set $\{\langle k \cdot K_3 \rangle_{k \in \mathbb{N}}, \langle C_k \rangle_{k \in \mathbb{N}}, \langle k \cdot K_3 \rangle_{k \in \mathbb{N}}\}$ is a universal obstruction of idf, with gap function $f(G) = O(k^4 \cdot \log^2 k)$.*

**Organization of the paper.** In Section 2 we provide some preliminaries and basic observations about the identification operation. In Section 3 we prove the NP-completeness and provide a linear kernel for IDENTIFICATION TO FOREST parameterized by the solution size. In Section 4 we bound the size of the obstructions of $\mathcal{F}^{(k)}$. Finally, in Section 5 we find the universal obstructions of $\mathcal{F}^{(k)}$.

# 2 Preliminaries

**Sets and integers.** We denote by $\mathbb{N}$ the set of non-negative integers. Given two integers $p, q$, where $p \le q$, we denote by $[p, q]$ the set $\{p, \dots, q\}$. For an integer $p \ge 1$, we set $[p] = [1, p]$ and $\mathbb{N}_{\ge p} = \mathbb{N} \setminus [0, p-1]$. For a set $S$, we denote by $2^S$ the set of all subsets of $S$ and by $\binom{S}{2}$ the set of all subsets of $S$ of size 2.

## 2.1 Basic concepts on graphs

A graph $G$ is a pair $(V, E)$ where $V$ is a finite set and $E \subseteq \binom{V}{2}$, i.e., all graphs in this paper are undirected, finite, and without loops or multiple edges. We refer the reader to [6] for any undefined terminology on graphs. For an edge $\{x, y\}$, we use the simpler notation $xy$ (or $yx$). We also define $V(G) = V$ and $E(G) = E$. Given $A, B \subseteq V(G)$, we also denote by $E_G(A, B)$ the set of edges of $G$ with one endpoint in $A$ and the other in $B$. Given a vertex $v \in V(G)$, we denote by $N_G(v)$ the set of vertices of $G$ that are adjacent to $v$ in $G$. Also, given a set $S \subseteq V(G)$, we set $N_G(S) = \bigcup_{v \in S} N_G(v) \setminus S$. For $S \subseteq V(G)$, we set $G[S] = (S, E \cap \binom{S}{2})$ and use $G - S$ to denote $G[V(G) \setminus S]$. We say that $G[S]$ is an induced (by $S$) subgraph of $G$. We denote by $\mathrm{cc}(G)$ the connected components of $G$. A bridge (resp. cut vertex) in $G$ is an edge (resp. a vertex) whose removal increases the number of connected components of $G$. Given $k \in \mathbb{N}_{\ge 1}$, we say that a graph $G$ is $k$-connected if, for any set $X$ of size at most $k-1$, $G - X$ is connected. Given two graphs $G_1$ and $G_2$, we denote $G_1 \cup G_2 = (V(G_1) \cup V(G_2), E(G_1) \cup E(G_2))$.

**Minors.** The contraction of an edge $e = uv \in E(G)$ results in a graph $G/e$ obtained from $G\setminus\{u, v\}$ by adding a new vertex $w$ adjacent to all vertices in the set $N_G(\{u, v\})$. Vertex $w$ is called the *heir* of $e$. A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from a subgraph of $G$ after a series of edge contractions. Equivalently, $H$ is a minor of $G$ if there is a collection $S = \{S_v \mid v \in V(H)\}$

<footnote n="4">⁴For a graph $H$, we denote by $k \cdot H$ the union of $k$ disjoint copies of $H$.</footnote>
of pairwise-disjoint connected subsets of $V(G)$ such that, for each edge $xy \in E(H)$, the set $S_x \cup S_y$ is connected in $V(G)$. $S$ is called a *model of H* in $G$.

We say that a graph class $\mathcal{H}$ is *hereditary* (resp. *monotone*) if it contains all the induced subgraphs (resp. subgraphs) of its graphs. A class $\mathcal{H}$ is *closed under disjoint union* if it contains the disjoint union of every two of its graphs. Finally, $\mathcal{H}$ is *closed under 1-clique-sums* if it is closed under disjoint union and, for any $G, G' \in \mathcal{H}$, the graph obtained by identifying a vertex of $G$ with a vertex of $G'$ also belongs to $\mathcal{H}$.

## 2.2 Identification operation

**Partitions.** Given $p \in \mathbb{N}$, a *p-partition* of a set $X$ is a set $\{X_1, \dots, X_p\}$ of non-empty pairwise disjoint subsets of $X$ such that $X = \cup_{i \in [p]} X_i$. A *partition* of $X$, denoted by $\mathcal{P}(X)$, is a *p-partition* of $X$ for some $p \in \mathbb{N}$. Given two sets $X, A$, and $\mathcal{X} = \{X_1, \dots, X_p\} \in \mathcal{P}(X)$, $\mathcal{X} \cap A$ denotes the partition $\{X_1 \cap A, \dots, X_p \cap A\}$ of $X \cap A$. Given two disjoint sets $X$ and $Y$, and $\mathcal{X} = \{X_1, \dots, X_p\} \in \mathcal{P}(X)$ and $\mathcal{Y} = \{Y_1, \dots, Y_q\} \in \mathcal{P}(Y)$, $\mathcal{X} \cup \mathcal{Y}$ denotes the partition $\{X_1, \dots, X_p, Y_1, \dots, Y_q\} \in \mathcal{P}(X \cup Y)$. Given a graph $G$, we define $\mathcal{P}(G) := \{\mathcal{X} \in \mathcal{P}(X) \mid X \subseteq V(G)\}$. Given $\mathcal{X} = \{X_1, \dots, X_p\} \in \mathcal{P}(G)$, we set $\bigcup \mathcal{X} := \bigcup_{i \in [p]} X_i$, and the order of $\mathcal{X}$ is the size of $\bigcup \mathcal{X}$.

Let $G$ be a graph and $X \subseteq V(G)$. The *identification of $X$ in $G$*, denoted by $G \parallel X$, is the result of the operation that transforms $G$ into a graph $G'$ obtained from $G$ by deleting $X$ and adding instead a new vertex $x$ adjacent to every vertex in $N_G(X)$. The vertex $x$ is called the *heir of $X$*. Note that, if $X = \{u, v\}$ with $uv \in E(G)$, then this corresponds to the contraction of $uv$.

Let $\mathcal{X} = \{X_1, \dots, X_p\} \in \mathcal{P}(G)$. The *identification of $\mathcal{P}$ in $G$* is the graph $G \parallel \mathcal{P} := G \parallel X_1 \parallel X_2 \parallel \dots \parallel X_p$. Note that the ordering of the members of the partition does not matter in this definition.

**Identification to $\mathcal{H}$**. Let $\mathcal{H}$ be a graph class and $G$ be a graph. We say that a partition $\mathcal{X} \in \mathcal{P}(G)$ is an *id-$\mathcal{H}$ partition of $G$* if $G \parallel \mathcal{X} \in \mathcal{H}$. A minimum id-$\mathcal{H}$ partition of $G$ is an id-$\mathcal{H}$ partition of $G$ of minimum order. As explained in the introduction, the problem of IDENTIFICATION TO $\mathcal{H}$ asks, given a graph $G$ and a non-negative integer $k$, whether $G$ admits an id-$\mathcal{H}$ partition of order at most $k$. We denote by $\mathcal{H}^{(k)}$ the set of graphs that admit an id-$\mathcal{H}$ partition of order $k$.

## 2.3 Minor-closedness

As said in the introduction, identifications preserve minor-closedness.

**Lemma 1.** If $\mathcal{H}$ is a minor-closed graph class, then for every $k \in \mathbb{N}$, the class $\mathcal{H}^{(k)}$ is minor-closed.

*Proof.* Let $G \in \mathcal{H}^{(k)}$ and $H$ be a minor of $G$. Let us show that $H \in \mathcal{H}^{(k)}$. Let $\mathcal{X} = \{X_1, \dots, X_p\} \in \mathcal{P}(G)$ be an id-$\mathcal{H}$ partition of $G$. Given that $H$ is a minor of $G$, there is a model $S = \{S_v \mid v \in V(H)\}$ of $H$ in $G$. For $i \in [p]$, let $Y_i = \{v \in V(H) \mid S_v \cap X_i \neq \emptyset\}$. Let $Y := \cup_{i \in [p]} Y_i$. Note that $|Y| \le |\bigcup \mathcal{X}| \le k$. We want to show that the partition $\mathcal{Z}$ of $Y$ induced by the $Y_i$s is an id-$\mathcal{H}$ partition of $H$. However, it is possible that $Y_i \cap Y_j \neq \emptyset$ for distinct $i, j \in [p]$, so $(Y_1, \dots, Y_p)$ is not a partition of $Y$. The correct partition is $\mathcal{Z} = (Z_1, \dots, Z_q) \in \mathcal{P}(Y)$ defined by merging the $Y_i$'s that intersect. In other words, for each $i \in [p]$, there is $j \in [q]$ such that $Y_i \subseteq Z_j$, and if $Z_j \setminus Z_i \neq \emptyset$, then there exists $i' \in [p]$ such that $Y_{i'} \subseteq Z_j$ and $Y_i \cap Y_{i'} \neq \emptyset$. Then $\{S_v \mid v \in V(H) \setminus Y\} \cup \bigcup_{j \in [q]} \{\bigcup_{v \in Z_j} S_v \setminus X \cup \bigcup_{i \in [p], Y_i \subseteq Z_j} \{x_i\}\}$ is a model of $H \parallel \mathcal{Z}$ in $G \parallel \mathcal{X}$, where $x_i$ is the heir of $X_i$. Given that $\mathcal{H}$ is minor-closed, $H \parallel \mathcal{Z} \in \mathcal{H}$, and therefore $H \in \mathcal{H}^{(k)}$. $\square$
# 3 Hardness result and kernel

In this section we exploit the relation between IDENTIFICATION TO FOREST and VERTEX COVER to present a hardness result and a linear kernel for IDENTIFICATION TO FOREST, building on the corresponding results for VERTEX COVER.

## 3.1 Dealing with bridges

We present a series of observations concerning $k$-identifications.

**Observation 1.** Let $\mathcal{H}$ be a hereditary graph class and $G$ be a graph. Then, for every $\mathcal{X} \in \mathcal{P}(G)$, if $G \not\| \mathcal{X} \in \mathcal{H}$, then for each $H \in \mathrm{cc}(G)$, $H \not\| (\mathcal{X} \cap V(H)) \in \mathcal{H}$.

*Proof.* Let $H \in \mathrm{cc}(G)$. Given that $H \not\| (\mathcal{X} \cap V(H)) = G \not\| \mathcal{X} - (V(G) \setminus V(H))$ and that $\mathcal{H}$ is hereditary, we conclude that $H \not\| (\mathcal{X} \cap V(H)) \in \mathcal{H}$. $\square$

**Observation 2.** Let $\mathcal{H}$ be a graph class that is closed under disjoint union and $G$ be a graph. Then, for each $H \in \mathrm{cc}(G)$ and for each $\mathcal{X}_H \in \mathcal{P}(H)$, if $H \not\| \mathcal{X}_H \in \mathcal{H}$, then $G \not\| \bigcup_{H \in \mathrm{cc}(G)} \mathcal{X}_H \in \mathcal{H}$.

*Proof.* Given that $\mathcal{H}$ is closed under disjoint union and $G \not\| \bigcup_{H \in \mathrm{cc}(G)} H \not\| \mathcal{X}_H$, we conclude that $G \not\| \bigcup_{H \in \mathrm{cc}(G)} \mathcal{X}_H \in \mathcal{H}$. $\square$

**Lemma 2.** Let $G$ be a graph and $G^b$ be the graph obtained from $G$ after removing all bridges. Then $\mathrm{idf}(G) = \mathrm{idf}(G^b)$.

*Proof.* Let $k := \mathrm{idf}(G)$. By definition, $G \in \mathcal{F}^{(k)}$. By Lemma 1, $\mathcal{F}^{(k)}$ is minor-closed, so $G - e \in \mathcal{F}^{(k)}$ for any edge $e$ of $G$. Therefore, $\mathrm{idf}(G - e) \le \mathrm{idf}(G)$.

By Observation 1 and Observation 2, we may assume without loss of generality that $G$ is connected. Let $e$ be a bridge of $G$. Let $G_1$ and $G_2$ be the two connected components of $G - e$. For $i \in [2]$, let $\mathcal{X}_i \in \mathcal{P}(X_i)$ be a minimum id-$\mathcal{F}$ partition of $G_i$. By Observation 2, $(G - e) \not\| \mathcal{X} \in \mathcal{F}$ where $\mathcal{X} = \mathcal{X}_1 \cup \mathcal{X}_2$. Suppose toward a contradiction that $G \not\| \mathcal{X}$ contains a cycle $C$. Then, given that $(G - e) \not\| \mathcal{X}$ is acyclic, it implies that $e$ is an edge of $C$. Given that no part of $\mathcal{X}$ contains vertices of both $G_1$ and $G_2$, it implies that $e$ is already an edge of a cycle. This contradicts the fact that $e$ is a bridge. The lemma follows by repeatedly applying this argument as long as there is a bridge. $\square$

**Lemma 3.** Let $G$ be a bridgeless graph. Then $\mathrm{idf}(G) = \mathrm{vc}(G)$.

*Proof.* Let $X$ be a vertex cover of $G$. Then $G \not\| X$ is a star (if $G$ is edgeless, a vertex is considered as a star). Hence, $\{X\} \in \mathcal{P}(G)$ is an id-$\mathcal{F}$ partition of $G$. So $\mathrm{idf}(G) \le \mathrm{vc}(G)$.

Let $\mathcal{X}$ be an id-$\mathcal{F}$ partition of $G$. Let $F := G \not\| \mathcal{X} \in \mathcal{F}$. Let us color red the vertices of $F$ that are heirs of a part of $\mathcal{X}$, and blue the other vertices of $F$. Given that $G$ is bridgeless, $F$ contains no edge whose endpoints are both blue. Hence, the red vertices form a vertex cover of $F$. Therefore, $X$ is a vertex cover of $G$. So $\mathrm{vc}(G) \le \mathrm{idf}(G)$. $\square$

Then we get the main result of this section as a direct corollary of Lemma 2 and Lemma 3.

**Lemma 4.** Let $G$ be a graph and $G^b$ be the graph obtained from $G$ after removing all bridges. Then $\mathrm{idf}(G) = \mathrm{vc}(G^b)$.
## 3.2 NP-completeness

Before proving the NP-completeness of IDENTIFICATION TO FOREST, we first need the following lemma.

**Lemma 5.** Let $k \in \mathbb{N}$. Let $G$ be a graph. Then there is a bridgeless graph $G'$ with $|V(G)| + 1$ vertices such that $G \in \mathcal{V}_k$ if and only if $G' \in \mathcal{V}_{k+1}$. Moreover, $G'$ can be constructed in linear time.

*Proof.* Let us construct a bridgeless graph $G'$ from $G$. Let $I$ be the set of isolated vertices of $G$. We add a new vertex $v$ to $G$ and add an edge between $v$ and every vertex of $G - I$. The constructed graph $G'$ is clearly bridgeless.

Let us check that $G \in \mathcal{V}_k$ if and only if $G' \in \mathcal{V}_{k+1}$. We assume that $G$ has at least one edge, otherwise the claim is trivially true. Suppose the $G \in \mathcal{V}_k$ and let $X$ be a vertex cover of $G$ of size at most $k$. Then $X \cup \{v\}$ is a vertex cover of $G$ so $G' \in \mathcal{V}_{k+1}$. Suppose now that $G' \in \mathcal{V}_{k+1}$. Let $Y$ be a vertex cover of $G'$ of size at most $k+1$. If $v \in Y$, then $Y \setminus \{v\}$ is a vertex cover of $G$ of size at most $k$. Otherwise $v \notin Y$. It implies that $V(G) \setminus I \subseteq Y$. But then, for any vertex $x$ of $G - I$, $N_{G-I}(x) \subseteq Y$. Therefore, $Y \setminus \{x\}$ is a vertex cover of $G$ of size at most $k$. Hence, $G \in \mathcal{V}_k$.

Given that $G'$ can be constructed in linear time, the result follows. $\square$

**Lemma 6.** IDENTIFICATION TO FOREST is NP-complete.

*Proof.* Given a graph $G$ and a partition $\mathcal{X} \in \mathcal{P}(G)$, checking that $G \not\in \mathcal{X} \in \mathcal{F}$ can obviously be done in linear time. We reduce from VERTEX COVER that is NP-hard [16]. Let $G$ be a graph. Let $b$ be the number of bridges in $G$. If $b \ge 1$, by Lemma 5, there is a graph $G'$ with $|V(G')| + 1$ vertices such that $G \in \mathcal{V}_k$ if and only if $G' \in \mathcal{V}_{k'}$ where $k' := k + 1$. If $b = 0$, we set $G' := G$ and $k' := k$. Since $G' \in \mathcal{V}_{k'}$ is bridgeless, by Lemma 3, $G' \in \mathcal{F}^{(k')}$. Since $G'$ can be constructed in linear time and that $G \in \mathcal{V}_k$ if and only if $G' \in \mathcal{F}^{(k')}$, the result follows. $\square$

## 3.3 A kernel for IDENTIFICATION TO FOREST

The following kernelization result is known for VERTEX COVER.

**Proposition 1** ([21, 22]). Given an instance $(G, k)$ of VERTEX COVER, one can compute in polynomial time an equivalent instance $(G', k')$ such that $|V(G')| \le 2k' \le 2k$.

Hence, we can derive the following kernelization result for IDENTIFICATION TO FOREST.

**Lemma 7.** Given an instance $(G, k)$ of IDENTIFICATION TO FOREST, one can compute in polynomial time an equivalent instance $(G', k')$ such that $|V(G')| \le 2k + 1$ and $k' \le k + 1$.

*Proof.* Let $G_1$ be obtained from $G$ after removing bridges. By Lemma 4, $(G, k)$ is a yes-instance of IDENTIFICATION TO FOREST if and only if $(G_1, k)$ is a yes-instance of VERTEX COVER. By Proposition 1, there is $(G_2, k_2)$ with $|V(G_2)| \le 2k_2 \le 2k$ such that $(G_1, k)$ is a yes-instance of VERTEX COVER if and only if $(G_2, k_2)$ is a yes-instance of VERTEX COVER. By Lemma 5, there is $(G_3, k_3)$ such that $G_3$ is a bridgeless graph with $|V(G_3)| \le |V(G_2)| + 1$ and $k_3 \le k_2 + 1$ such that $(G_2, k_2)$ is a yes-instance of VERTEX COVER if and only if $(G_3, k_3)$ is a yes-instance of VERTEX COVER. Finally, by Lemma 4, given that $G_3$ is bridgeless, by Lemma 3, $(G_3, k_3)$ is a yes-instance of VERTEX COVER if and only if it is a yes-instance of IDENTIFICATION TO FOREST. Hence the result. $\square$
# 4 Obstructions

Given that VERTEX COVER and IDENTIFICATION TO FOREST are strongly related, it is reasonable to suspect that this holds for their obstructions as well. Already, as a direct corollary of Lemma 4, we have the two following results.

**Observation 3.** Let $k \in \mathbb{N}$ and $F \in \text{obs}(\mathcal{F}^{(k)})$. Then $F$ is bridgeless.

**Lemma 8.** Let $k \in \mathbb{N}$. The bridgeless obstructions of $\mathcal{V}_k$ are obstructions of $\mathcal{F}^{(k)}$.

*Proof.* Let $H \in \text{obs}(\mathcal{V}_k)$ be bridgeless. By Lemma 3, $H \notin \mathcal{F}^{(k)}$. Thus, there is a minor $H'$ of $H$ such that $H' \in \text{obs}(\mathcal{F}^{(k)})$. By Observation 3, $H'$ is bridgeless. Therefore, by Lemma 3, $H' \notin \mathcal{V}_k$. Given that $H'$ is a minor of $H$ and that $H \in \text{obs}(\mathcal{V}_k)$, we conclude that $H = H'$. Therefore, $H \in \text{obs}(\mathcal{F}^{(k)})$. $\square$

We are actually going to prove in Subsection 4.1 that the only bridges that may occur in an obstruction of $\mathcal{V}_k$ are isolated edges. Then, in Subsection 4.2, we will prove that any obstruction of $\mathcal{F}^{(k)}$ can be obtained from an obstruction of $\mathcal{V}_k$ by adding edges. See Figure 1 for a comparison of $\mathcal{V}_k$ and $\mathcal{F}^{(k)}$ for $k \le 3$, where the obstructions of $\mathcal{V}_k$ are taken from [3].

## 4.1 Bridges in the obstructions of $\mathcal{V}_k$

In this subsection, we prove the following.

**Lemma 9.** Let $k \in \mathbb{N}$ and $G \in \text{obs}(\mathcal{V}_k)$ be a graph. Then the connected components of $G$ are 2-connected. Therefore, the bridges of $G$ are isolated edges.

Actually, we prove a more general version of Lemma 9 applying on any graph class $\mathcal{H}^{\langle k \rangle}$ defined as follows. Let $\mathcal{H}$ be a hereditary graph class (i.e., closed under vertex deletion) that is also closed under 1-clique-sums. Let $\mathcal{H}^{\langle k \rangle}$ be the set of graphs $G$ such that there exists a set $X \subseteq V(G)$ with $|X| \le k$ and $G - X \in \mathcal{H}$. In this setting $\mathcal{V}_k = \mathcal{E}^{\langle k \rangle}$, where $\mathcal{E}$ is class of edgeless graphs.

We need the following easy lemma.

**Lemma 10.** Let $\mathcal{H}$ be a hereditary class, $k \in \mathbb{N}$ and $H \in \text{obs}(\mathcal{H}^{\langle k \rangle})$. Then, for any $v \in V(H)$, there is a set $S \subseteq V(H)$ of size $k+1$ such that $v \in S$ and $H - S \in \mathcal{H}$. In particular, $\text{obs}(\mathcal{H}^{\langle k \rangle}) \subseteq \mathcal{H}^{\langle k+1 \rangle} \setminus \mathcal{H}^{\langle k \rangle}$.

*Proof.* Let $H \in \text{obs}(\mathcal{H}^{\langle k \rangle})$ and $v \in V(H)$. By definition of an obstruction, $H \notin \mathcal{H}^{\langle k \rangle}$ and $H - \{v\} \in \mathcal{H}^{\langle k \rangle}$. So there is a vertex set $S'$ of size at most $k$ in $H - \{v\}$ such that $H - \{v\} - S' \in \mathcal{H}$. Let $S := S' \cup \{v\}$. Then $H - S \in \mathcal{H}$ so $H \in \mathcal{H}^{\langle k+1 \rangle}$. Given that $H \notin \mathcal{H}^{\langle k \rangle}$, we have $|S| > k$, and therefore, $|S| = k + 1$. $\square$

Here is the main result of the subsection.

**Lemma 11.** Let $k \in \mathbb{N}$. Every connected component of a graph in $\text{obs}(\mathcal{H}^{\langle k \rangle})$ is 2-connected.

*Proof.* Suppose toward a contradiction that $G \in \text{obs}(\mathcal{H}^{\langle k \rangle})$ has a connected component that is not 2-connected. Then there is a cut vertex $v$ in $G$. Let $G_1$ be a connected component of $G - \{v\}$ such that $v \in N_G(V(G_1))$ and let $G_2 = G - V(G_1) - \{v\}$. For $i \in [2]$, let $k_i$ be the minimum $k$ such that $G_i \in \mathcal{H}^{\langle k \rangle}$. Hence, $G_i \in \mathcal{H}^{\langle k_i \rangle} \setminus \mathcal{H}^{\langle k_i-1 \rangle}$.
<table><caption>Figure 1: The obstructions of $V_k$ (first and second columns) and $F^{(k)}$ (second and third columns) for $k \le 3$. Each graph in $obs(F^{(k)})$ is either 1) also a graph in $obs(V^{(k)})$ (second column), or 2) can be obtained from a graph in $obs(V^{(k)})$ with bridges (first column) by adding edges (in blue in the third column), or 3) is also a graph in $obs(V^{(k+1)})$ (in purple in the third column). We use yellow shadows for disconnected obstructions, to make clear that each of them is a single graph.</caption><thead><tr><th></th><th>obs(V<sub>k</sub>) \ obs(F<sup>(k)</sup>)</th><th>obs(V<sub>k</sub>) ∩ obs(F<sup>(k)</sup>)</th><th>obs(F<sup>(k)</sup>) \ obs(V<sub>k</sub>)</th></tr></thead><tbody><tr><td>k = 0</td><td><img src="image_0.png" alt="A graph with a vertex labeled K<sub>2</sub> and two edges, one to the left and one to the right."></td><td></td><td><img src="image_1.png" alt="A graph with a triangle and a line segment connecting its vertices. The triangle has vertices labeled K<sub>3</sub> and C<sub>3</sub>, and the line segment has a vertex labeled K<sub>3</sub>."></td></tr><tr><td>k = 1</td><td><img src="image_2.png" alt="A graph with three vertices, two of which are connected by edges. The graph is a subgraph of the graph in the first row."></td><td><img src="image_3.png" alt="A graph with three vertices, two of which are connected by edges, and the third vertex is connected to one of the other two vertices. The graph is a subgraph of the graph in the first row."></td><td></td></tr><tr><td>k = 2</td><td><img src="image_4.png" alt="A graph with four vertices, three of which are connected by edges. The graph is a subgraph of the graph in the first row."></td><td><img src="image_5.png" alt="A graph with four vertices, three of which are connected by edges, and the fourth vertex is connected to one of the other three vertices. The graph is a subgraph of the graph in the first row."></td><td><img src="image_6.png" alt="A graph with four vertices, three of which are connected by edges, and the fourth vertex is connected to one of the other three vertices. The graph is a subgraph of the graph in the first row."></td></tr><tr><td>k = 3</td><td><img src="image_7.png" alt="A graph with five vertices, four of which are connected by edges. The graph is a subgraph of the graph in the first row."></td><td><img src="image_8.png" alt="A graph with five vertices, four of which are connected by edges, and the fifth vertex is connected to one of the other four vertices. The graph is a subgraph of the graph in the first row."></td><td><img src="image_9.png" alt="A graph with five vertices, four of which are connected by edges, and the fifth vertex is connected to one of the other four vertices. The graph is a subgraph of the graph in the first row."></td></tr></tbody></table>

**Claim 1.** $k = k_1 + k_2$.

*Proof.* By Lemma 10, $G \in \mathcal{H}^{\langle k+1 \rangle} \setminus \mathcal{H}^{\langle k \rangle}$. For $i \in [2]$, let $S_i \subseteq V(G_i)$ of size at most $k_i$ be such that $G_i - S_i \in \mathcal{H}$. Then $S := S_1 \cup S_2 \cup \{v\}$ is such that $G - S \in \mathcal{H}$, so $k + 1 \le k_1 + k_2 + 1$.

By Lemma 10, there is a set $S \subseteq V(G)$ of size $k+1$ such that $v \in S$ and $G - S \in \mathcal{H}$. Given that $\mathcal{H}$ is hereditary, $G_i - (S \cap V(G_i)) \in \mathcal{H}$. Moreover, $G_i \notin \mathcal{H}^{\langle k_i-1 \rangle}$ for $i \in [2]$, so we conclude that $|S \cap V(G_i)| \ge k_i$. Hence, $k+1 = |S| = |\{v\} \cup (S \cap V(G_1)) \cup (S \cap V(G_2))| \ge k_1 + k_2 + 1$. $\square$

For $i \in [2]$, let $\bar{G}_i := G[V(G_i) \cup \{v\}]$. Since $G_i \in \mathcal{H}^{\langle k_i \rangle} \setminus \mathcal{H}^{\langle k_i-1 \rangle}$ and we only add the vertex $v$, $\bar{G}_i \in \mathcal{H}^{\langle k_i+1 \rangle} \setminus \mathcal{H}^{\langle k_i-1 \rangle}$.

**Claim 2.** There is $i \in [2]$ such that $\bar{G}_i \in \mathcal{H}^{\langle k_i+1 \rangle} \setminus \mathcal{H}^{\langle k_i \rangle}$.

*Proof.* Suppose that $\bar{G}_i \in \mathcal{H}^{\langle k_i \rangle}$ for $i \in [2]$. Let $S_i \subseteq V(\bar{G}_i)$ of size $k_i$ be such that $\bar{G}_i - S_i \in \mathcal{H}$.
Then $S := S_1 \cup S_2$ has size at most $k_1 + k_2 < k + 1$. Moreover, given that $\mathcal{H}$ is closed under 1-clique-sums, we have $G - S \in \mathcal{H}$. By Claim 1, it follows that $G \in \mathcal{H}^{\langle k \rangle}$, a contradiction. $\square$

By Claim 2, without loss of generality, we assume that $\bar{G}_1 \in \mathcal{H}^{\langle k_1+1 \rangle} \setminus \mathcal{H}^{\langle k_1 \rangle}$. Let $G'$ be the graph obtained from the disjoint union of $\bar{G}_1$ and $G_2$. Given that $\mathcal{H}$ is closed under disjoint union and by Claim 1, $G' \in \mathcal{H}^{\langle k_1+1+k_2 \rangle} \setminus \mathcal{H}^{\langle k_1+k_2 \rangle} = \mathcal{H}^{\langle k+1 \rangle} \setminus \mathcal{H}^{\langle k \rangle}$. $G'$ is a subgraph of $G$ so this contradicts the minimality of $G$ as an obstruction of $\mathcal{H}^{\langle k \rangle}$. $\square$

## 4.2 Constructing the obstructions of $\mathcal{F}^{(k)}$ from the obstructions of $\mathcal{V}_k$

What Lemma 8 and Lemma 11 tell us is that the difference (as sets) between $\text{obs}(\mathcal{V}_k)$ and $\text{obs}(\mathcal{F}^{(k)})$ is caused by isolated edges. Essentially, to go from an obstruction $H$ of $\mathcal{V}_k$ with isolated edges to an obstruction $H'$ of $\mathcal{F}^{(k)}$, we will have to add vertices and edges minimally to get a bridgeless graph. In this section, we prove that we actually just need to add edges.

Let $\text{Obs} = \bigcup_{k \in \mathbb{N}} \text{obs}(\mathcal{F}^{(k)})$. We have the following easy observation.

**Observation 4.** Let $G \in \text{Obs}$ and $k := \text{idf}(G) - 1$. Then $G \in \text{obs}(\mathcal{F}^{(k)})$.

Note that, while we observed in Lemma 10, in particular, that $\text{obs}(\mathcal{V}_k) \subseteq \mathcal{V}_{k+1} \setminus \mathcal{V}_k$, the same does not hold for $\mathcal{F}_k$. For instance, $k \cdot K_3$ (see Figure 4) belongs to both $\text{obs}(\mathcal{F}_{2k-2})$ and $\text{obs}(\mathcal{F}_{2k-1})$. However, we can prove the following.

**Lemma 12.** Let $k \in \mathbb{N}$. Then $\text{obs}(\mathcal{F}_k) \subseteq \mathcal{F}_{k+2} \setminus \mathcal{F}_k$.

*Proof.* Let $G \in \text{obs}(\mathcal{F}_k)$ and $uv \in E(G)$. Let $\mathcal{X}$ be an id-$\mathcal{F}$ partition of $G/uv$. Then $G \nsim \{u, v\} \nsim \mathcal{X} \in \mathcal{F}$, so $G \nsim \mathcal{X}' \in \mathcal{F}$, where $\mathcal{X}'$ is obtained from $\mathcal{X}$ by further identifying $u$ and $v$. Thus, $|\bigcup \mathcal{X}'| \le |\bigcup \mathcal{X}| + 2 \le k + 2$, hence the result. $\square$

The main result of this subsection is the following.

**Lemma 13.** Let $G$ be a graph and $k := \text{idf}(G) - 1$. If $G \in \text{obs}(\mathcal{F}^{(k)})$, then there is $H \in \text{obs}(\mathcal{V}_k)$ that is a minor of $G$, and for any such $H$, there is $E' \subseteq E(G)$ such that $G - E' = H$.

*Proof.* By Observation 3, $G$ is bridgeless. Therefore, by Lemma 3, $\text{idf}(G) = \text{vc}(G)$, and thus $G \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$. We first prove that, for any edge $e \in E(G)$, $G/e \in \mathcal{V}_k$.

**Claim 3.** For any edge $uv \in E(G)$, $G/uv \in \mathcal{V}_k$.

*Proof of claim.* Suppose toward a contradiction that there is an edge $uv \in E(G)$ such that $G/uv \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$. Let $w$ be the heir of $uv$ in $G/uv$. Since $G \in \text{obs}(\mathcal{F}^{(k)})$, it implies that $G/uv \in \mathcal{F}^{(k)}$. By Observation 3, $G$ is bridgeless. Thus, by Lemma 3 and since $G/uv \in \mathcal{F}^{(k)} \setminus \mathcal{V}_k$, it implies that the contraction of $u$ and $v$ created a bridge $e$. Given that only the edges incident to $u$ and $v$ are involved in the contraction, the bridges of $G/uv$ are exactly the edges $xw$ where $x \in N_G(u) \cap N_G(v)$ is a cut vertex of $G$ (the edges $xu$ and $xv$ in $G$ are contracted to $xw$ in $G/uv$). See Figure 2 for an illustration. Let $C$ be the set of all such $x$. Let $E_1$ be the set of all edges $xu, xv$ of $G$ for $x \in C$ and let $E_2$ be the set of all edges $xw$ of $G/uv$ for $x \in C$.

Given that $G/uv \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$, there is $H \in \text{obs}(\mathcal{V}_k)$ that is a minor of $G/uv$. For $x \in C$, let $G_x$ be the connected component of $G - E_1$ containing $x$ and $G_w$ be the disjoint union of the remaining components of $G - E_1$. Note that $G_x$ is also the connected component of $G/uv - E_2$ containing $x$ for $x \in C$, and that $G'_w := G_w/uv$ is the union of the other connected components of $G/uv - E_2$. Given
<figure><img src="image_2.png" /><figcaption>Figure 2: Graphs $G$ and $G/uv$.</figcaption></figure>

that $G/uv - E_2$ is bridgeless, so are $G_x$ for $x \in C$ and $G'_w$. By Lemma 11, each connected component of $H$ is 2-connected. Therefore, given a model $M$ of $H$ of minimal size in $G/uv$, a bridge of $G/uv$ belongs to $M$ if and only if it is an isolated edge in $M$. Therefore, $H$ is either a minor of $F := G'_w \cup \bigcup_{x \in C} G_x$ or, for some $x \in C$, a minor of $F_x := G[\{x, w\}] \cup (G'_w - \{w\}) \cup (G_x - x) \cup \bigcup_{y \in C \setminus \{y\}} G_y$. See Figure 3 for an illustration.

<figure><img src="image_3.png" /><figcaption>Figure 3: Graphs $F$, $F_x$, and $F'_x$.</figcaption></figure>

If $H$ is a minor of $F$ which is a minor of $G$, then $F \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$. Given that $F$ is bridgeless, by Lemma 3, we thus have $F \in \mathcal{F}^{(k+1)} \setminus \mathcal{F}^{(k)}$. This contradicts the fact that $G \in \text{obs}(\mathcal{F}^{(k)})$.

Hence, $H$ is a minor of $F_x$ for some $x \in C$. Then $H$ is also a minor of $F'_x := G[\{x, u, v\}] \cup (G_w - u - \{v\}) \cup (G_x - x) \cup \bigcup_{y \in C \setminus \{x\}} G_y$, which is a minor of $G$. Thus, $F_x, F'_x \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$. Let $S$ be a vertex cover of $F'_x$ of minimum size, i.e., $|S| = k+1$. Let $S' := S \cap \{x, u, v\}$. Given that $G[\{x, u, v\}]$ is a triangle, $|S'| = 2$. But then, $S \setminus S' \cup \{x\}$ is a vertex cover of $F_x$ of size $k$, a contradiction. $\diamond$

We now prove that, for any vertex $v \in V(G)$, $G - \{v\} \in \mathcal{V}_k$.

**Claim 4.** For any vertex $v \in V(G)$, $G - \{v\} \in \mathcal{V}_k$.

*Proof of claim.* Suppose toward a contradiction that there is a vertex $v \in \mathcal{V}_k$ such that $G - \{v\} \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$. If $v$ is an isolated vertex, then $G - \{v\}$ is bridgeless. So by Lemma 3, $G - \{v\} \in \mathcal{F}^{(k+1)} \setminus \mathcal{F}^{(k)}$, contradicting that $G \in \text{obs}(\mathcal{F}^{(k)})$. So there is a vertex $u \in N_G(v)$. Let us prove that $G/uv \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$. This will contradict Claim 3 and prove the claim.

Suppose toward a contradiction that $G/uv \in \mathcal{V}_k$. Let $S$ be a vertex cover of $G/uv$ of size $k$. Let $w$ be the heir of the edge $uv$ in $G/uv$. If $w$ belongs to $S$, then $S - \{w\} \cup \{u, v\}$ is a vertex cover of $G$ of size $k+1$ containing $v$. If $w$ does not belong to $S$, then $N_{G/uv}(w) \subseteq S$. Since
$N_{G/uv}(w) = N_G(\{u, v\})$, we conclude that $S \cup \{v\}$ is a vertex cover of $G$ of size $k+1$ containing $v$. In both cases, $G$ has a vertex cover $S'$ of size $k+1$ containing $v$. Therefore, $G - \{v\}$ has a vertex cover of size $k$, contradicting the fact that $G - \{v\} \notin \mathcal{V}_k$. ◇

Given that $G \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$, there is $H \in \mathbf{obs}(\mathcal{V}_k)$ that is a minor of $G$. By Lemma 10, $H \in \mathcal{V}_{k+1} \setminus \mathcal{V}_k$. $H$ is obtained from $G$ by a sequence of vertex deletions, edge deletions, and edge contractions such that at each step, the resulting graph belong to $\mathcal{V}_{k+1} \setminus \mathcal{V}_k$. In particular, we can first do all vertex deletions and edge contractions and then the remaining edge deletions. But then, by Claim 3 and Claim 4, we cannot do any vertex deletion nor edge contraction and still remain in $\mathcal{V}_{k+1} \setminus \mathcal{V}_k$. Therefore, there is $E' \subseteq E(G)$ such that $G - E' \in \mathbf{obs}(\mathcal{V}_k)$. This concludes the proof. □

We thus have the following upper bound on the size of obstructions, which is a restatement of Theorem 2.

**Lemma 14.** Let $k \in \mathbb{N}$. For any obstruction $G \in \mathbf{obs}(\mathcal{F}^{(k)})$, $|V(G)| \le 2k + 4$.

*Proof.* The obstruction of maximal size in $\mathbf{obs}(\mathcal{V}_k)$ is $(k+1) \cdot K_2$, i.e., the graph obtained from the disjoint union of $k+1$ isolated edges, which has size $2k+2$.

Let $G \in \mathbf{obs}(\mathcal{F}^{(k)})$. By Lemma 12, we have $\mathrm{idf}(G) \in \{k+1, k+2\}$. Moreover, by Lemma 13, there is $E' \subseteq E(G)$ such that $G - E' \in \mathbf{obs}(\mathcal{V}_{\mathrm{idf}(G)-1})$. Therefore, $G - E'$, and thus $G$, has size at most $2k+4$. □

# 5 Universal obstruction

As we already explained in the introduction, we denote by $k \cdot K_3$ the union of $k$ disjoint copies of $K_3$ and by $C_k$ the cycle on $k$ vertices. Recall also that the *marguerite* of order $k$, denoted by $k \cdot K_3$, is the graph $(k \cdot K_3) \parallel X$, where $X \subseteq V(k \cdot K_3)$ is a set containing exactly one vertex from each triangle (see Figure 4).

<figure><img src="image_4.png" /><figcaption>Figure 4: The universal obstruction for IDENTIFICATION TO FOREST.</figcaption></figure>

**Observation 5.** $C_{2k+1}, \lfloor \frac{k}{2} + 1 \rfloor \cdot K_3$, and $(k+1) \cdot K_3$ are in $\mathbf{obs}(\mathcal{F}^{(k)})$.

**Lemma 15.** If $G$ excludes every graph in $\{C_k, k \cdot K_3, k \cdot K_3\}$ as a minor, then $\mathrm{idf}(G) = O(k^4 \cdot \log^2 k)$.

*Proof.* Let $G$ be a $\{C_k, k \cdot K_3, k \cdot K_3\}$-minor-free graph. By Lemma 3, we can assume without loss of generality that $G$ is bridgeless. In particular, any vertex of $G$ has degree at least two.
By the Erdős–Pósa's theorem [10], either $G$ has a packing of $k$ cycles, or there is a set $X$ of size $\mathcal{O}(k \cdot \log k)$ such that $G - X \in \mathcal{F}$. Given that $G$ is $k \cdot K_3$-minor-free, there exists such a set $X$ and $G[X]$ has at most $\mathcal{O}(k \cdot \log k)$ connected components.

Let $C$ be a connected component of $G[X]$. Let $\mathcal{T}_C$ be the set of trees in $F$ with a neighbor in $C$. Given that $G$ is bridgeless and that any path from a vertex of $T \in \mathcal{T}_C$ to a vertex of $G-V(C)-V(T)$ intersects $C$, we have $|E_G(V(T), V(C))| \ge 2$. Hence, there is a cycle in the graph induced by $T$ and $C$. Hence, $|\mathcal{T}_C| * K_3$ is a minor of $G$. Therefore, $|\mathcal{T}_C| \le k - 1$.

Let $T \in \mathcal{T}_C$. Let $T^C$ be the subtree of $T$ obtained by iteratively removing every leaf of $T$ that is not in $N_G(C)$. Hence, for every pair of leaves $u, v$ of $T^C$, there are two $(u, v)$-paths $P_1$ and $P_2$, the first one in $T^C$ and the second one going through $C$, that are internally vertex-disjoint. So there is a cycle of length at least $\Delta(T^C) + 1$, where $\Delta(T^C)$ denotes the diameter of $T^C$. Given that $C_k$ is not a minor of $G$, $T^C$ has diameter at most $k - 2$.

Let $L(T^C)$ denote the leaves of $T^C$, and let $PL(T^C)$ denote the parents of vertices in $L(T^C)$. We claim that $|PL(T^C)| \le k$. Indeed, let $u \in L(T^C)$ be a leaf picked arbitrarily. Let $V' = V(C) \cup V(T^C) \setminus PL(T^C) \setminus \{u, \mathfrak{p}(u)\}$, where $\mathfrak{p}(u)$ is the parent of $u$ in $T^C$. Observe that, since $u$ is connected to $C$, $G[V']$ is connected. Hence, we can contract $V'$ to a single vertex $c$ to obtain a graph $G'$. For each $t \in PL(T^C) \setminus \{\mathfrak{p}(u)\}$, there is a triangle $ctv_t$ where $v_t \in L(T^C)$ is a child of $t$. Hence, $(|PL(T^C)| - 1) * K_3$ is a subgraph of $G'$ and thus a minor of $G$. Since $k * K_3$ is not a minor of $G$, we proved our claim.

Therefore, $|V(T^C) \setminus L(T^C)| \le \Delta(T^C) \cdot |PL(T^C)| \le k \cdot (k-2)$.

Let $E'$ be the set of all edges of $F$ that do not belong to $T^C$ for any $C \in \mathrm{cc}(G[X])$ and $T \in \mathcal{T}_C$. Let $e \in E'$. Since $e$ is not a bridge, $e$ is part of a cycle $C_e$. Hence, there are $C, C' \in \mathrm{cc}(G[X])$ and $T \in \mathcal{T}_C \cap \mathcal{T}_{C'}$ such that any path from $T^C$ to $T_{C'}$ in $T$ goes through $e$. Moreover, there are at most $k-5$ such edges between $T^C$ to $T_{C'}$, since otherwise $C_e$ would have length at least $k$. Hence, $|E'| \le (k-5) \cdot (|\mathrm{cc}(G[X])|) \cdot \max_{C \in \mathrm{cc}(G[X])} |\mathcal{T}_C| = \mathcal{O}(k^4 \cdot \log^2 k)$.

Let $V' \subseteq V(G)$ be the union of $X$, of the endpoints of edges in $E'$, and of the internal nodes of $T^C$ for any $C \in \mathrm{cc}(G[x])$ and any $T \in \mathcal{T}_C$. Then, $V(G) \setminus V' \subseteq L(F)$, so $G \setminus V'$ is a star. Moreover, $|V| = \mathcal{O}(k \cdot \log k + k^4 \cdot \log^2 k + k \cdot \log k \cdot k \cdot k^2) = \mathcal{O}(k^4 \cdot \log^2 k)$. $\square$

*Proof of Theorem 3.* The first condition of the universal obstruction property follows from Lemma 15 and the second one follows from Observation 5. $\square$

# 6 Discussion and open problems

In this paper we initiated the study of graph modification problems where the modification operation is vertex identification. We defined the problem IDENTIFICATION TO $\mathcal{H}$ and studied the case where the target class $\mathcal{H}$ is the class of forest, denoted by $\mathcal{F}$.

**Relation with CONTRACTION TO $\mathcal{H}$**. An important feature of IDENTIFICATION TO $\mathcal{H}$ is that it behaves similarly to the problem DELETION TO $\mathcal{H}$, in the sense that both problems are FPT when $\mathcal{H}$ is a minor-closed graph class. This follows from Lemma 1 and the algorithmic consequence of the Robertson and Seymour's theorem [17, 18, 25, 27, 28]. It is easy to observe that the problem CONTRACTION TO $\mathcal{H}$ (that is, asking whether $k$ edge contractions yield property $\mathcal{H}$) does not have this property. To see this, let $\mathcal{P}$ be the class of planar graphs and let $K_{3,4}^+$ (resp. $K_{2,3}^+$) be the graph obtained from $K_{3,4}$ (resp. $K_{2,3}$) by adding an edge $e$ between two vertices of degree three (resp. two). Contracting $e$ yields a planar (resp. acyclic) graph, so $(K_{3,4}^+, 1)$ (resp. $(K_{2,3}^+, 1)$) is
a *yes*-instance of CONTRACTION TO *P* (CONTRACTION TO FOREST). However, ($K_{3,4}, 1$) (resp. ($K_{2,3}, 1$)) is a *no*-instance of the corresponding problem.

Let us define the parameter $ec_H : G_{all} \to \mathbb{N}$, corresponding to the problem CONTRACTION TO $\mathcal{H}$, i.e., $ec_H(G)$ is the minimum number of edge contractions that can transform $G$ to a graph in $\mathcal{H}$. As we observed above, neither $ec_F$ nor $ec_P$ are minor-monotone, and similar counterexamples can be found for other instantiations of $\mathcal{H}$. We use $ecf$ as a shortcut for $ec_F$ and we next observe that $idf$ and $ecf$ are functionally equivalent.

**Lemma 16.** For every graph $G$ it holds that $idf(G) = O(\text{ecf}(G))$ and that $ecf(G) = O((idf(G))^3)$.

*Proof.* Using the fact that edge contractions are also edge identifications, it easily follows that, for every graph $G$, $idf(G) \le 2 \cdot \text{ecf}(G)$.

Assume now that $idf(G) \le k$ and we claim that $ecf(G) = O(k^3)$. To prove this claim we first observe that, because $idf(k \cdot K_3) = \Omega(k)$ and $idf(k * K_3) = \Omega(k)$ (see Observation 5), it follows that the number of 2-connected components of $G$ that are not bridges is bounded by some linear function of $k$. Let $B$ be a 2-connected component of $G$. As $B$ is a minor of $G$, it has an id-$\mathcal{F}$ partition $\mathcal{X} = \{X_1, \dots, X_p\}$ of order $\le k$. For $i \in [p]$, let $x_i^1, \dots, x_{p_i}^i$ be an ordering of the vertices of $X_i$ and let $F_i = \{\{x_i^1, x_2^1\}, \{x_2^1, x_3^1\}, \dots, \{x_{p_i-1}^i, x_{p_i}^i\}\}$. Let also $F = F_1 \cup \dots \cup F_p$. Clearly, the 2-element sets in $F$ are not necessarily edges of $B$. For each $\{x, y\} \in F$ we define a set of edges $F_{x,y}$ as follows. As $B$ is 2-connected, $x$ and $y$ belong to a cycle of $B$. As $idf(C_k) = \Omega(k)$ (see Observation 5), this implies that $x$ and $y$ are joined in $B$ by a path of length $O(k)$. The edges of this path are the edges in $F_{x,y}$. We now set $F^+ = \bigcup_{\{x,y\} \in F} F_{x,y}$ and observe that $|F^+| = O(k^2)$. Notice now that contracting the edges of $F^+$ in $B$ yields an acyclic graph. Therefore, applying these contractions to every non-bridge connected component of $G$, we obtain an acyclic graph. As there are $O(k)$ such components, the lemma follows. $\square$

In other words, $ecf$ is not minor-monotone but, however, it is “functionally” monotone in the sense that if $G'$ is a minor of $G$ then $ecf(G') \le O((ecf(G))^3)$.<fnref n="5" /> While it is easy to see that $\text{id}_H(G) \le 2 \cdot \text{ec}_H(G)$, we also conjecture that an upper bound as the one of Lemma 16 holds for every minor-closed class $\mathcal{H}$.

**Conjecture 1.** For every minor-closed graph class $\mathcal{H}$, there is a function $f_\mathcal{H} : \mathbb{N} \to \mathbb{N}$ such that for every $G$, $ec_\mathcal{H} \le f_\mathcal{H}(\text{id}_\mathcal{H}(G))$.

Note that CONTRACTION TO $\mathcal{H}$ is known to be W[1]-hard, parameterized by the solution size, for several families $\mathcal{H}$ that are not minor-closed, such as chordal graph or split graphs (see [1] and the references cited therein). However, when $\mathcal{H}$ is minor-closed, the recent meta-algorithmic results in [11] (further generalized in [29]) imply that CONTRACTION TO $\mathcal{H}$ is (constructively) FPT (see [14, 19] for explicit algorithms for some particular families). Also, as it has been proved in [14], CONTRACTION TO FOREST is not expected to admit a polynomial kernel. Interestingly, the kernelization we give in this paper for IDENTIFICATION TO FOREST, under the light of the polynomial-gap functional equivalence of Lemma 16, can be seen as some kind of “functional kernel” for CONTRACTION TO FOREST.

**Identification minors.** We say that a graph $H$ is an *identification minor* of a graph $G$ if $H$ can be obtained from a minor of $G$ after identifying vertices. As the minor relation between

<footnote n="5">⁵The cubic bound in Lemma 16 is just indicative and has not been optimized.</footnote>
two graphs also implies their identification minor relation, Robertson and Seymour's theorem [26]
implies that graphs are well-quasi-ordered by the identification minor relation. It is also easy to
observe that, for every graph $H$, the graphs in the set $M_H$ of minor-minimal graphs containing
$H$ as an identification have size is bounded by a quadratic function of $|H|$. Therefore, checking
whether $H$ is an identification minor of $G$ can be done in time $O_{|H|}(|G|^{1+\epsilon})$, according to the recent
results in [18].

It is a natural question to ask whether graphs are well-quasi-ordered with respect to the vertex identification operation alone. The answer turns out to be negative. Indeed, there is an infinite antichain $(H_k)_{k \in \mathbb{N}}$, where $H_k$ is the graph formed from a cycle on $3k$ vertices $p_1, \dots, p_{3k}$ by adding three vertices $a_1, a_2, a_3$ and an edge between each pair $(a_i, p_j)$ such that $j$ is equal to $i$ modulo three. See Figure 5 for an illustration. It can be verified that this family of graphs is indeed an antichain, even if we allow both vertex identifications and vertex removals.

<figure><img src="image_5.png" /><figcaption>Figure 5: The graph $H_k$ for $k = 5$. We give credit to Hugo Jacob for finding it.</figcaption></figure>

We now wish to give the following interpretation of Lemma 15 in terms of identification minors.
To prove it, one needs to observe that $k * K_3$ is an identification-minor of both $k \cdot K_3$ and $C_{3k}$.

**Theorem 4.** For every graph $G$ and positive integer $k$, either $G$ contains the $k$-marguerite $k*K_3$ as an identification minor, or $G$ can become acyclic after applying $O(k^4 \cdot \log^2 k)$ vertex identifications.

The above theorem can be seen as an analogue of the Erdős-Pósa's theorem [10] where instead of the vertex removal operation we have vertex identification, and instead of $k \cdot K_3$ minor containment we have $k * K_3$ identification minor containment. Which are the (parametric) graphs appearing as identification minors when $\mathrm{id}_H$ is big enough, for a general minor-closed graph class $\mathcal{H}$?

References

[1] Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split contraction: The untold story. *ACM Transactions on Computational Theory*, 11(3):18:1–18:22, 2019. doi: 10.1145/3319909. 15

[2] Manuel Bodirsky, Jan Kára, and Barnaby Martin. The complexity of surjective homomorphism problems—a survey. *Discrete Applied Mathematics*, 160(12):1680–1690, 2012. doi:10.1016/j.dam.2012.03.029. 3

[3] Kevin Cattell and Michael J. Dinneen. A characterization of graphs with vertex cover up to five. In *Proc. of Orders, Algorithms, and Applications, International Workshop ORDAL*, volume 831 of LNCS, pages 86–99. Springer, 1994. doi:10.1007/BFB0019428. 9

[4] Marc Comas and Maria Serna. Vertex fusion under distance constraints. *European Journal of Combinatorics*, 30(7):1612–1623, 2009. doi:10.1016/j.ejc.2009.03.014. 2, 3
[5] Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr Golovach. A survey of parameterized algorithms and the complexity of edge modification. *Computer Science Review*, 48:100556, 2023. doi:https://doi.org/10.1016/j.cosrev.2023.100556.2

[6] Reinhard Diestel. *Graph theory*, volume 173 of *Graduate Texts in Mathematics*. Springer, Berlin, fifth edition, 2017. doi:10.1007/978-3-662-53622-3. 5

[7] Michael J. Dinneen. Too many minor order obstructions (for parameterized lower ideals). In *First Japan-New Zealand Workshop on Logic in Computer Science (Auckland, 1997)*, volume 3(11), pages 1199-1206 (electronic). Springer, 1997. 4

[8] Michael J. Dinneen and Rongwei Lai. Properties of vertex cover obstructions. *SIAM Journal on Discrete Mathematics*, 307(21):2484-2500, 2007. doi:10.1016/J.DISC.2007.01.003. 4

[9] Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon. Measuring what matters: A hybrid approach to dynamic programming with treewidth. *Journal of Computer and System Sciences*, 121:57-75, 2021. doi:10.1016/j.jcss.2021.04.005. 2

[10] Paul Erdős and Lajos Pósa. On independent circuits contained in a graph. *Canadian Journal of Mathematics*, 17:347-352, 1965. 5, 14, 16

[11] Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound Logics for Modification Problems. In *Proc. of the 50th International Colloquium on Automata, Languages, and Programming (ICALP)*, volume 261 of *LIPIcs*, pages 61:1-61:21, 2023. doi:10.4230/LIPIcs.ICALP.2023.61. 15

[12] Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Modification to Planarity is Fixed Parameter Tractable. In *Proc. of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS)*, volume 126 of *LIPIcs*, pages 28:1-28:17, 2019. doi:10.4230/LIPIcs.STACS.2019.28. 2

[13] Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In *Proc. of the 1st International Workshop on Parameterized and Exact Computation (IWPEC)*, volume 3162 of *LNCS*, pages 162-173, 2004. doi:10.1007/978-3-540-28639-4_15. 1

[14] Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov, and Christophe Paul. Contracting graphs to paths and trees. *Algorithmica*, 68(1):109-132, 2014. doi:10.1007/S00453-012-9670-2. 2, 3, 15

[15] Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul. Obtaining a bipartite graph by contracting few edges. *SIAM Journal on Discrete Mathematics*, 27(4):2143-2156, 2013. doi:10.1137/130907392. 2

[16] Richard M. Karp. *Reducibility among combinatorial problems*. Springer, 2010. 8

[17] Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. The disjoint paths problem in quadratic time. *Journal of Combinatorial Theory, Series B*, 2011. doi:10.1016/j.jctb.2011.07.004. 3, 14
[18] Tuukka Korhonen, Michał Pilipczuk, and Giannos Stamoulis. Minor containment and disjoint paths in almost-linear time, 2024. arXiv:2404.03958. 3, 14, 16

[19] R. Krithika, V. K. Kutty Malu, Roohani Sharma, and Prafullkumar Tale. Parameterized complexity of biclique contraction and balanced biclique contraction. In Proc. of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 284 of LIPIcs, pages 8:1–8:18, 2023. doi:10.4230/LIPICS.FSTTCS.2023.8.15

[20] John M. Lewis and Mihalis Yannakakis. The Node-Deletion Problem for Hereditary Properties is NP-Complete. Journal of Computer and System Sciences, 20(2):219–230, 1980. doi:10.1016/0022-0000(80)90060-4. 1

[21] Wenjun Li and Binhai Zhu. A 2k-kernelization algorithm for vertex cover based on crown decomposition. Theoretical Computer Science, 739:80–85, 2018. doi:10.1016/J.TCS.2018.05.004. 8

[22] George L. Nemhauser and Leslie E. Trotter Jr. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8(1):232–248, 1975. doi:10.1007/BF01580444. 8

[23] Christophe Paul, Evangelos Protopapas, and Dimitrios M Thilikos. Graph Parameters, Universal Obstructions, and WQO. CoRR, abs/2304.03688, 2023. URL: https://arxiv.org/abs/2304.03688, arXiv:2304.03688. 4

[24] Christophe Paul, Evangelos Protopapas, and Dimitrios M. Thilikos. Universal obstructions of graph parameters, 2023. arXiv:2304.14121. 4

[25] Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995. doi:10.1006/jctb.1995.1006. 3, 14

[26] Neil Robertson and Paul D. Seymour. Graph Minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004. doi:10.1016/j.jctb.2004.08.001. 3, 4, 16

[27] Neil Robertson and Paul D. Seymour. Graph Minors. XXI. Graphs with unique linkages. Journal of Combinatorial Theory, Series B, 99(3):583–616, 2009. doi:10.1016/j.jctb.2008.08.003. 3, 14

[28] Neil Robertson and Paul D. Seymour. Graph minors. XXII. Irrelevant vertices in linkage problems. Journal of Combinatorial Theory, Series B, 102(2):530–563, 2012. doi:10.1016/j.jctb.2007.12.007. 3, 14

[29] Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Parameterizing the quantification of CMSO: model checking on minor-closed graph classes, 2024. arXiv:2406.18465. 3, 15

[30] Dimitrios M. Thilikos and Sebastian Wiederrecht. Excluding surfaces as minors in graphs, 2024. arXiv:2306.01724. 2

[31] Mihalis Yannakakis. Edge-deletion problems. SIAM Journal on Computing, 10(2):297–309, 1981. doi:10.1137/0210021. 1