Paloma T Lima
email: paloma.lima@uib.no

Vinicius F Dos Santos
email: viniciussantos@dcc.ufmg.br

Ignasi Sau
email: ignasi.sau@lirmm.fr

Uéverton S Souza
email: ueverton@ic.uff.br

Reducing graph transversals via edge contractions

Keywords: 2012 ACM Subject Classification Theory of computation →, edge contraction, graph transversal, parameterized complexity, vertex cover, feedback vertex set, odd cycle transversal

For a graph invariant π, the Contraction(π) problem consists of, given a graph G and positive integers k, d, deciding whether one can contract k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] studied the case where π is the size of a minimum dominating set. We focus on graph invariants defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection H according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in H, in particular implying that Contraction(π) is co-NP-hard for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.

Introduction

Graph modification problems play a central role in algorithmic graph theory and have been widely studied in the last few years [START_REF] Hans | Graph modification problems (dagstuhl seminar 14071)[END_REF][START_REF] Crespelle | A survey of parameterized algorithms and the complexity of edge modification[END_REF][START_REF] Fedor | Graph modification problems: A modern perspective[END_REF]. In this kind of problem, given a graph, we want to perform a small number of modifications so that the resulting graph satisfies a desired property. Typically, this property is described as a graph class to which the resulting graph must belong, and the corresponding problem is usually NP-hard [START_REF] Lewis | The Node-Deletion Problem for Hereditary Properties is NP-Complete[END_REF][START_REF] Watanabe | On the NP-hardness of edgedeletion and -contraction problems[END_REF][START_REF] Yannakakis | Node-and Edge-Deletion NP-Complete Problems[END_REF]. Numerous famous problems can be stated as graph modification problems. For instance, if the operation is vertex deletion and the target graph class is that of forests, we obtain the well-known Feedback Vertex Set problem. A distinct type of graph modification problem that has been considered more recently is concerned with graph invariants1 , instead of graph classes.

The goal here is to perform a small number of modifications in order to decrease (or increase) a given invariant of the input graph. These are the so-called blocker problems, the main object of study in this work. More precisely, in a blocker problem with invariant π, given a graph G and a set M of graph modification operations, the question is whether G can be modified into a graph G such that π(G ) ≤ π(G) -d, for some threshold d, via at most k operations from M. The name blocker comes from the fact that the set of vertices or edges involved in the modifications can be viewed as "blocking" the invariant π, that is, preventing π from being smaller, as we would like in a minimization problem. Identifying parts of the graph that are responsible for an increase in a graph invariant gives useful information about the graph structure and has been the central question around many graph problems. For instance, if the invariant in question is the size of a longest path, d = 1 and the operation is vertex deletion, the problem becomes equivalent to testing whether there exists a set of k vertices that intersects every longest path of the input graph [START_REF] Márcia | Transversals of longest paths[END_REF][START_REF] Márcia | Intersection of longest paths in graph classes[END_REF][START_REF] Chen | Nonempty intersection of longest paths in series-parallel graphs[END_REF][START_REF] Rautenbach | Transversals of longest paths and cycles[END_REF]. Another example is that of computing the Hadwiger number of a graph. The Hadwiger Number problem takes as input a graph G and an integer t, and asks whether there exists a set of edges in G the contraction of which results in a graph isomorphic to the complete graph on t vertices [START_REF] Bollobás | Hadwiger's Conjecture is True for Almost Every Graph[END_REF][START_REF] Fedor | Computation of hadwiger number and related contraction problems: Tight lower bounds[END_REF][START_REF] Golovach | Hadwiger number of graphs with small chordality[END_REF]. This problem can be formulated as a blocker problem with the edge contraction operation, the invariant being the independence number (denoted by α), k = |V (G)| -t, and d = α(G) -1.

Because of their relevance and connection to other well-studied graph problems, blocker problems have been investigated for numerous graph invariants, such as the chromatic number, the independence number, the matching number, the diameter, the domination number, the total domination number, and the clique number of a graph [2-4, 10, 16, 22, 23, 31, 34, 35, 38]. The set M has so far been restricted to contain a single operation, usually vertex deletion, edge deletion, edge addition, or edge contraction. In this work, we restrict ourselves to the edge contraction operation. Formally, we are interested in the following problem, where π is any graph invariant.

Input:

A graph G and two positive integers k, d.

Question:

Can G be k-contracted into a graph G such that π(G ) ≤ π(G) -d?

Contraction(π)

When k and d are fixed instead of being part of the input, we denote the corresponding problem by k-Contraction (π, d). Blocker problems with the edge contraction operation have already been studied with respect to the chromatic number, clique number, and independence number [START_REF] Öznur | Contraction and deletion blockers for perfect graphs and H-free graphs[END_REF][START_REF] Paulusma | Critical vertices and edges in H-free graphs[END_REF], and the domination number [START_REF] Galby | Reducing the domination number of graphs via edge contractions and vertex deletions[END_REF], denoted by χ, ω, α, and γ, respectively. These works address the problem from the point of view of graph classes. Diner et al. [START_REF] Öznur | Contraction and deletion blockers for perfect graphs and H-free graphs[END_REF] showed, among other results, that Contraction(π) is NP-complete restricted to split graphs for π ∈ {χ, α, ω}, but it is polynomial-time solvable in this graph class for fixed d in all three cases. Galby et al. [START_REF] Galby | Reducing the domination number of graphs via edge contractions and vertex deletions[END_REF] recently initiated the study of the problem for π = γ for the case d = 1, providing several negative and positive results restricted to particular graph classes, such as a polynomial-time algorithm for k-Contraction(γ, 1) on (P 5 + pK 1 )-free graphs, for any p ≥ 1. Galby et al. [START_REF] Galby | Reducing the domination number of graphs via edge contractions and vertex deletions[END_REF] also considered a variant of the blocker problem in which an edge is given as part of the input. Namely, they showed that the problem of deciding whether the contraction of this specific edge decreases the domination number of a graph admits no polynomial-time algorithm unless P=NP. We observe here that their proof [START_REF] Galby | Reducing the domination number of graphs via edge contractions and vertex deletions[END_REF]Theorem 3.13] in fact works for any graph invariant satisfying two specific conditions, as stated in the following proposition.

Proposition 1 (Galby et al. [START_REF] Galby | Reducing the domination number of graphs via edge contractions and vertex deletions[END_REF]). Let π be a graph invariant such that (i) it is NP-hard to compute the π-number of a graph and (ii) contracting an edge reduces π by at most one.

