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 → Design blocker problem, edge contraction, graph transversal, parameterized complexity, vertex cover, feedback vertex set, odd cycle transversal Digital Object Identifier 10

For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k, d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where π is the size of a minimum dominating set. We focus on graph parameters 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, which in particular imply that Contraction(π) is co-NP-hard even for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that 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 parameters, instead of graph classes.

The goal here is to perform a small number of modifications in order to decrease (or increase) a given parameter 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 parameter π, 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 parameter π, 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 parameter gives useful information about the graph structure and has been the central question around many graph problems. For instance, if the parameter 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 parameter 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 parameters, such as the chromatic number, the independence number, the matching number, the domination number, and the clique number of a graph [2-4, 10, 16, 21, 22, 31, 32, 35]. 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 parameter.

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 | Blocking dominating sets for H-free graphs via edge contractions[END_REF][START_REF] Galby | Reducing the domination number of graphs via edge contractions[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 | Blocking dominating sets for H-free graphs via edge contractions[END_REF][START_REF] Galby | Reducing the domination number of graphs via edge contractions[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[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[END_REF]Theorem 11] in fact works for any graph parameter 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[END_REF]). Let π be a parameter 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 parameters 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 parameter 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 parameters satisfy the conditions of Proposition 1.

Our results and techniques. We show (Theorem 4) that 1-Contraction(τ ≺ H , 1) is co-NPhard 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 parameter 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. 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, using the FPT algorithm of Heggernes et al. [START_REF] Heggernes | Obtaining a bipartite graph by contracting few edges[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 M F C S 2 0 2 0 64:4

Reducing Graph Transversals via Edge Contractions

show (Lemma 13) that the problem can be solved in FPT time by combining a formulation in MSO 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. Due to space limitations, the proofs of the results marked with "( )" have been moved to the full version of this article, available at https: //arxiv.org/abs/2005.01460.

Preliminaries

We use standard graph-theoretic notation, and we refer the reader to [START_REF] Diestel | Graph Theory[END_REF] for any undefined notation. For completeness, we provide basic definitions about graphs in the full version.

Graph transversals. For a fixed graph containment relation ≺ and a fixed (finite or infinite) collection of graphs H, we define the parameter τ ≺ 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. We also consider

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

64:5

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 I ∈ L in time bounded by f (k) • |I| g (k) .

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) 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 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 ϕ. [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.

Exponential Time Hypothesis and clean 3-Sat. The Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi

Hardness results

We start with some definitions that will be used in the reductions of this section. Let G and 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

H be two graphs, let u, v ∈ V (H),
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 .

a x,C 1 , a x,C 2 , ¯ a x,C 3 , a x b C, 2 b C, 1 b C, 3 AB-copy z s 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.

64:7

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 ϕ.

τ 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. Claim 6 ( ). If τ H (G H ϕ ) = 8n -m, then there is no edge e such that τ H (G H ϕ /e) < τ H (G H ϕ ). 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, namely 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 , 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 of 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.

M F C S 2 0 2 0 64:8

Reducing Graph Transversals via Edge Contractions

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 1 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 lemma. 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 s ∈ 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 by Lemma 3, by observing that

|V (G H ϕ )| = O(n) and that ∆(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, 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, it can be verified that 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.

It can be verified 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. It is easy to see 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 (cf. figure in the full version); 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.

4

The case of Vertex Cover

In this section we focus on the case where the considered property π 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. [26]). 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 is the key insight in 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 |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 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 between such vertices u and v results in a graph H with vc(H ) ≤ vc(H) - • n some some 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 formula whose length depends only on d. Indeed, it consists in finding the minimum size of a set F ⊆ E(C i ) such that vc(C i /F ) ≤ vc(C i ) -d . To express the latter inequality by an MSO formula with length depending on d, we crucially use the hypothesis that vc(C i ) ≤ d. To do this, we first compute := vc(C i ) independently with a standard MSO 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 .) Corollary 16 ( ). The Min-Contraction(vc) problem can be 2-approximated in FPT time parameterized by d.

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 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 2approximated 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.

  the versions of the Contraction(π) problem defined in Section 1 where one of 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(π).

  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, it follows that

Lemma 12 .

 12 Let G be an n-vertex graph, d ≥ 1 an integer, and C a connected component of G such that vc(C) ≥ d + 1. Then there exists a set F ⊆ E(G) with |F | ≤ 2d such that vc(G/F ) ≤ vc(G) -d.

1 .

 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 C of G, it holds that vc(C) ≤ d. Then the Min-Contraction(vc) problem with input (G, d) can be solved in time f (d) • n O(1) for some computable function f . Proof. Let C 1 , . . . , C p be the connected components of G. Since vc(C i ) ≤ d for i ∈ [p], it is easy to observe that tw(G) ≤ d+1. For every two integers i, d with i ∈ [p] and 0 ≤ d ≤ d, we apply Proposition 2 to solve Min-Contraction(vc) with input (C i , d ) in time f (d)

2 0 2 0 64:6 Reducing Graph Transversals via Edge Contractions 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.

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.

M F C S

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

Acknowledgements

We would like to thank the anonymous reviewers 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) and ESIGMA (ANR-17-CE23-0010). 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). and Uéverton S. Souza; licensed under Creative Commons

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 k in C i , then dp(i, j) = dp(i -1, j -k) + opt(C i , k). Then dp(i, j) can be computed as follows.

Note that each dp(i, j) can be computed in time O(j). 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. Proposition 14 (Heggernes et al. [26]). 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. Proof. Let (G, k, d) be the input of Contraction(vc), and let n = |V (G)|. The XP algorithm that we proceed to present is summarized in Algorithm 1. 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 that 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.

If vc(C i ) ≤ d for every i ∈ [p], we apply Lemma 13 and solve the Min-Contraction(vc) 1) for some computable function f . If the optimal solution is larger than k, we answer "No", otherwise we answer "Yes".

Otherwise Let C 1 , . . . , C p be the connected components of G. 1) , as claimed. 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

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 set B := V (L) ∪ V F . Note that |B| ≤ |V (L)| + |V F | ≤ 2(d -1) + 2(2d -1) = O(d) and that G \ B is a subgraph of G \ V (L), hence it is bipartite as well, and we are done.

From the XP algorithm given in Theorem 15 we easily get the following corollary.


Clémence Devailly

Patrick Bouriat

Christophe Dicharry

Frédéric Risso