Then, there exists no polynomial-time algorithm deciding whether contracting one given edge decreases the π-number of a graph, unless P=NP.

In this work, the invariants we focus on are H-transversals, that is, the minimum size of a vertex set of a graph that hits all the occurrences of graphs in a fixed (finite or infinite) collection H according to a specified containment relation ≺. We denote this invariant by τ ≺ H . Note that distinct instantiations of H and ≺ capture, for instance, the vertex cover, feedback vertex set, and odd cycle transversal numbers, and that these three invariants satisfy the conditions of Proposition 1.

Our results and techniques. We show (Theorem 4) that 1-Contraction(τ ≺ H , 1) is co-NP-hard when H is a family of 2-connected graphs containing at least one non-complete graph and ≺ is any of the subgraph, induced subgraph, minor, or topological minor containment relations. This implies that it is co-NP-hard to test whether we can reduce the feedback vertex set number or the odd cycle transversal number of a graph by performing one edge contraction. Note that this result is not implied by Proposition 1, since we do not specify which edge should be contracted. We also show (Theorem 9) that the problem is co-NP-hard if H is a family of cliques of size at least three and ≺ is the minor or topological minor containment relation. The same holds (Theorem 10) if H is a family of graphs containing a path on at least four vertices and any collection of 2-connected graphs and ≺ is the subgraph, induced subgraph, minor, or topological minor containment relation. All these reductions are from the 3-Sat problem restricted to clean formulas (see Section 2 for the definition).

We point out that, as can be seen by earlier results and the ones mentioned above, blocker problems are generally very hard, and become polynomial-time solvable only when restricted to specific graph classes. However, we show that the picture changes completely when the invariant in question is the vertex cover number of a graph (denoted by vc): we prove (Theorem 15) that Contraction(vc) can be solved in XP time parameterized by d on general graphs, hence in polynomial time for fixed d, in particular for d = 1. This result should be compared to Proposition 1, which shows that the problem is hard for d = 1 if the edge to be contracted is prescribed. Note that since the contraction of an edge may drop the minimum vertex cover of a graph by at most one, we may assume that k ≥ d (as otherwise the answer is trivially 'No'), hence parameter d is stronger than k. Our algorithm (cf. Algorithm 1) starts by checking whether the bipartite contraction number of G (i.e., the minimum number of edges to be contracted in order to obtain a bipartite graph), denoted by bc(G), is at most d -1. This can be done in FPT time by a result of Heggernes et al. [START_REF] Heggernes | Obtaining a bipartite graph by contracting few edges[END_REF], later improved by Guillemot and Marx [START_REF] Guillemot | A faster FPT algorithm for Bipartite Contraction[END_REF]. If bc(G) ≥ d, a simple argument allows to conclude that we are dealing with a Yes-instance. Otherwise, we distinguish two cases depending on whether G contains a connected component C with vc(C) > d or not. If it is not the case, we show (Lemma 13) that the problem can be solved in FPT time by combining a formulation in MSO 2 logic and a dynamic programming algorithm. Otherwise, we prove that we may assume (Lemma 12) that k < 2d, which enables us to enumerate all subsets F ⊆ E(G) of size at most k and, for each of them, solve the problem in FPT time by a branching algorithm, exploiting the fact that vc can be computed in polynomial time on bipartite graphs.

Finally, we also show that a small modification of the above algorithm yields (Corollary 16) that the problem of determining the minimum number of edges to be contracted to drop the vertex cover number of a graph by d can be 2-approximated in FPT-time parameterized by d.

Organization.

In Section 2 we provide some preliminaries and formally define all the problems mentioned throughout the text. In Section 3 we prove the co-NP-hardness results, and in Section 4 we present the algorithms for reducing the size of a minimum vertex cover via edge contractions. We conclude the article in Section 5 with some further observations and directions for further research.

Preliminaries

Graph notation. We use standard graph-theoretic notation, and we refer the reader to [START_REF] Diestel | Graph Theory[END_REF] for any undefined notation.

G (v) (resp. N G [v]
). We may drop the subscript if the graph G is clear from the context. The contraction of an edge e = {u, v} in a graph G results in a graph G obtained from G by removing u and v, and adding a new vertex v e with N G (v e ) = N G (u) ∪ N G (v). We denote by G/e the graph obtained from G by contracting an edge e, and if F ⊆ E(G), we denote by G/F the graph obtained from G by contracting all the edges in F , in any order; it is easy to verify that the resulting graph does not depend on the order in which the contractions are applied.

If |F | = k, we say that G is k-contracted into G/F .
A vertex cover (resp. feedback vertex set, odd cycle transversal) of a graph G is a set S ⊆ V (G) such that G \ S is edgeless (resp. acyclic, bipartite). We denote the minimum size of a vertex cover (resp. feedback vertex set, odd cycle transversal) of a graph G by vc(G)

(resp. fvs(G), oct(G)). Note that, if G is connected, vc(G) = 1 if and only if G is a star.
A graph H is a minor of a graph G if it can be obtained from G by removing vertices, deleting edges, and contracting edges. A graph H is a topological minor of a graph G if it can be obtained from G by removing vertices, deleting edges, and contracting edges having at least one vertex of degree at most two. The operation of subdividing an edge {u, v} consists in deleting the edge {u, v} and adding a new vertex w adjacent to u and v.

Graph transversals. For a fixed graph containment relation ≺ and a fixed (finite or infinite) collection of graphs H, we define the invariant τ ≺ H such that, for every graph G, τ ≺ H (G) is equal to the minimum size of a set S ⊆ V (G) such that G \ S does not contain any of the graphs in H according to containment relation ≺.

If H = {H}, we denote τ ≺ {H} by τ ≺ H . Such a set S is called an H-transversal or an H-hitting set.
For instance, if ≺ is the minor relation and H is an edge (resp. a triangle), then τ ≺ H is the size of a minimum vertex cover (resp. feedback vertex set), which we abbreviate as vc (resp. fvs). On the other hand, if ≺ is the subgraph relation and H contains all odd cycles, then τ ≺ H is the size of a minimum odd cycle transversal, which we abbreviate as oct.

Definition of the problems. For a graph invariant π, we also consider the versions of the

Input:

A graph G and a positive integer d.

Output:

The minimum integer

k such that G be k-contracted into a graph G such that π(G ) ≤ π(G) -d.