Thierry Ondarçuhu

Philippe Tordjeman
email: philippe.tordjeman@imft.fr

Open Archive Toulouse Archive Ouverte

Keywords: atomic force microscopy, hydrodynamic force, frequency modulation

We study the effects of hydrodynamic forces in frequency-modulation AFM experiments (FM-AFM) in liquid. We first establish the theoretical equations needed to derive the interaction stiffness k;nr and the damping /3;ni due to the hydrodynamic forces from the frequency shift and the excitation amplitude. We develop specific FM-AFM experiments to measure the variation of k;n1 and f3mt over a large range of distance in water up to 200 µ,m. Comparison between theory and experiments point out that the evolution of k;n1 at short and long distance arises from unsteady hydrodynamic forces on the cantilever. On the other hand, f3mt is smalt at long distance and diverges at short probe-surface distance, as predicted by the classical Reynolds sphere model.

Introduction

Nanoscale imaging and investigation of local properties of materials by atomic force microscopy (AFM) requires a com prehensive understanding of the interaction forces between the probe and the material under study. In general, these interac tion forces may have conservative and dissipative components [l] leading to in-phase and out-of-phase responses compared to the excitation signal, respectively. The dynamic AFM tech niques based on the cantilever oscillation, allow to quantify both contributions. In Amplitude Modulation (AM-AFM), the variations of the amplitude and of the phase, when the probe approaches the material surface, depend on both the conservat ive and dissipative forces [START_REF] Garcia | Amplitude Modulation Atomic Force Microscopy[END_REF]. In Frequency Modulation (FM AFM), in air or vacuum, the in-phase and out-of-phase con tributions are obtained independently by monitoring the res onance frequency and the excitation voltage to maintain the tip oscillation amplitude constant, respectively [START_REF] Morita | Noncontact Atomic Force Microscopy[END_REF]. This con stitutes an advantage of FM-AFM compared to AM-AFM.

Performing AFM in liquids is of a great interest, in particu lar with biological samples which need to remain immersed [START_REF] Dufrene | Imaging modes of atomic force microscopy for application in molecular and cell biology[END_REF] or to study molecules or ion adsorption at solid interfaces [START_REF] Fukuma | Atomic-scale distribution of water molecules at the mica-water interface visualized by three-dimensional scanning force microscopy[END_REF][START_REF] Van Lin | Ion-specific and ph-dependent hydration of mica-electrolyte interfaces[END_REF]. Contact mode and dynamic AFM mode have been intens ively used leading to high-resolution imaging of biological samples and high speed monitoring of biological processes [START_REF] Ando | High-speed atomic force microscopy for nano-visualization of dynamic biomolecular processes[END_REF]. However, dynamic AFM in liquids is a lot more tricky than in air due to the dynamic viscosity of the medium TJ which is, for water, 50 higher than in air [START_REF] Baró | Atomic Force Microscopy in Liquid: Biological Applications[END_REF]. Dissipative hydrodynamic forces become significant and lead to a dramatic decrease of the quality factor of the cantilever (from 100 in air to unit in water) and, consequently of the sensitivity. Moreover, canti lever base motion in dynamic mode becomes significant com pared to the cantilever end amplitude. Additional vibration of the cantilever can also be induced by the liquid cell or the cantilever holder [START_REF] Putman | Tapping mode atomic force microscopy in liquid[END_REF][START_REF] Kiracofe | Quantitative force and dissipation measurements in liquids using piezo-excited atomic force microscopy: a unifying theory[END_REF]. In order to perform FM-AFM measurements in liquids these effects have to be taken into account in the general equations as it was done in AM-AFM [START_REF] Kiracofe | Quantitative force and dissipation measurements in liquids using piezo-excited atomic force microscopy: a unifying theory[END_REF][START_REF] Maali | Precise damping and stiffness extraction in acoustic driven cantilever in liquid[END_REF]. The theoretical equations that allow to calculate the hydrodynamic load of a microcantilever that vibrates in a viscous fluid close to a surface were solved numerically [START_REF] Sader | Frequency response of cantilever beams immersed in viscous fluids with applications to the atomic force microscope[END_REF][START_REF] Green | Small amplitude oscillations of a thin beam immersed in a viscous fluid near a solid surface[END_REF][START_REF] Basak | Hydrodynamic loading of microcantilevers vibrating in viscous fluids[END_REF]. These results established that the in-phase and out-of-phase components of the hydrodynamic force strongly depend on the Reynolds number Re = ρωb 2 /4η, where ρ, ω and b are the fluid density, the oscillation angular frequency and the width of the cantilever, respectively. Moreover, the two components may be of the same order of magnitude due to a sizable increase of the added-mass coefficient when the surface-cantilever distance decreases [START_REF] Basak | Hydrodynamic loading of microcantilevers vibrating in viscous fluids[END_REF]. FM-AFM experiments performed with cantilevers functionalized by a bead or with large radius tips show that the dissipative force is well described by the Reynolds force [START_REF] Maali | Precise damping and stiffness extraction in acoustic driven cantilever in liquid[END_REF][START_REF] Maali | Measurement of the slip length of water flow on graphite surface[END_REF][START_REF] Comtet | Nanoscale capillary freezing of ionic liquids confined between metallic interfaces and the role of electronic screening[END_REF][START_REF] Suzuki | Accurate formula for dissipative interaction in frequency modulation atomic force microscopy[END_REF] (low Re). However, the in-phase part of the force may change as well, even in simple liquids where no elastic part is expected. This change has been several times seen in literature as a phase decrease in AM mode [START_REF] Maali | Precise damping and stiffness extraction in acoustic driven cantilever in liquid[END_REF] or as a frequency shift in FM mode [START_REF] Comtet | Nanoscale capillary freezing of ionic liquids confined between metallic interfaces and the role of electronic screening[END_REF]. In these experiments, the frequency shift varies spatially in a micron range, much larger than the characteristic length of molecular interactions. An example of the frequency shift variation when a 8 µ m glass bead is approached to a silica surface in water is presented figure 1 (see below for details). This long-range variation shows that hydrodynamic forces play a significant role in dynamic AFM.

In order to decorrelate the hydrodynamic force and the interaction force in FM-AFM, the first one should be calculated in function of the tip-sample distance and subtracted to the measured total force. Even if the theoretical equations are well described in the literature, the calculation of the hydrodynamic load requires numerical simulations which are difficult to apply in practice. Furthermore, to our knowledge, direct comparison between experiments and theory has never been achieved because no experiments in FM-AFM were realized at very large distance.

In this paper, we propose an alternative solution for FM-AFM experiments in liquid: we first derive the general relations for the frequency shift and the excitation tension for FM-AFM experiments in liquids. As expected, we show that these two signals are not anymore independently related to the conservative and dissipative forces as in air. Then, we develop specific experiments at very large distance to measure the inphase and the out-of-phase components of the hydrodynamic load in function of the cantilever-surface distance. The results can be reproduced by a pure hydrodynamic model, in a simple geometry, which provides an analytical derivation of the two components, and remains valid even at short distance where the dissipation is modeled by the Reynolds equation.

FM-AFM theory in liquids

We derive the general equations to extract physical quantities FM-AFM in liquids when the resonance quality factor Q is small. We consider that the cantilever is fixed on a base, excited at an amplitude A which has about the same magnitude as the tip deflection q. The model for a cantilever excited by a piezo actuator is described figure 2. The voltage imposed to the piezo is proportional to the displacement A. The total motion of the cantilever tip in the laboratory referential is q+A where, q is the motion of the cantilever end in the base referential. The signal measured in AFM is proportional to q. The equation of motion of the tip in the lab referential q+A in water far from any surface is then:

m 0 ∂ 2 q + A ∂t 2 + β 0 ∂q + A ∂t + k 0 q = 0, (1)
where the subscript ''0'' is for measurement far from any surfaces. m 0 , β 0 and k 0 are respectively an effective mass, effective dissipation and effective stiffness of a cantilever mode in liquid. All these three parameters can be measured by fitting the thermal noise resonance curve, knowing the calibration factor measured in nm/V in contact mode. Here k 0 is not the stiffness of the cantilever but the stiffness of the vibration mode in liquid. It is well known that the cantilever immersed in a liquid can also be excited through the fluid in vibration [START_REF] Kiracofe | Quantitative force and dissipation measurements in liquids using piezo-excited atomic force microscopy: a unifying theory[END_REF]. This effect called ''fluidborne'' excitation is studied in supplementary material. It is shown that one can neglect this effect in our experiments. As we are working in the dynamic mode at a frequency ω, one rewrites the equation with q = q 0 e jωt+ϕ (ω) and A = A ex0 e jωt :

(-

ω 2 ω 2 0 + jω ω 0 Q 0 + 1)q 0 e jϕ(ω) = ( ω 2 ω 2 0 - jω ω 0 Q 0 )A ex0 , (2)
where

ω 0 = √ k 0 /m 0 and Q 0 = k0 β0ω0 .
In presence of an interaction force, A = A ex e jωt . Two additional terms appear in equation [START_REF] Israelachvili | Intermolecular and Surface Forces[END_REF], one in-phase -k int (qe jϕ(ω) + A ex ), and one out-ofphase -jωβ int (qe jϕ(ω) + A ex ) with the tip motion. We assume that over one oscillation, k int and β int remain constant, i.e. that the oscillation amplitude is small compared to the range of interaction.This decomposition is only valid for a force for which the term in phase is proportional to the displacement and the term in out-of-phase is proportional to the velocity. Then, the equation of motion becomes:

(- ω 2 ω 2 0 + jω ω 0 Q 0 + 1)qe jϕ(ω) = ( ω 2 ω 2 0 - jω ω 0 Q 0 )A ex - k int k 0 (qe jϕ(ω) + A ex ) - jωβ int k 0 (qe jϕ(ω) + A ex ). (3)
In FM-AFM mode, the amplitude of the oscillation is kept constant so q = q 0 and the phase is fixed to a value that is fixed to -π/2. Let's define the corresponding frequency ω 0 π/2 so that ϕ 0 (ω 0 π/2 ) = -π/2. By inserting this in equation ( 2), we obtain a system of two equations (real and imaginary parts) with two unknowns ω 0 π/2 and q 0 . After simplifying at first order in 1/Q 0 and in frequency variation, one gets:

ω 0 π/2 = ω 0 (1 -1/2Q 2 0 ), (4)
q 0 = A ex0 Q 0 (1 -1/2Q 2 0 ). (5)
In liquid FM-AFM, we measure the frequency ω at the phase -π/2 and compare it to the reference value ω 0 π/2 in absence of interaction force. We point out that ω 0 π/2 differs from the natural frequency ω 0 and the resonance frequency given by ω 0 √ 1 -1/2Q 2 0 . Then, one can insert equation ( 5) in (3) and it gives:

k int k 0 = ( ω ω 0 ) 2 -1 + 1 1 + Q 2 0 ( Aex0 Aex ) 2 ( 1 -1/2Q 2 0 ) (6)
and

β int β 0 = -1 + ω 0 Q 0 ω Aex Aex0 Q 0 (1 -1/2Q 2 0 ) ( Aex Aex0 ) 2 + Q 2 0 (1 -1/2Q 2 0 ) 2 . ( 7
)
The previous relationships can be approximated by considering that Q 0 > A ex /A ex0 in order to evidence the additional terms in liquids compared to the relationships air:

k int k 0 ≈ 2 ∆ω ω 0 π/2 + 1 Q 2 0 ( ( A ex A ex0 ) 2 -1 ) (8)
and

β int β 0 ≈ A ex A ex0 -1 - A ex A ex0 ∆ω ω 0 π/2 , ( 9
)
where ∆ω = ω -ω 0 π/2 . Equations ( 8) and ( 9) clearly show that k int and β int both depend on the frequency shift and on the excitation amplitude, contrary to experiments in air where elastic and damping forces are separated. For typical values of Q 0 ≃5, with an amplitude ratio A ex /A ex0 ≤ 2, and of relative frequency shift around 1%, the second term in the right hand side of k int equation is predominant. On the other hand, the third term in the right hand side β int equation is small and the dissipation is barely changed compared to air. The coupling between equations ( 8) and ( 9) is based on the assumption that the in-phase and out-of-phase parts of the interaction force are proportional to the displacement and the velocity, respectively. Note that the approximate equation ( 9) is identical to that obtained by Suzuki et al [START_REF] Suzuki | Accurate formula for dissipative interaction in frequency modulation atomic force microscopy[END_REF]. The case of arbitrarily large oscillation amplitudes was treated in the literature [START_REF] Sader | Quantitative force measurements using frequency modulation atomic force microscopy?theoretical foundations[END_REF] but provides expressions which are more difficult to use in practice.