Min-Contraction(π)

Parameterized complexity. We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions. A parameterized problem is a decision problem whose instances are pairs (x, k) ∈ Σ * × N, where k is called the parameter. A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f , and a constant c such that given an instance I = (x, k), A (called an FPT algorithm) correctly decides whether I ∈ L in time bounded by f (k) • |I| c . A parameterized problem is slice-wise polynomial (XP) if there exists an algorithm A and two computable functions f, g such that given an instance I = (x, k), A (called an XP algorithm) correctly decides whether k) . Within parameterized problems, the class W[1] may be seen as the parameterized equivalent to the class NP of classical optimization problems. Without entering into details (see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for the formal definitions), a parameterized problem being W[1]-hard can be seen as a strong evidence that this problem is not FPT. The canonical example of W[1]-hard problem is Independent Set parameterized by the size of the solution. To transfer W[1]hardness from one problem to another, one uses a parameterized reduction, which given an input I = (x, k) of the source problem, computes in time f (k) • |I| c , for some computable function f and a constant c, an equivalent instance I = (x , k ) of the target problem, such that k is bounded by a function depending only on k. An equivalent definition of W[1]-hard problem is any problem that admits a parameterized reduction from Independent Set parameterized by the size of the solution.

I ∈ L in time bounded by f (k) • |I| g(
Treewidth and Courcelle's Theorem. For an integer k ≥ 1, a k-tree is a graph that be obtained from a k-clique by recursively adding vertices adjacent to a k-clique of the current graph. The treewidth of a graph G, denoted by tw(G), is the smallest integer k such that G is a subgraph of a k-tree. The syntax of monadic second order (MSO 2 ) logic of graphs includes the logical connectives ∨, ∧, ¬, variables for vertices, edges, sets of vertices and sets of edges, the quantifiers ∀, ∃ that can be applied to these variables, and the binary relations expressing whether a vertex or an edge belong to a set, whether an edge is incident to vertex, whether two vertices are adjacent, and whether two sets are equal. The following result of Courcelle [START_REF] Courcelle | The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs[END_REF], as well as one of its several optimization variants [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF], is one of the most widely used results in the area of parameterized complexity.

Proposition 2 (Courcelle [11], Arnborg et al. [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF]). Checking whether an MSO 2 formula ϕ holds on an n-vertex graph of treewidth at most tw can be done in time f (ϕ, tw) • n, for a computable function f . Moreover, within the same running time, one can find a vertex or edge set of G of maximum or minimum size that satisfies ϕ.

Exponential Time Hypothesis and clean 3-Sat. The Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi [START_REF] Impagliazzo | On the Complexity of k-SAT[END_REF] implies that the 3-Sat problem on n variables cannot be solved in time 2 o(n) . The Sparsification Lemma of Impagliazzo et al. [START_REF] Impagliazzo | Which Problems Have Strongly Exponential Complexity[END_REF] implies that if the ETH holds, then there is no algorithm solving a 3-Sat formula with n variables and m clauses in time 2 o(n+m) . Using the terminology from Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF], a 3-Sat formula ϕ, in conjunctive normal form, is said to be clean if each variable of ϕ appears exactly three times, at least once positively and at least once negatively, and each clause of ϕ contains two or three literals and does not contain twice the same variable. Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF] observed the following useful lemma. Lemma 3 (Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF]). The problem of deciding whether a clean 3-Sat formula with n variables is satisfiable is NP-hard, and the existence of an algorithm in time 2 o(n) to solve it would violate the ETH.

Hardness results

We start with some definitions that will be used in the reductions of this section. Let G and H be two graphs, let u, v ∈ V (H), and let {x, y} ∈ E(G). By replacing {x, y} by H u,v we mean deleting edge {x, y} from G, adding a copy of H and identifying vertices u and v of H with vertices x and y of G, respectively. The operation of replacing {x, y} by two copies of H u,v is defined similarly, except that we add two copies of H and we identify vertices u and v of both copies of H with vertices x and y of G, respectively. By attaching H u to x ∈ V (G) we mean adding a copy of H and identifying vertex u of H with vertex x of G, and by attaching a pendent H u to x ∈ V (G) we mean adding a copy of H and an edge between vertex u of H and vertex x of G. We denote by H 2 u the graph obtained from two copies of H by identifying vertex u in each of the copies.

Theorem 4. Let H be a collection of 2-connected graphs containing at least one noncomplete graph. Then 1-Contraction(τ ≺

H , 1) is co-NP-hard, for ≺ being any of the subgraph, induced subgraph, minor, or topological minor containment relations. Moreover, the problem cannot be solved in subexponential time assuming the ETH, even restricted to graphs with maximum degree depending on H.

Proof. We present a reduction from the 3-Sat problem restricted to clean formulas, which is NP-hard by Lemma 3. Namely, given a clean formula ϕ with n variables and m clauses, we will construct in polynomial time an instance G H ϕ such that ϕ is satisfiable if and only if G H ϕ is a No-instance of 1-Contraction(τ ≺ H , 1). We start by constructing a graph G ϕ that will be reused in the other reductions of this section, and which is inspired by the classical NP-hardness reduction [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] from 3-Sat to Vertex Cover.

For each variable x of ϕ and for each clause C containing x in a literal ∈ {x, x}, we add to G ϕ a new vertex a x,C, . We also introduce another "dummy" vertex a x . Since ϕ is clean, we have introduced four vertices in G ϕ for each variable x. Let a x,C1, , a x,C2, ¯ , a x,C3, , a x be the four introduced vertices (recall that x appears at least once positively and negatively in ϕ). We add the following four edges, inducing a C 4 : (a x,C1, , a x,C2, ¯ ), (a x,C2, ¯ , a x,C3, ), (a x,C3, , a x ), and (a x , a x,C1, ). We denote by A the union of all the vertices in these variable gadgets.

For each clause C of ϕ and for each literal in C, we add to G ϕ a new vertex b C, . Since ϕ is clean, we have introduced two or three vertices in G ϕ for each clause C. We add an edge between every pair of these vertices, hence inducing a clique of size two or three. We denote by B the union of all the vertices in these clause gadgets.

Finally, for each variable x of ϕ and for each clause C containing x in a literal ∈ {x, x}, we add to G ϕ an edge between a x,C, ∈ A and b C, ∈ B. This concludes the construction of G ϕ , which we proceed to modify. Note that

V (G ϕ ) = A ∪ B.
Let H ∈ H be a non-complete 2-connected graph, and let u, v be two non-adjacent vertices in H. Starting from G ϕ , we replace each of the edges between two vertices in A or two vertices in B by two copies of H u,v , and each edge between a vertex in A and a vertex in B by one copy of H u,v . Each of these copies of H is called an A-copy, B-copy, or AB-copy, depending on whether its attachment vertices are both in A, both in B, or one in A and one in B, respectively.

Finally, for each AB-copy of H, we choose arbitrarily within it a vertex z distinct from u and v, and we attach a pendent copy of H 2 u to z. These newly added copies of H are called pendent copies, the edge linking them to its corresponding AB-copy of H is called the pendent edge of that AB-copy of H, and the vertex in the AB-copy incident with the pendent edge is called the base vertex of that AB-copy of H. This concludes the construction of G H ϕ ; see Figure 1 for an example for H containing all cycles and H = C 4 . We can clearly assume that H is an antichain with respect to ≺, that is, that its elements are pairwise incomparable with respect to ≺. Assume for the sake of presentation that ≺ is the subgraph relation, and we omit it from the notation τ ≺ H ; at the end of the proof we will argue that the same arguments apply as well to the other containment relations listed in the statement of the theorem. Note that G H ϕ contains 2n pairwise vertex-disjoint A-copies of H and 3n pairwise vertex-disjoint pendent copies of H, taking into account that each variable appears exactly three times in ϕ. On the other hand, since for clause C of ϕ the vertices {b C, | ∈ C} ⊆ B induce a clique in G ϕ , for each clause C of ϕ at least |C| -1 vertices of G H ϕ are needed to hit the B-copies of H among the vertices {b C, | ∈ C} ⊆ B, where |C| denotes the number of literals in C. Therefore, using ϕ that is clean, it follows that

a x,C 1 , a x,C 2 , ¯ a x,C 3 , a x b C 1 , 2 b C 1 , 1 b C 1 , 3
τ H (G H ϕ ) ≥ 2n + 3n + C∈ϕ (|C| -1) = 8n -m. ( 1
)
We present three claims that, together, will conclude the proof of the theorem.

Claim 5. τ H (G H ϕ ) = 8n -m if and only if ϕ is satisfiable.
Proof. Suppose first that ϕ is satisfiable, and let α be an assignment of the variables that satisfies all the clauses in ϕ. We define a set X ⊆ V (G H ϕ ) as follows. For each variable x, add to X all vertices a x,C, such that α( ) is true. If only one vertex was added in the previous step, add to X vertex a x as well. For each clause C, choose a literal that satisfies C, and add to X the set {b C, | = }. Finally, for each pendent copy of H, add to X its corresponding vertex u. By construction we have that |X| = 8n -m, hence by Equation ( 1) we just have to verify that G H ϕ \ X does not contain any of the graphs in H as a subgraph. Note that by the choice of X, it contains at least one vertex of each A-copy, B-copy, and pendent copy of H, and since α is a satisfying assignment, X contains at least one vertex of each AB-copy of H as well. Let F be a connected component of G H ϕ \ X. Since by hypothesis all the graphs in H are 2-connected, it suffices to verify that no 2-connected component F of F contains one of the graphs in H as a subgraph. By the construction of G H ϕ , the choice of X, and the fact that X hits all copies of H in G H ϕ , it follows that such a 2-connected component F is a proper subgraph of H. Since H is an antichain, F cannot contain any of the graphs in H as a subgraph, and we are done.

Conversely, suppose that there exists X ⊆ V (G H ϕ ) with |X| ≤ 8n -m such that G H ϕ \ X does not contain any of the graphs in H, in particular H, as a subgraph. By Equation (1), we have that |X| = 8n -m. By construction of G H ϕ and the fact that |X| = 8n -m (see the paragraph above Equation ( 1)), it follows that X must contain exactly one of the pairs {a x,C1, , a x,C3, } and {a x , a x,C2, ¯ } for each variable x, and exactly |C| -1 vertices in {b C, | ∈ C} for each clause C. We define the following assignment α of the variables: for each variable x, let ∈ {x, x} such that a x,C, ∈ X for some clause C. Then we set α(x) to true if = x, and to false if = x. By the above discussion, this is a valid assignment. Consider a clause C of ϕ, and let be the literal in C such that b C, / ∈ X. Since G H ϕ \ X does not contain H as a subgraph, there must exist a variable x ∈ { , ¯ } such that a x,C, ∈ X, as otherwise the AB-copy of H between b C, and a x,C, would be an occurrence of H in G H ϕ \ X. By the definition of α, necessarily α( ) is true, and therefore α satisfies C. Since this argument holds for every clause, we conclude that ϕ is satisfiable.

Claim 6. If τ H (G H ϕ ) = 8n -m,
(|C| -1) = 8n -m = τ H (G H ϕ ),
and the claim follows.

Claim 7. If τ H (G H ϕ ) > 8n -m, then there is an edge e such that τ H (G H ϕ /e) < τ H (G H ϕ ).
Proof. Let X ⊆ V (G H ϕ ) be an H-hitting set of minimum size. We call a vertex in a copy of H in G H ϕ internal if it is distinct from its attachment vertices (cf. Figure 1). We proceed to construct another H-hitting set X ⊆ V (G H ϕ ) with canonical properties, such that

1. |X | ≤ |X|, 2.
X contains exactly either {a x,C1, , a x,C3, } or {a x , a x,C2, ¯ } for each variable x, 3. X contains exactly |C| -1 vertices in the set {b C, | ∈ C} for each clause C, 4. X contains exactly one vertex in each pair of pendent copies of H, 5. X contains no internal vertex of an A-copy, B-copy, or pendent copy of H, and 6. all internal vertices of AB-copies of H that are in X are base vertices.

Note that Property 1 above implies that

|X | = |X| = τ H (G H ϕ ) > 8n -m.
We construct the set X via the following procedure:

1. Start with X = X.

For each A-copy, B-copy, or pendent copy H of H in G H

ϕ such that X contains at least one internal vertex in H, remove from X all internal vertices of H, and add to X any of the attachment vertices of H, which may already be in X .

3.