Long range FM-AFM experiments

A specific experiment is developed in order to characterize the effects of hydrodynamic forces at short and long distance. A JPK Nanowizard 3 AFM is employed in FM-AFM mode and thermal noise mode to measure the frequency shift and the dissipation versus the distance to a glass surface D. For thermal noise measurements, the signal from the cantilever deflection is recorded at a high sampling rate (400 kHz ) during 2 s at fixed sample-tip separation. For FM experiments, the PLL device of the signal access module Vortis JPK operates two feedbacks, one on the excitation frequency to maintain the phase constant and one on the excitation amplitude A ex to maintain the tip oscillation constant. The resulting angular frequency shift ∆ω and A ex are monitored in function of D.

The cantilever used is NanoW Arrow TL. Since the first resonance frequency is too low to be efficiently excited by the piezo shaker available, we work with higher translational modes. This permits to have a higher Q factor as well, Q 0 ≃5. The cantilever stiffness k 0 is characterized for a given mode by thermal noise using the deflection sensitivity derived from contact mode experiments on a glass wafer substrate [START_REF] Sader | Quantitative force measurements using frequency modulation atomic force microscopy?theoretical foundations[END_REF].

The probe-substrate distance D is calculated by the difference between the piezo elevation and the cantilever deflection although in most of the range of our measurements, the cantilever deflection is close to zero.

Cantilevers are functionalized with beads of radius R = 8.3µm (Duke Standards, dry, Borosilicate) and R = 20.6µm (Dynoseeds TS, dry, Polystyrene ). There are glued at the end of the cantilever thanks to NOA 68 and insulated under UV lamp for 10 min. All AFM experiments are realized in deionized water. When performing experiments above glass, the cell is carefully rinsed with isopropanol, ethanol then water.

We perform two series of experiments against a glass surface in water at an approaching speed of 1µm s -1 : one at ''short'' distance within the 15 µ m range piezo displacement in order to study the influence of the oscillation amplitude; one at large distance up to 160 µ m, where the cantilever is moved by alternatively by the step motor and the piezo transducer. The reference values of A ex0 and ω π/2 0 are measured at distance larger than 200µm for which no variation of the frequency is observed.

Results and discussion

Figure 1 shows the shift in frequency for different tip oscillations q. We observe a decreasing frequency when approaching the wall as previously observed [START_REF] Suzuki | Accurate formula for dissipative interaction in frequency modulation atomic force microscopy[END_REF]. This is equivalent in AM-AFM mode of a phase decrease [START_REF] Maali | Precise damping and stiffness extraction in acoustic driven cantilever in liquid[END_REF]. We observe a perfect match for different oscillation amplitudes. Even with thermal noise excitation, the amplitude of excitation of which is very low, we measure similar variations in resonance frequency. Thus, decreasing the oscillation amplitude will not decrease the frequency shift. These results suggest that hydrodynamic forces are responsible for this behavior [START_REF] Green | Small amplitude oscillations of a thin beam immersed in a viscous fluid near a solid surface[END_REF]. In order to verify this assumption, we performed AFM experiments in liquid at large distance, far above the characteristic lengths of molecular and electrostatic interactions. We performed experiments up to 200 µm for the biggest bead we were able to glue that provide a nice resonance peak with a radius R = 20.6µm and a width b = 100µm in order to maximize the hydrodynamic forces.

Thanks to equation ( 6) and ( 7), we plot k int /k 0 and β int /β 0 respectively in figure 3 and4. Interestingly, the hydrodynamic forces induce a variation of the in-phase parameter over a range of distance of order of 100 µm. In comparison, the variation of the out-of-phase component is confined within 10 µm and is close to zero beyond. The decrease of k int was also observed with R = 8.3µm bead as shown at short distance in figure 1. Note that dynamic AFM in non-elastic (Newtonian) liquid generates at large distance hydrodynamic forces for which the in-phase component can be on a same order of magnitude that the one in outof-phase. Whereas the damping increase of an oscillating sphere near a wall has already been well characterized both experimentally and numerically in the lubrication approximation R > > D, the decrease of k int that accounts for the added-mass increase as D decreases [START_REF] Basak | Hydrodynamic loading of microcantilevers vibrating in viscous fluids[END_REF] has attracted less attention.

Recently, the hydrodynamic force exerted on an oscillating bead near a wall was analytically calculated for various limit cases [START_REF] Fouxon | Fundamental solution of unsteady stokes equations and force on an oscillating sphere near a wall[END_REF]. Three main parameters are R the bead radius, H = R + D the distance between the bead center and the wall, and δ = √ ν/ω, the size of the boundary layer. In the experimental conditions of figure 3 and4, we obtain δ ≈ 4µm. For H > > R and H > > δ corresponding to our experiments for which the flow is unsteady, the normalized perpendicular force exerted by the fluid on the bead F N is given by: [START_REF] Kiracofe | Quantitative force and dissipation measurements in liquids using piezo-excited atomic force microscopy: a unifying theory[END_REF] where Ω = R 2 ω/ν is the Reynolds number for a sphere and V ⊥ is the dimensionless perpendicular velocity of the bead. V ⊥ = 1 if the movement is purely perpendicular to the wall. In this equation, the force is normalized by ρνRV where V is the bead velocity. Rewriting this force in term of k int and β int , we obtain:

F N = - 3πR 3 4 H 3 ( 5 + 3 √ 2/Ω + √ 2Ω ) V ⊥ -j 3πR 3 4 H 3 ( 3/Ω + 3 √ 2/Ω -Ω/3 - √ 2Ω ) V ⊥
k int = ρνRω 3πR 3 4 H 3 (3/Ω + 3 √ 2/Ω - √ 2Ω -Ω/3), (11)
and