For each variable x, let X x = X ∩ {a x,C1, , a x,C2, ¯ , a x,C3, , a x }. If |X x | ≥ 3, let P be one of the pairs {a x,C1, , a x,C3, } and {a x , a x,C2, ¯ } such that P ⊆ X . Remove X x \ P from X and, for every vertex v ∈ X x \ P with v = a x , add to X an arbitrarily chosen internal vertex in the AB-copy of H containing v, which may already be in X .

For each clause C, let X

C = X ∩ {b C, | ∈ C}. Note that by construction of G H ϕ and Step 2 above, |X C | ≥ |C| -1. If |X C | = |C|, remove from X an arbitrarily chosen vertex v ∈ {b C, | ∈ C},
and add to X an arbitrarily chosen internal vertex in the AB-copy of H containing v, which may already be in X .

For each AB-copy H of H in G H

ϕ such that X contains at least one internal vertex in H, remove from X all internal vertices of H, and add to X the base vertex of H, which may already be in X .

Let X be the set obtained at the end of the above procedure. It can be easily verified that X satisfies the desired Properties 1-6. In order to see that X is a H-hitting set, note that, by construction of G H ϕ , each vertex in A ∪ B is contained in at most one AB-copy of H. Thus, in Steps 3 and 4 of the above procedure, when we swap vertices in A ∪ B by internal vertices in AB-copies of H, we guarantee that the currently constructed set X is still a H-hitting set. Clearly, this property is also preserved in Steps 2 and 5.

We now proceed, using the constructed H-hitting set X , to identify an edge e

∈ E(G H ϕ ) such that τ H (G H ϕ /e ) < |X | = τ H (G H ϕ ), concluding the proof of the claim. Since by hypothesis |X | = τ H (G H ϕ ) ≥ 8n -m + 1
, Properties 1-6 of X imply that X contains at least one base vertex z in an AB-copy H of H. Let s be the vertex in the pendent copies of H such that {z, s} ∈ E(G H ϕ ); hence {z, s} is the pendent edge of H (cf. Figure 1). By Property 5 of X , it follows that z ∈ X . Let e = {z, s}, and let w be the vertex in G H ϕ /e resulting from the contraction of e . Since both z, s ∈ X , it can be easily verified that the set

X := (X \ {z, s}) ∪ {w} is a H-hitting set of G H ϕ /e with |X | = |X | -1. Therefore, τ H (G H ϕ /e ) ≤ |X | < |X | = τ H (G H ϕ ),
and the claim follows.

Claims 5, 6, and 7 together imply that ϕ is satisfiable if and only if G H ϕ is a No-instance of 1-Contraction(τ ≺ H , 1) for the subgraph relation, as we wanted to prove. Let us now argue that the same proof applies when ≺ is another of the graph containment relations stated in the theorem. Indeed, by construction of G H ϕ , the hypothesis that all the graphs in H are 2-connected, and the fact that H is an antichain, it follows that if X is an H-hitting set for some of these containment relations, none of the graphs in H occurs in G H ϕ \ X nor in (G H ϕ /e) \ X for any edge e, for any of the subgraph, induced subgraph, minor, or topological minor containment relations.

Finally, the latter statement in the theorem follows easily from Lemma 3 and by observing that, since the construction of G H ϕ depends on a fixed graph H ∈ H, it follows that

|V (G H ϕ )| = O(n) and ∆(G H ϕ ) ≤ 5 • ∆(H).
From Theorem 4 we immediately get the following corollary.

Corollary 8. 1-Contraction(π, 1) is co-NP-hard if π = fvs or π = oct.
Proof. For π = fvs (resp. π = oct), we apply Theorem 4 for H being the collection of all cycles (resp. odd cycles) and ≺ being the subgraph relation.

Note that we can also obtain hardness results assuming that the input graph of the considered problem is planar (and some graph in H as well), by reducing from planar versions of 3-Sat.

More interesting is the fact the proof of Theorem 4 does not work if either all the graphs in H are cliques, or if H contains some graph that is not 2-connected. Indeed, in the proof of Claim 6 we crucially used the fact that the vertices u, v ∈ V (H) are not adjacent, so that the contraction of any edge e still leaves intact one of each pair of copies of H in G H ϕ /e. On the other hand, if H contains a graph H that is not 2-connected, Claim 5 does not hold anymore: such a graph H may occur in the graph G H ϕ \ X considered in the first part of the proof, hence X may not be an H-hitting set of G H ϕ anymore. We now present two hardness results for families H in which we drop one of the two assumptions discussed above, namely complete graphs and families containing paths.

In the next theorem we prove, using a simple trick, co-NP-hardness when H consists of complete graphs, for the minor and topological minor containment relations. Note that we may assume that the complete graphs have at least three vertices, as otherwise the problem can be solved in polynomial time by Theorem 15.

Theorem 9. Let H be a collection of cliques, each having at least three vertices. Then 1-Contraction(τ ≺

H , 1) is co-NP-hard, for ≺ being the minor or topological minor containment relations.

Proof. Let H

• = {H • | H ∈ H}
, where H • is the graph obtained from H by subdividing each edge once. (If H is the minor relation, we may assume that H contains only one clique.) Since all the graphs in H are cliques on at least three vertices, H • is a collection of 2-connected graphs none of which is a clique, hence Theorem 4 can be applied to it. Given a clean 3-Sat formula ϕ, let G H • ϕ be the graph constructed in the proof of Theorem 4 for the family H • . Claims 5, 6, and 7 together imply that ϕ is satisfiable if and only if

G H • ϕ is a No-instance of 1-Contraction(τ ≺ H • , 1)
for the subgraph relation. The important observation is that, by construction, in both G H • ϕ and G H • ϕ /e for any edge e, the gadgets that we attach to a pair of vertices, as well as their proper subgraphs once we delete a H • -hitting set, contain a graph in H • as a subgraph if and only if they contain one of the cliques in H as a minor or as a topological minor, and the same proof yields the claimed result.

Note that the proof of Theorem 9 does not work for the subgraph or induced subgraph containment relations: in that case, the constructed graph G H • ϕ does not contain any clique of size at least three.

In our next theorem we change appropriately the construction of the graph G H ϕ defined in the proof of Theorem 4 to obtain a hardness result when H consists of a path on at least four vertices and any collection of 2-connected graphs, for any of the containment relations discussed above. Proof. We present again a reduction from the 3-Sat problem restricted to clean formulas, similar in spirit to that of Theorem 4. Given a clean formula ϕ with n variables and m clauses, we will construct in polynomial time an instance G H ϕ such that ϕ is satisfiable if and only if G H ϕ is a No-instance of 1-Contraction(τ ≺ H , 1). We start with the same graph G ϕ defined in the proof of Theorem 4, and we modify it as follows. In order to define the graph G H ϕ , we distinguish two cases according to the parity of i, the number of vertices in H = P i . In this proof, whenever we attach a path, we choose as attachment vertices the endvertices of the path.