β int = ρνR 3πR 3 4 H 3 (5 + 3 √ 2/Ω + √ 2Ω). ( 12
)
This model is compared with the experimental results in figure 3 and4. The stiffness and the resonant frequency characteristic of the second mode that is used in these FM-AFM experiments are measured by thermal noise with optical lever correction: k 0 = 4.8 N m -1 and ω 0 = 77.9 × 10 3 rad s -1 . Due to the respective dimensions of the probe (R = 20.6 µm) and of the cantilever (100 × 500 µm 2 ), the hydrodynamic forces arise mainly from the cantilever vibration at large distance. In order to compare the results with the model, the cantilever is assimilated to a sphere with an equivalent radius R eq and the origin of its displacement is defined by D =-2 R. Indeed, at D = 0, the cantilever is at a distance of 2 R due to the presence of bead probe. The experimental results are fitted by the model with R eq as the only free parameter. We found a very good agreement between model and experiments for R eq = 59 µm for the curves of k int /k 0 . We check that 2R eq is comprised between the length and the width of the cantilever. The inset of figure 3 shows that the experimental data follow the powerlaw in (D + R eq ) -3 in the whole range of the experimental distance as predicted by equation [START_REF] Maali | Precise damping and stiffness extraction in acoustic driven cantilever in liquid[END_REF]. On the other hand, the bead model points out clearly that β int /β 0 is small, within the experimental noise, in agreement with the experiments at large distance. However, it cannot predict the divergence of the dissipation when the bead attached at the extremity of the cantilever approaches the substrate. In this case, the dissipation is simply given by the Reynolds formulae β int = 6πηR 2 /D calculated in lubrication assumptions (steady flow) for the probe of radius R and D ≲ δ. The inset of figure 4 shows the very good agreement between the Reynolds model and the experimental data, in accordance with the literature [START_REF] Maali | Precise damping and stiffness extraction in acoustic driven cantilever in liquid[END_REF][START_REF] Maali | Measurement of the slip length of water flow on graphite surface[END_REF][START_REF] Comtet | Nanoscale capillary freezing of ionic liquids confined between metallic interfaces and the role of electronic screening[END_REF]. The situation is different for k int since the Reynolds force associated with the probe has no in-phase component. As seen in figure 3 no deviation from the oscillating bead model for the cantilever is observed at short distance.

Hence, the hydrodynamic forces arise from the oscillating cantilever and from the bead probe at its extremity. The force on cantilever is effective at very large distance up to 200 µm and is mainly observed on the in-phase k int /k 0 component. The Reynolds force on the bead probe occurs at short distance (D ≲ δ) and is only observed on the out-of-phase β int /β 0 component. In this range of distance, the dissipation due to the force on the cantilever is negligible. We can compare the experimental data at D = 10µm to those obtained by numerical simulations. We measure an in-phase and out-ofphase components of the hydrodynamic load of 0.8 nN and 0.6 nN, respectively. Estimation using published numerical simulations [START_REF] Green | Small amplitude oscillations of a thin beam immersed in a viscous fluid near a solid surface[END_REF] leads to hydrodynamic forces of about 1 nN, both for the conservative and dissipative components, in agreement with the experiments and the analytical model. Equations ( 11) and ( 12) can therefore be used to deduce the equivalent radius of the cantilever by fitting data at large distance. The long range hydrodynamic interaction due to the cantilever can then be subtracted from the total signal to infer molecular interactions between the probe and the surface at short distance.

Conclusion

FM-AFM experiments in liquid require to take into account the hydrodynamic forces that influence measurements of the frequency shift and of the dissipation. Theoretically, we have shown that the frequency shift and the excitation amplitude are dependent on the in-phase component k int and out-of-phase component β int of the interaction forces including hydrodynamic forces. We have established the relationships which can be used to extract k int and β int from the experimental raw data. Specific FM-AFM experiments have been developed in conditions where the cantilever and the bead probe are submitted to hydrodynamic forces. The results were analyzed in the frame of a hydrodynamic model of one sphere oscillating near a wall. The experiments point out that the evolution of k int with the distance arise from the unsteady hydrodynamic forces on the cantilever over a large range of displacement. On the other hand, the evolution of β int is observed at short distance and is due to the Reynolds force on the bead probe. Finally, we investigate the effects of the fluid-borne interactions (in the supplementary material) and showed that these forces do not influence the measurements in FM-AFM. This work allows us to analyze easily FM-AFM experiments in liquid in order to extract the interaction force between tip and sample. Indeed, it shows that the dissipated force between a probe and a surface can be analyzed using the Reynolds model with confidence at short distance. Moreover, the measurement of molecular interaction force between the probe and the surface based on k int determination requires to subtract the effects of hydrodynamic forces on the cantilever. This can be achieved using equation [START_REF] Maali | Precise damping and stiffness extraction in acoustic driven cantilever in liquid[END_REF]. This study may therefore broaden the use of FM-AFM in liquid.

Figure 1 .

 1 Figure 1.Resonance frequency shift of the 3rd mode of a cantilever with an 8 µ m bead versus the distance D from a glass surface in pure water. Lines: measurements for three excitation amplitudes q; symbols: resonance frequency shift in the same configuration measured by fitting the thermal noise resonance peak.

Figure 2 .

 2 Figure 2.Sketch of the experiment. The cantilever functionalized with a bead of radius R is oscillated at a mean distance D from a solid surface. The position of the base of the cantilever is noted Aex(t) and its extremity Aex(t)+q(t) where q(t) is the cantilever deflection.

Figure 3 .

 3 Figure 3. Evolution of k int /k 0 vs the distance D measured in long range FM-AFM experiments (red symbols). Comparison with the model of an oscillating bead in a liquid close to a wall (black line). Inset: verification of the power law in -3 in agreement with equation (11).

Figure 4 .

 4 Figure 4. Evolution of β int /β 0 vs the distance D measured in long range FM-AFM experiments (blue symbols). Comparison with the model of an oscillating bead in a liquid close to a wall (equation (12), black line) and with the Reynolds model (blue line). Inset: comparison of experimental data of β int /β 0 and Reynolds model at short distance.

Acknowledgment

The authors thank the Institut Carnot Isifor which funded the RIC project and allowed us to realize this study.

ORCID iD

Philippe Tordjeman  https://orcid.org/0000-0002-6470-

Supplementary material

See supplementary material (link) to have the details calculations for FM-AFM formulae including fluid-borne forces and their effects in data of the present paper.


Jean-Jacques Vasseur

Sabine Müller

Michael Smietana
email: michael.smietana@umontpellier.fr

Selective chemical modification of DNA with boronic acids by on-column CuAAc reactions Mégane Debiais a

Keywords: CuAAc, boronic acid, oligonucleotide, bioconjugation, DNA, RNA