If i ≥ 4 is even, we replace each of the edges between two vertices in A or two vertices in B by a P i 2 +1 , and we attach a P i 2 to each vertex in A ∪ B. If i ≥ 5 is odd, we replace each of the edges between two vertices in A or two vertices in B by a P i+1 2 , and we attach a P i+1 2 to each vertex in A ∪ B. The remainder of the construction of G H ϕ is the same for both i even and odd. We replace each edge between a vertex in A and a vertex in B by a P 3 (note that this does not depend on i) and, for each such a P 3 , let z be the internal vertex in it. Attach a pendent copy of H 2 u to z, where H = P i and u is one of the endvertices of P i . This concludes the construction of G H ϕ ; see Figure 2 for examples for H = P 4 and H = P 5 . Again, suppose first that ≺ is the subgraph relation. The main properties of G H ϕ are the same as in Theorem 4: we may assume that a minimum P i -hitting set

a x,C 1 , a x,C 2 , ¯ a x,C 3 , a x b C 1 , 2 b C 1 , 1 b C 1 , 3 z (a) (b) a x,C 1 , a x,C 2 , ¯ a x,C 3 , a x b C 1 , 2 b C 1 , 1 b C 1 , 3 z s s
X ⊆ V (G H ϕ )
contains exactly one of the pairs {a x,C1, , a x,C3, } and {a x , a x,C2, ¯ } for each variable x, that X contains exactly |C| -1 vertices in the set {b C, | ∈ C} for each clause C, and that X contains precisely the attachment vertex of every copy of H 2 u (cf. vertices s in Figure 2). Note that since all the graphs in H \ {P i } are 2-connected by hypothesis, and for any P i -hitting set X every connected component of G H ϕ \ X is a tree, it follows that any P i -hitting set of G H ϕ is also an H-hitting set of G H ϕ . Moreover, by construction of G H ϕ , these properties are preserved in G H ϕ /e for any edge e ∈ E(G H ϕ ). Taking into account the above discussion, it can be verified that the current graph G H ϕ satisfies Claims 5, 6, and 7 in the proof of Theorem 4, by using the same arguments; we omit the details. Thus, ϕ is satisfiable if and only if G H ϕ is a No-instance of 1-Contraction(τ ≺ H , 1) for the subgraph relation, as we wanted to prove. As for other containment relations, let X be a P i -hitting set for some of the considered relations. Since P i or any 2-connected graph in H does not occur in G H ϕ \ X nor in (G H ϕ /e) \ X for any edge e, for any of the subgraph, induced subgraph, minor, or topological minor relations, the same arguments apply.

Note that the proof of Theorem 10 does not work for H = P 3 . Indeed, in the construction of G H ϕ for odd i, we replace the edges with both endvertices in A or in B by a P i+1

2

; for i = 3 this results in an edge between such a pair, whose contraction would identify both vertices, hence violating the main properties of the reduction.

Finally, note also that, as in Theorem 4, the reductions given in Theorem 9 and Theorem 10 also rule out the existence of subexponential algorithms assuming the ETH.

case of Vertex Cover

In this section we focus on the case where the considered invariant π is the size of a minimum vertex cover or, equivalently, where π = τ ≺ K2 for ≺ being any of the subgraph, induced subgraph, minor, or topological minor containment relations. Recall that we use the notation vc to denote τ ≺ K2 . It is easy to see that Contraction(vc) is NP-hard, even if we assume that the value vc(G) is given along with the input. Indeed, the particular case d = vc(G) -1 is the problem of reducing the vertex cover number of the (connected) input graph G to one (i.e., obtaining a star) by doing at most k edge contractions. This problem is known in the literature as Star Contraction [START_REF] Heggernes | Contracting graphs to paths and trees[END_REF][START_REF] Krithika | Lossy kernels for graph contraction problems[END_REF] and is equivalent to Connected Vertex Cover (see [START_REF] Krithika | Lossy kernels for graph contraction problems[END_REF] for a proof), which is known to be NP-hard even on graphs for which computing a minimum vertex cover can be done in polynomial time, such as bipartite graphs [START_REF] Escoffier | Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs[END_REF]. Following Heggernes et al. [START_REF] Heggernes | Obtaining a bipartite graph by contracting few edges[END_REF], a 2-coloring of a graph G is a function φ : V (G) → {1, 2}, and we denote by V 1 φ and V 2 φ the sets of vertices of V (G) colored 1 and 2, respectively. A set

X ⊆ V (G) is a monochromatic component of φ if G[X] is a connected component of G[V 1 φ ] or G[V 2
φ ], and we denote by M φ the set of all monochromatic components of φ. The cost of a 2-coloring φ is defined as cost(φ) = X∈M φ (|X| -1). We will need the following lemma.

Lemma 11 (Heggernes et al. [28]). A graph G has a 2-coloring of cost at most k if and only if there exists a set F ⊆ E(G) of at most k edges such that G/F is bipartite.

The following simple observation concerning the 1-Contraction(vc, 1) problem is the key insight to the algorithm of Theorem 15. Let G be a graph and let X be a minimum vertex cover of G. We define a 2-coloring φ of G as follows. For every vertex

v ∈ V (G), φ(v) = 1 if v ∈ X, and φ(v) = 2 otherwise. Since X is a vertex cover, G[V 2 φ ] is edgeless. Consider the graph G[V 1 φ ] = G[X],
and distinguish two cases according to whether G is bipartite or not. If it is not, then since G[V 2 φ ] is edgeless, necessarily G[X] contains some edge e (equivalently, cost(φ) ≥ 1). Then contracting e results in a graph having a vertex cover of size at most vertex cover. The remaining graph is bipartite, hence we can compute a minimum vertex cover of it in polynomial time. Note that this procedure works even if F = ∅, hence vc(G) can also be computed in time 2 O(d) • n O (1) . Therefore, to conclude the proof if it enough to find such a set B ⊆ V (G/F ).

Recall that we are in the case where bc(G) ≤ d -1. Let L ⊆ E(G) with |L| ≤ d -1 such that G/L is bipartite, obtained in time FPT in d by Proposition 14 (it is easy to see that the FPT algorithm for the decision version can also obtain in FPT time the corresponding set of edges to be contracted). Note that G \ V (L) is also bipartite. Let V F be the set of vertices in V (G/F ) resulting from the contraction of F . We

Conclusions and further research

We provided co-NP-hardness results for the 1-Contraction(τ ≺ H , 1) problem when H contains only 2-connected graphs and at least one of them is not a clique (Theorem 4), when H consists of cliques but only for the minor and topological minor containment relations (Theorem 9), and when H contains a path on at least four vertices and 2-connected graphs (Theorem 10). Several interesting cases remain open, for instance when H = {H} with H = P 3 , H = K h with h ≥ 3 (for the subgraph and induced subgraph relations), or H being an arbitrary tree. The cases where H may contain disconnected graphs seem to be trickier.

For the cases that are co-NP-hard, it is natural to parameterize the problem by τ ≺ H , that is, by the value of the parameter in the input graph G. If ≺ is the minor relation and H contains some planar graph, it is well-known [START_REF] Robertson | Graph minors. V. Excluding a planar graph[END_REF] that the treewidth of G is bounded by τ ≺ H (G) plus a function that depends only on H. In this case, the Contraction(τ ≺ H ) problem is FPT parameterized by τ ≺ H (G) + k, since it can be expressed by an MSO 2 formula with length depending only on k (note that we may assume that k ≥ d), and therefore it can be solved in time f (τ ≺ H (G), k) • n by Courcelle's Theorem [START_REF] Courcelle | The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs[END_REF]. In particular, this observation yields that when H = {K 3 }, the Contraction(fvs) problem is FPT parameterized by fvs + k.

When H = {K 2 }, that is, when τ ≺ H is the size of a minimum vertex cover, we proved that the Contraction(vc) problem parameterized by d is in XP (Theorem 15) and can be 2-approximated in FPT time (Corollary 16). The natural question is whether Contraction(vc) is FPT or W [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF]-hard parameterized by d. We tend to believe that the former case holds. In fact, we do not even know whether the problem is FPT parameterized by k (recall that we may assume that k ≥ d).

  Contraction(π) problem, defined in the Introduction, where one or both positive integers k and d are fixed, instead of being part of the input. Namely, we denote by k-Contraction(π), Contraction(π, d), and k-Contraction(π, d) the version of Contraction(π) in which k, d, and both k and d are fixed, respectively.Finally, we define the following optimization version of Contraction(π).

Figure 1

 1 Figure 1 Illustration of the graph G Hϕ for H containing all cycles and H = C4. Black (resp. white) vertices are attachment (resp. internal) vertices of the corresponding copies of H. Vertex z is the base vertex and {z, s} is the pendent edge of the depicted AB-copy of H.

Figure 2

 2 Figure 2 Illustration of the graph G H ϕ for (a) H = P4 and (b) H = P5.

Corollary 16 .

 16 set B := V (L) ∪ V F . Note that |B| ≤ |V (L)| + |V F | ≤ 2(d -1) + 2(2d -1) = O(d) and that (G/F ) \ B is a subgraph of G \ V (L), hence it is bipartite as well, and the theorem follows. From the XP algorithm given in Theorem 15 we easily get the following corollary. The Min-Contraction(vc) problem can be 2-approximated in FPT time parameterized by d. Proof. Let (G, d) be the input of the Min-Contraction(vc) problem, and let k 0 be the desired minimum number of contractions to drop the vertex cover number of G by at least d, so necessarily k 0 ≥ d. Note that the algorithm given in Theorem 15 (cf. Algorithm 1) either concludes that there is no feasible solution (in case k 0 < d), or concludes that k 0 = d (in case bc(G) < d), or solves optimally the Min-Contraction(vc) problem with input (G, d) (in case vc(C i ) ≤ d for every connected component C i of G), except in the case where there exists a component C of G such that vc(C) ≥ d + 1. That is, this algorithm in fact solves the Min-Contraction(vc) problem with input (G, d) except for this latter case, which is in fact the only step of the algorithm that is not FPT in d, since we need to enumerate the candidate sets F ⊆ E(G) of size at most 2d -1. But if we are aiming at a 2-approximation algorithm, in the case where there is a component C of G with vc(C) ≥ d + 1, we can just apply Lemma 12 directly and conclude that k 0 ≤ 2d. Since k 0 ≥ d, this yields a 2-approximation that runs in time FPT parameterized by d.

  H ϕ /e are needed to hit the B-copies of H among the vertices {b C, | ∈ C} ⊆ B. Thus, as by hypothesis τ H (G H ϕ ) = 8n -m, we have that τ H (G H ϕ /e) ≥ 2n + 3n +

	C∈ϕ
	Proof. Let e ∈ E(G H ϕ ) be an arbitrary edge, and consider the graph G H ϕ /e. Since in G H ϕ
	there are two copies of H between every pair of vertices in A and B within the same variable
	or clause gadget, respectively, two copies of H are attached to u in every pendent H 2 u , and u
	and v are not adjacent in H, it follows that, for each such a pair of copies of H, at least one
	of them still survives in G H ϕ /e.
	Therefore, G H

then there is no edge e such that τ H (G H ϕ /e) < τ H (G H ϕ ). ϕ /e still contains 2n pairwise vertex-disjoint A-copies of H, 3n pairwise vertex-disjoint pendent copies of H, and, for each clause C of ϕ, at least |C| -1 vertices of G

Theorem 10 .

 10 Let H = P i with i ≥ 4, and let H contain H and any collection of 2connected graphs. Then 1-Contraction(τ ≺ H , 1) is co-NP-hard, for ≺ being any of the subgraph, induced subgraph, minor, or topological minor containment relations.

We use "invariant" instead of parameter in order to avoid confusion with the parameter of the corresponding parameterized problem.

Acknowledgement. We would like to thank the anonymous reviewers of the conference and journal versions of this article for helpful remarks that improved the presentation of the manuscript.

Funding Vinicius F. dos Santos: Grant APQ-02592-16 Minas Gerais Research Support Foundation (FAPEMIG) and Grants 311679/2018-8 and 421660/2016-3 National Council for Scientific and Technological Development (CNPq). Ignasi Sau: CAPES-PRINT Institutional Internationalization Program, process 88887.371209/ 2019-00, and projects DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), ELIT (ANR-20-CE48-0008-01), and UTMA (ANR-20-CE92-0027). Uéverton S. Souza: Grant E-26/203.272/2017 Rio de Janeiro Research Support Foundation (FAPERJ) and Grant 303726/2017-2 National Council for Scientific and Technological Development (CNPq).