The use of the Cu(I)-catalyzed azide-alkyne cycloaddition (CuAAC) reaction for the preparation of oligonucleotide conjugates is by now familiar. However, the selective introduction of boronic acids into DNA and RNA sequences by CuAAC reactions has long been considered impossible due to the incompatibility of the boronic acid moiety with copper salts. Here we describe two new methods for the selective on-column functionalization of oligonucleotides with boronic acids via two different CuAAC reactions. The first one allows the introduction of a phenylboronic acid at the 5'extremity of oligonucleotides, while the selective intrastrand positioning of the modification can be achieved with the second one. Both methods were applied to the DNA and RNA series (up to a 20mer) with good isolated yields and excellent purities. These results illustrate the potential of the reported methods for selective incorporation of boronic acids into oligonucleotides.

The widespread properties of boronic acid-containing organic compounds has resulted in their use in a large number of applications in various fields, including organic chemistry,1 medicinal chemistry,2 asymmetric synthesis,3 catalysis4 and materials.5 Due to their trigonal planar sp2-hybridized boron atom bearing two hydroxyl groups and an empty p-orbital, boronic acids can form covalent and reversible complexes with electron-donating centres such as oxygen and nitrogen nucleophiles. In aqueous media, when the pH is higher than the pKa, this Lewis acid-base reaction results in a rehybridization of the boron atom from sp2 to sp3 leading to an anionic tetravalent borate species. [START_REF] Hall | Boronic Acids[END_REF] The reversible reaction with 1,2 cis-diols leading to cyclic boronate esters has notably been used to create self-organizing systems, sensors and pH responsive materials.7 Given the versatile features of boronic acids, it is therefore not surprising that the incorporation of this moiety into biomolecules is currently attracting a lot of attention to develop new bioconjugates endowing new properties. While the site-selective modification of peptides and proteins with boronic acids has made huge strides in recent years,8 their incorporation into DNA remains challenging. One of the reasons is that the cornerstone Cu catalyzed azide-alkyne cycloaddition (CuAAC) reaction is difficult to apply, given the lack of stability of boronic acids in the presence of copper salts.9

Modified oligonucleotides (ONs) are usually obtained either by automated chemical synthesis10 or by enzymatic chain assembly with appropriately modified phosphoramidite building blocks or modified nucleoside triphosphates, respectively.11 Both approaches have the disadvantage of requiring a multi-step synthesis of the modified monomers, which subsequently have to tolerate the reagents and conditions used for the elongation. An attractive alternative is the site-specific postsynthetic conjugation of a desired functionality to a defined reactive group incorporated into the ON.12 This latter strategy is highly modular, easier to handle, and usually gives better yields.13

Considering the broad variety of applications that can be achieved with borono-based DNA in particular in the field of aptamers,14 the two strategies described above have been applied to introduce a boronic acid moiety into ONs. In the laboratory, we have extensively studied the phosphoramidite approach that led us to develop enzyme-free DNA-and RNA-templated ligation systems with 5'-boronic acid modified oligonucleotides.15 We have also demonstrated the ability of borono-based ONs to inhibit nucleases including RNase H.16 Enzymatic polymerization,17 amide bond formation18 and strain-promoted alkyne-azide cycloaddition (SPAAC)19 have been evaluated as well by other research groups, all of them requiring the prior multi-step synthesis of modified nucleosides or solid-phase synthesis of boronic acid reactive species. In this context, the development of a rapid, efficient Figure 1 Schematic illustration of on-column CuAAC conjugation of boronic acids. Blue spheres represent the CPG solid-support; Reagents and conditions: Method 1: i. CH3P(OPh)3I (500 equiv.), DMF, rt, 15 min; ii. TMGA (300 equiv.), ACN, 60°C, 1,5 h.; CuAAC: 1 (8 equiv.), CuSO4•5H2O (1 equiv.), sodium ascorbate (5 equiv), THPTA (3 equiv.), ACN/H2O (4/6), 60 °C, 1 h. Method 2: CuAAC: 2 (20 equiv.), CuSO4•5H2O (1 equiv.), sodium ascorbate (5 equiv.), THPTA (3 equiv.), 2 (20 equiv.), dioxane/ACN/H2O (3/1/6), MW 60 °C, 2 h. Cleavage and deprotection: NH4OH, 55 °C, 5 h for DNA synthesis; DBU 1 M, rt, 3 min, NH4OH, 37 °C, 3 h for RNA synthesis. and modular approach for postsynthetic introduction of boronic acid functions into DNA is highly desirable. Herein we report the on column introduction of phenylboronic acid moieties either at the 5'-extremity or at an internal position of the ONs via two different CuAAc reactions (Figure 1): (a) Method 1 involves reaction of a 5'-azido modified ON with 4-ethynylphenylboronic acid pinacol ester 1, and (b) Method 2 implicates an incorporated 2' O propargyluridine and 4-(azidomethyl)phenylboronic acid MIDA ester 2.

The insertion of Cu(I) between carbon-boron bonds is a well-documented side reaction that can hamper the efficacy of the CuAAC reaction.20 This observation has led many research groups to consider that the selective labeling of DNA with boronic acid was incompatible with the CuAAC reaction,18b, 19b although various groups including ours have shown that appropriately protected boronic acids can be successfully used with CuAAC reactions in the context of small molecule synthesis.9, 21 Inspired by these results, we started our study by evaluating the possibility of performing the oncolumn attachment of commercially available 4-ethynylphenylboronic acid pinacol ester 1 at the 5'extremity of DNA sequences (Figure 1, Method 1). 5' azido-modified sequences were obtained following the two-steps protocol developed by Kool and co workers.22 All the oligonucleotides were prepared using standard phosphoramidite chemistry on a DNA synthesizer with removal of the terminal DMT group. The 5'-terminal hydroxyl groups were then converted to the corresponding 5' iodide via the on-column reaction with (PhO)3PCH3I in DMF for 15 min at r.t.. The conversion of 5'iodides to 5'-azides proceeded to completion by on-column reaction with a solution of tetramethylguanidinium azide (TMGA) in acetonitrile for 90 min at 60 °C. Excess of TMGA was removed by washing the column with a sodium bisulphite solution. In each step, a syringe with the reagent was fitted to one end of the DNA synthesis column containing the CPG-bound ODN and an empty syringe was fitted to the other end. 1 mL of reagent was passed through the column from one syringe to the other for the appropriate time before putting the column on a shaker at the appropriate temperature.

The CuAAC reaction conditions were optimized for the tetranucleotide (5'-N3dTCCG-3') until full conversion was observed by HPLC analysis with no noticeable formation of by-products after cleavage from the support. A control experiment was run using 5'-N3dTCCG-3' and 8 equiv. of 4ethynylphenylboronic acid, the deprotected analogue of 1, CuSO4•5H2O (1 equiv.), sodium ascorbate (5 equiv.) and tris(benzyltriazolylmethyl)amine (THPTA, 3 equiv.) for 60 min at 60 °C in a ACN/H2O mixture. The resulting CPG support was then washed with a saturated solution of EDTA and ODN1 was cleaved off the support by addition of a concentrated aqueous solution of ammonia. MALDI-TOF MS analysis confirmed that the boronic acid was fully oxidized to the corresponding phenol moiety under these conditions (Table 1, entry 1). However, the use of 4 ethynylphenylboronic acid pinacol ester 1 under otherwise identical conditions led to the postsynthetic modification of ODN2 by a phenylboronic acid moiety with 93 % conversion without noticeable degradation of the boronic acid functionality (Table 1, entry 2). RP HPLC spectra of the crude product after three steps and deprotection/cleavage from the solid support showed very little amount of the starting material, indicating complete conversion in all the reactions. This also confirmed the removal of the pinacol protecting group by concentrated aqueous ammonia.15c

Figure 2 HPLC and MALDI-TOF spectra of the A) crude ODN1 and B) pure ODN2.

Following RP-HPLC purification, the modified ODN2 was isolated in 34% yield and an excellent purity as shown by RP-HPLC analysis. The RP-HPLC spectrum of ODN1 and ODN2 showed very close retention times (< 1.0 min span). In MALDI-TOF analysis, a single peak at m/z 1291.82 Da (calcd. m/z = 1291.94 Da) was observed for the oxidized sequence ODN1, whereas peaks at m/z = 1318.91 and 1475.12 Da corresponding to [M-H]-(calcd. m/z = 1318.75 Da) and [M-+citrate-2H2O-H]-(calcd. m/z = 1475,85 Da), were observed for ODN2 in accordance with fragmentations and adducts that typically appears with boronic acid-modified oligonucleotides (Figure 2).15c, 17b, 18b

Encouraged by these results, we evaluated the method on sequences varying in length and nature of the residue at the 5' end. As the length of the sequences increased, we observed a decrease in the conversions and isolated yields as exemplified with the 17-mer ODN5, which was obtained with 55 % conversion and 8% isolated yield after purification (Table 1, entry 5). The seemingly low isolated yields are actually not that low considering that they are calculated on 1 µmol scale after automated synthesis (16 cycles), four reaction steps, deprotection and purification by RP-HPLC. In fact, the isolated yields are similar to previously reported syntheses using 5'-azido ONs23 and far superior to the minimum guaranteed yields provided by major market suppliers for pure custom oligonucleotides (usually less than 50 nmol are guaranteed for modified ONs 10-19mer on a 1 µmol scale purified by RP HPLC). Replacement of 5'-thymidine by 5'-cytidine resulted in similarly good conversions but slightly lower isolated yields (Table 1, entries 6-8). Finally, the method was successfully applied to a hexameric RNA sequence leading to the 5'-boronic acid modified ORN1 with 90 % conversion and 20% isolated yield (Table 1, entry 9).

The successful conjugation of boronic acids at the 5'-extremity of ONs prompted us to evaluate their incorporation inside oligonucleotide strands (Figure 1, Method 2). Commercially available 2'-Opropargyluridine phosphoramidite was used to prepare CPG-bound oligonucleotides (DMT-off). The partner 4 (azidomethyl)phenylboronic acid MIDA ester 2, was synthesized in two steps starting from commercially available 4 (hydroxymethyl)phenylboronic acid 3. The boronic acid moiety was first protected as a N-methyliminodiacetic acid (MIDA) boronate ester under Dean-Stark conditions affording the corresponding derivative 4 in 98% yield. MIDA was selected for its stability and facile deprotection under basic conditions.24 The azidation of 4 was obtained in one step using diphenyl phosphoryl azide (DPPA) and 1,8-diazabicyclo [5.4.0]undec-7-ene (DBU) in DMF to afford the desired azide 2 in 89% yield (Scheme 1).

Scheme 1 Synthesis of azide 2

The Cu(I)-catalysed azide-alkyne cycloaddition reaction was then carried out on column by mixing the representative ONs with azide 2 (20 equiv.) in a 2:8 ACN/dioxane mixture in the presence of a freshly prepared aqueous solution of CuSO4•5H2O (1 equiv.), sodium ascorbate (5 equiv.) and THPTA (3 equiv.), and by heating the mixture for 120 min at 60 °C under microwave irradiation (Figure 1, Method 2). The resulting CPG supports were then washed with a saturated solution of EDTA, treated with aqueous ammonia and purified by preparative RP-HPLC, leading to the corresponding conjugated oligonucleotides. The boronic acid moiety could be positioned successfully either at the extremity of a sequence or inside the DNA strand although in the latter case we observed a decrease of the overall isolated yield, probably due to steric hindrance (Table 1, entries 10 and 11). The method is equally compatible with RNA sequences although the isolated yields are lower than in the DNA series (Table 1, entry 12). To further demonstrate the applicability of borono-modified sequences in the field of aptamers, the 20-mer ODN11 containing the core sequence of the tobramycin aptamer, used notably for the detection of this aminoglycoside antibiotic in milk and human serum samples,25 was obtained with 48 % conversion and 7% isolated yield (Table 1, entry 13).

Finally, to further prove the presence of the boronic acid moiety in the modified sequences, we performed a colorimetric displacement assay with Alizarin red S (ARS). Indeed, the combination of this dye with boronic acids is well known for the detection of various analytes.26 The binding of the boronic acid to ARS induces a significant colour change from purple to yellow within a few seconds, which can be readily visualised by the naked-eye (Figure 3). The addition of 100 equiv. of fructose results, in less than 1 min, in the displacement of the ARS dye and the formation of a DNA-fructose complex, which ultimately restores the purple colour.

In conclusion, we have described the first successful use of CuAAC reactions as a convenient strategy for postsynthetic on column conjugation of oligonucleotides with boronic acids. The phenylboronic acid moiety could be selectively positioned either at the 5'-extremity or at an internal position of ONs by the use of the appropriately protected 4-ethynyl-or 4-(azidomethyl)-phenylboronic acid. The functionalized oligonucleotide products were obtained after preparative HPLC in good isolated yields and excellent purities in both the DNA and the RNA series. The demonstrated practicability of this new procedure for postsynthetic modification of oligonucleotides with boronic acids increases significantly the repertoire of possible DNA and RNA conjugation chemistries and will undoubtedly find use for the design of functional ONs.