|X| -1, and therefore we can conclude that G is a Yes-instance of the 1-Contraction(vc, 1) problem. Otherwise, if G is bipartite, we can solve 1-Contraction(vc, 1) on G in polynomial time by first computing vc(G) in polynomial time using the fact that G is bipartite [START_REF] Diestel | Graph Theory[END_REF], and then computing vc(G/e) for every edge e ∈ E(G) in polynomial time as explained below. If for some e ∈ E(G), we have that vc(G/e) < vc(G), we answer 'Yes', otherwise we answer 'No'. To compute vc(G/e) in polynomial time, let w be the vertex resulting from the contraction of e and, letting G e := G/e, note that vc(G e ) = min{1 + vc(G e \ {w}) , |N (w)| + vc(G e \ N [w])}, and that both G e \ {w} and G e \ N [w] are bipartite, so a minimum vertex cover in them can be computed in polynomial time.

Summarizing, the algorithm to solve 1-Contraction(vc, 1) in polynomial time works as follows: we first check whether G is bipartite (in polynomial time). If it is not, we answer 'Yes' (without needing to compute any minimum vertex cover). If it is, we solve the problem in polynomial time as discussed above.

In Theorem 15 (cf. Algorithm 1) we generalize this idea to solve Contraction(vc, d) in polynomial-time for every fixed d ≥ 1. We first need some technical lemmas.

Lemma 12.

Let G be a graph, d ≥ 1 an integer, and

Proof. The main observation is that for any connected graph H such that vc(H) ≥ 2, any minimum vertex cover X of H contains two vertices u, v within distance at most two in H. Indeed, either H[X] contains an edge, and we choose u, v to be the endvertices of that edge, or since H is connected and vc(H) ≥ 2, necessarily there is a vertex in V (H) \ X with at least two neighbors in X, which we choose as u, v. In both cases, contracting a shortest path (of length at most two) between such vertices u and v results in a graph H with vc(H ) ≤ vc(H) -1.

Let G, d, and C be as in the statement of the lemma. Since vc(C) ≥ d + 1, we can recursively apply d times the above observation to C, hence obtaining a set F ⊆ E(C) ⊆ E(G) of size at most 2d such that vc(C/F ) ≤ vc(C) -d. Since the size of a minimum vertex cover is additive with respect to connected components, we have that vc(G/F ) ≤ vc(G) -d.

Lemma 13. Let G be a graph, d ≥ 1 an integer, and suppose that for every connected component

• n for some computable function f . For this, we just have to verify that the Min-Contraction(vc) problem on (C i , d ) can be expressed by an MSO 2 formula whose length depends only on d. Indeed, it consists of finding the minimum size of a set

To express the latter inequality by an MSO 2 formula with length depending on d, we crucially use the assumption that vc(C i ) ≤ d. To do this, we first compute := vc(C i ) independently with a standard MSO 2 formula (or with a standard branching algorithm, since we are assuming that vc(C i ) ≤ d). Then the inequality "vc(C i /F ) ≤ -d ", where we have that -d ≤ d, can be expressed as the existence of a set of vertices S := {v 1 , . . . , v -d } ⊆ V (C i ) such that every edge in E(C i ) \ F has an endpoint in S or has an endpoint u ∈ V (F ) such that there exists a vertex v ∈ S and a path from u to v in C i using only edges in F . (This latter case captures the fact that an edge e of C i /F can also be covered by a vertex v ∈ V (F ) that becomes eventually an endpoint of e after contracting the edges in F .)

Let opt(C i , d ) be the output of Min-Contraction(vc) with input (C i , d ), for i ∈ [p] and 0 ≤ d ≤ d. We assume that opt(C i , d ) = ∞ if vc(C i ) ≤ d , and opt(C i , 0) = 0. With this information at hand, we present a simple dynamic programming algorithm to solve the Min-Contraction(vc) problem with input (G, d) within the claimed running time.

Let dp(i, j) be the minimum size of a set F ⊆ E(C 1 ) ∪ . . . ∪ E(C i ) such that vc(G/F ) ≤ vc(G) -j, or ∞ if such set does not exist. Note that, in order to compute dp(i, j), if in an optimal solution the size of a minimum vertex cover drops by q in C i , then dp(i, j) = dp(i -1, j -q) + opt(C i , q). Then dp(i, j) can be computed as follows.

Note that each dp(i, j) can be computed in time O(j). Recall that p is the number of connected components of G. Hence, since p ≤ n, dp(i, j) can be computed for each pair i, j in total time O(n • d 2 ) and the answer is given by dp(p, d).

The bipartite contraction number of a graph G, denoted by bc(G), is the minimum size of a set F ⊆ E(G) such that G/F is bipartite. We will use the following result of Heggernes et al. [START_REF] Heggernes | Obtaining a bipartite graph by contracting few edges[END_REF] as a subroutine in our algorithms. Note that [START_REF] Guillemot | A faster FPT algorithm for Bipartite Contraction[END_REF] presents a faster algorithm. Proposition 14 (Heggernes et al. [START_REF] Heggernes | Obtaining a bipartite graph by contracting few edges[END_REF]). Given a graph G and a positive integer k, deciding whether bc(G) ≤ k is FPT parameterized by k.

We finally have all the ingredients to present our main algorithm. Note that since the contraction of an edge may drop the minimum vertex cover of a graph by at most one, we may assume that k ≥ d, as otherwise the answer is trivially 'No'. We start by checking whether bc(G) ≤ d -1 by using Proposition 14 in time f (d) • n O (1) . We distinguish two cases.

Assume first that bc(G) ≥ d, and let X be a minimum vertex cover of G, which is only used for the analysis. We define a 2-coloring φ of G as follows. For every vertex

Since we may assume that k ≥ d, in this case we can safely answer 'Yes'.

Otherwise, we have that bc(G) ≤ d -1. Let C 1 , . . . , C p be the connected components of G. For every i ∈ [p], we check whether vc(C i ) ≤ d in time 2 O(d) • n O(1) by using an FPT algorithm for Vertex Cover [START_REF] Cygan | Parameterized Algorithms[END_REF]. We distinguish again two cases.