The experimental section has no title; please leave this line here.

Commercially available reagents were used as received. Pyridine was distilled on calcium hybrid. The reaction mixtures were monitored by TLC using silica gel plates (Merck) with fluorescent indicator (λ = 254 nm). The purification of the products was performed by flash column chromatography using silica gel 60 (43-63 μm) from Merck-Millipore. NMR analyses were made on a Bruker spectrometer 400 MHz at 20 °C. Chemical shifts are reported in parts per million (ppm) and are referenced to the residual solvent resonance as the internal standard (CD3CN δ = 1.94 for 1H NMR and CD3CN δ = 1.32 for 13C NMR). Data are reported as follows: chemical shift, multiplicity (standard abbreviations), coupling constant (Hz), and integration. HRMS were recorded on a Micromass Q-TOF spectrometer with an electrospray ionisation (ESI) in negative or positive mode. All the oligonucleotide syntheses were conducted on an ABI 394 DNA/RNA synthesizer by classical phosphoramidite chemistry with commercial phosphoramidites and CPG (Control Pore Glass) solid support using standard conditions.

Crude sequences were purified by semi-preparative HPLC Dionex 600 in reverse phase with a gradient of buffer B (TEAAc 0.05M + 80% ACN) in buffer A (TEAAc 0.05M + 1% ACN) at 30 °C at a flow rate of 4 mL/min. Purified DNA samples were analysed by analytic HPLC with a gradient of buffer B (TEAAc 0.05M + 80% ACN) in buffer A (TEAAc 0.05M + 1% ACN) at a flow of 1 mL/min. MALDI-TOF mass spectra were recorded on an Axima assurance spectrometer (Shimadzu Biotech) using 1 µL of purified DNA sample mixed with 5 µL of a 6-aza-2-thiothimine (ATT) saturated matrix and ammonium citrate (0.1 M) as co-matrix. Samples were then spotted on a stainless steel plate and air dried before analysis. Reactions under micro-wave irradiation were realized on an monowave 400 (Anton Paar) in G10 reaction flask with a power of 850 W and a speed of 400t/min.

On-column Iodination

Upon completion of the syntheses of the desired sequences (DMT-off), the columns were removed from the synthesizer and 1 mL syringes were fitted to each end. 1 mL of a solution of (PhO)3PCH3I (0.5 M in anhydrous DMF, 500 µmol) was then passed through the column at r.t. for 15 min. The column was then washed with 10 mL of DCM, 10 mL of ACN and 10 mL of DCM, and eventually dried under argon.

On column Azidation

The column containing the 5'-iodo oligodeoxyribonucleotide bound to a CPG resin was fitted in each end by 1 mL syringes. 1 mL of a solution of TMGA (0.3 M in anhydrous ACN, 300 µmol) was then passed through the column 10 to 15 times before placing the column in an oven at 60 °C for 60 min.

The column was then washed with 10 mL of ACN, 5 mL of sodium bisulphite, 5 mL of DCM and 5 mL of ACN and dried under argon.

On-column CuAAc reactions

Incorporation of alkyne-boronic acid 1

All solutions were freshly prepared and degassed with argon bubbling. The column containing the 5'azido oligodeoxyribonucleotide bound to a CPG resin was fitted in each end by 1 syringes. 1 mL of a solution containing boronic acid 1 (80 µL, 0.1 M in ACN, 8 µmol), THPTA (30 µL, 0.1 M in water, 3 µmol), copper sulphate (25 µL, 0.04 M in water, 1 µmol) and sodium ascorbate (50 µL, 0.1 M in water, 5µmol) was then passed through the column 10 to 15 times before putting the column in an shaker at 60 °C for 60 min. The column was then washed with 5 mL of aqueous EDTA disodium salt, 5 mL of ACN and dried under argon.

Incorporation of azide-boronic acid 2

All solutions were freshly prepared and degassed with argon bubbling. Protected oligodeoxyribonucleotide attached to CPG beads was placed into a 10 mL reaction flask (G10). THPTA (30 µL, 0.1 M in water, 3 µmol) and boronic acid 2 (200 µL, 0.1 M in a 8:2 dioxane/ACN mixture, 20 µmol), copper sulphate (25 µL, 0.04 M in water, 1 µmol) and sodium ascorbate (50 µL, 0.1 M in water, 5 µmol) were added and the resulting mixture was then stirred for 120 min at 60 °C under microwave irradiation (power: 850W, speed: 400t/min).28 The beads were then successively washed with 5 mL of aqueous EDTA disodium salt and 5 mL of ACN, and eventually dried under argon. ODN11 was obtained using 100 µmol of boronic acid 2 after 180 min under microwave irradiation at 60 °C.

Deprotection, analysis and purification of oligonucleotides Deprotection and cleavage of the DNA sequences from the solid support was achieved upon mixing with concentrated NH4OH at 55 °C for 5 h.

Deprotection and cleavage of the RNA sequences from the solid support, on the other hand, was possible after passing a solution of DBU 1 M in ACN through the column for 3 min before treating the beads with concentrated NH4OH at 37 °C for 3 h.

Funding Information

The Agence Nationale de la Recherche and the Deutsche Forschungsgemeinschaft are gratefully acknowledged for financial support (ANR PCRI "TEMPLAR"-16-CE92-0010-01; DFG MU1396/11).

Supporting Information YES (this text will be updated with links prior to publication)

Table 1

 1 On-column CuAAC reaction with DNA and RNA sequences

	Entry Name Sequence 5'→ 3'a	Conversion (%)b	Yield (nmol/ (%))c
	1	ODN1 PhOH-d(TCCG) -	-
	2	ODN2 PhBn-d(TCCG) 93	348,6 (34)
	3	ODN3 PhBn-d(TCTCCG)	95	145,8 (15)
	4	ODN4 PhBn-d(TCTCTCCG)	93	148,7 (15)
	5	ODN5 PhBn d(TACAACGACTCTCTCCG) 55	77,1 (8)
	6	ODN6 PhBn-d(CCG) 95	98,9 (10)
	7	ODN7 PhBn-d(CTCCG) 95	141,5 (14)