Raul Lopes
email: raul.lopes@lia.ufc.br

Ignasi Sau
email: ignasi.sau@lirmm.fr

A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps

Keywords: 2012 ACM Subject Classification Theory of computation → Fixed parameter tractability; Theory of computation Parameterized complexity, directed disjoint paths, congestion, dual parameterization, kernelization, directed tree-width

In the Directed Disjoint Paths problem, we are given a digraph D and a set of requests {(s1, t1), . . . , (s k , t k )}, and the task is to find a collection of pairwise vertex-disjoint paths {P1, . . . , P k } such that each Pi is a path from si to ti in D. This problem is NP-complete for fixed k = 2 and W[1]-hard with parameter k in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Good news are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified large part of it. Namely, in the Disjoint Enough Directed Paths problem, given an n-vertex digraph D, a set of k requests, and non-negative integers d and s, the task is to find a collection of paths connecting the requests such that at least d vertices of D occur in at most s paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of D. Among other results, we show that the problem is W[1]-hard in DAGs with parameter d and, on the positive side, we give an algorithm in time O(n d+2 • k d•s ) and a kernel of size d • 2 k-s • k s + 2k in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number k of terminals and d, where d = n -c and c is the size of the solution.

Introduction

In the Disjoint Paths problem, we are given a graph G and a set of pairs of vertices {(s 1 , t 1 ), . . . , (s k , t k )}, the requests, and the task is to find a collection of pairwise vertexdisjoint paths {P 1 , . . . , P k } such that each P i is a path from s i to t i in G. Since this problem is NP-complete in the directed and undirected cases, even if the input graph is planar [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF][START_REF] Lynch | The equivalence of theorem proving and the interconnection problem[END_REF], algorithmic approaches usually involve approximations, parameterizations, and relaxations.

In this article, we focus on the latter two approaches and the directed case.

Previous work. For the undirected case, Robertson and Seymour [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF] showed, in their seminal work on graph minors, that Disjoint Paths can be solved in time f (k) • n O (1) for some computable function f , where n is the number of vertices of G; that is, the problem is fixed-parameter tractable (FPT) when parameterized by the number of requests.

The directed case, henceforth referred to as the Directed Disjoint Paths (DDP) problem, turns out to be significantly harder: Fortune et al. [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF] showed that the problem is NP-complete even for fixed k = 2. In order to obtain positive results, a common approach has been to consider restricted input digraphs. For instance, it is also shown in [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF] that DDP is solvable in time n O(k) if the input digraph is acyclic. In other words, DDP is XP in DAGs with parameter k. For some time the question of whether this could be improved to an FPT algorithm remained open, but a negative answer was given by Slivkins [START_REF] Slivkins | Parameterized tractability of edge-disjoint paths on directed acyclic graphs[END_REF]: DDP is W [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hard in DAGs with parameter k. Johnson et al. introduced in [START_REF] Johnson | Directed tree-width[END_REF] the notion of directed tree-width, as a measure of the distance of a digraph to being a DAG, and provided generic conditions that, if satisfied by a given problem, yield an XP algorithm on graphs of bounded directed tree-width. In particular, they gave an n O(k+w) algorithm for DDP on digraphs with directed tree-width at most w. Another restriction considered in the literature is to ask for the underlying graph of the input digraph to be planar. Under this restriction, Schrijver [START_REF] Schrijver | Finding k disjoint paths in a directed planar graph[END_REF] provided an XP algorithm for DDP with parameter k, which was improved a long time afterwards to an FPT algorithm by Cygan et al. [START_REF] Cygan | The Planar Directed k-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable[END_REF].

A natural relaxation for the Directed Disjoint Paths problem is to allow for vertex and/or edge congestion. Namely, in the Directed Disjoint Paths with Congestion problem (DDPC for short, or DDPC-c if we want to specify the value of the congestion), the task is to find a collection of paths satisfying the k requests such that no vertex in the graph occurs in more than c paths of the collection. Amiri et al. [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF] considered the tractability of this problem when restricted to DAGs. Namely, they showed that DDPC-c in DAGs is W [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hard for every fixed c ≥ 1 but admits an XP algorithm with parameter d, where d = k -c. By a simple local reduction to the general version given in [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF] and the framework given by Johnson et al. [START_REF] Johnson | Directed tree-width[END_REF], it follows that DDPC-c also admits an XP algorithm with parameters k and w for every fixed 1 ≤ c ≤ n -1 in digraphs with directed tree-width at most w, and the same result also holds when we allow for congestion on the edges.

Motivated by Thomassen's proof [START_REF] Thomassen | Highly connected non-2-linked digraphs[END_REF] that DDP remains NP-complete for k = 2 when restricted to β-strongly connected digraphs, for any integer β ≥ 1, Edwards et al. [START_REF] Edwards | Half-integral linkages in highly connected directed graphs[END_REF] recently considered the DDPC-2 problem (this version of the problem is usually called half-integral in the literature) and proved, among other results, that it can be solved in time n f (k) when restricted to (36k 3 + 2k)-strongly connected digraphs. Kawarabayashi et al. [START_REF] Kawarabayashi | An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem[END_REF] considered the following asymmetric version of the DDPC-4 problem: the task is to either find a set of paths satisfying the requests with congestion at most four, or to conclude that no set of pairwise vertex-disjoint paths satisfying the requests exists. In other words, we ask for a solution for DDPC-4 or a certificate that there is no solution for DDP. They proved that this problem admits an XP algorithm with parameter k in general digraphs, and claimed -without a proof-that Slivkins' reduction [START_REF] Slivkins | Parameterized tractability of edge-disjoint paths on directed acyclic graphs[END_REF] can be modified to show that it is W [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hard in DAGs. In their celebrated proof of the Directed Grid Theorem, Kawarabayashi and Kreutzer [START_REF] Kawarabayashi | The Directed Grid Theorem[END_REF] claimed that an XP algorithm can be also obtained for the asymmetric version with congestion at most three. To the best of our knowledge, the existence of an XP algorithm in general digraphs for the DDPC-2 problem, or even for its asymmetric version, remains open.

Summarizing, the existing positive results in the literature for parameterizations and/or relaxations of the Directed Disjoint Paths problem in general digraphs are quite scarce.

Our approach, results, and techniques. In this article, we propose another congestion metric for DDP. In contrast to the usual relaxations discussed above, which focus on a local congestion metric that applies to every vertex, our approach considers, on top of local congestion, a global congestion metric: we want to keep control of how many vertices (a global metric) appear in "too many" paths (a local metric) of the solution. That is, we want the paths to be such that "most" vertices of the graph do not occur in too many paths, while allowing for any congestion in the remaining vertices. In the particular case where we do not allow for local congestion, we want the paths to be pairwise vertex-disjoint not in the whole graph, but in a large enough set of vertices; this is why we call such paths "disjoint enough".

Formally, in the Disjoint Enough Directed Paths (DEDP) problem, we are given a set of requests {(s 1 , t 1 ), . . . , (s k , t k )} in a digraph D and two non-negative integers c and s, and the task is to find a collection of paths {P 1 , . . . , P k } such that each P i is a path from s i to t i in D and at most c vertices of D occur in more than s paths of the collection. If s = 1, for instance, we ask for the paths to be pairwise vertex-disjoint in at least n -c vertices of the graph, and allow for at most c vertices occurring in two or more paths. Choosing c = 0 and s = 1, DEDP is exactly the DDP problem and, choosing s = 0, DEDP is exactly the Steiner Network problem (see [START_REF] Emil | The complexity landscape of fixed-parameter directed Steiner network problems[END_REF] for its definition).

By a simple reduction from the Directed Disjoint Paths with Congestion problem, it is easy to prove that DEDP is NP-complete for fixed k ≥ 3 and s ≥ 1, even if c is large with respect to n, namely at most n -n α for some real value 0 < α ≤ 1, and W [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hard in DAGs with parameter k. By applying the framework of Johnson et al. [START_REF] Johnson | Directed tree-width[END_REF], we give an n O(k+w) algorithm to solve DEDP in digraphs with directed tree-width at most w.

The fact that DEDP is NP-complete for fixed values of k = 2, c = 0, and s = 1 [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF] motivates us to consider the "dual" parameter d = n -c. That is, instead of bounding from above the number of vertices of D that lie in the intersection of many paths of a collection satisfying the given requests, we want to bound from below the number of vertices that occur only in few paths of the collection. Formally, we want to find X ⊆ V (D) with |X| ≥ d such that there is a collection of paths P satisfying the given requests such that every vertex in X is in at most s paths of the collection. We first prove, from a reduction from the Independent Set problem, that DEDP is W[1]-hard with parameter d for every fixed s ≥ 0, even if the input graph is a DAG and all source vertices of the request set are the same.

Our main contribution consists of positive algorithmic results for this dual parameterization. On the one hand, we give an algorithm for DEDP running in time O(n d • k d•s ). This algorithm is not complicated, and basically performs a brute-force search over all vertex sets of size d, followed by k connectivity tests in a digraph D obtained from D by an appropriate local modification. On the other hand, our most technically involved result is a kernel for DEDP with at most d • 2 k-s • k s non-terminal vertices. This algorithm first starts by a reduction rule that eliminates what we call congested vertices; we say that the resulting instance is clean. We then show that if D is clean and sufficiently large, and k = s + 1, then the instance is positive and a solution can be found in polynomial time. This fact is used as the base case of an iterative algorithm. Namely, we start with the original instance and proceed through k -s + 1 iterations. At each iteration, we choose one path from some s i to its destination t i such that a large part of the graph remains unused by any of the pairs chosen so far (we prove that such a request always exists) and consider only the remaining requests for the next iteration. We repeat this procedure until we arrive at an instance where the number of requests is exactly s + 1, and use the base case to output a solution for it. From this solution, we extract in polynomial time a solution for the original instance, yielding a kernel of the claimed size. Since positive results for the Directed Disjoint Paths problem are not common in the literature, especially in general digraphs, we consider our algorithmic results to be of particular interest. Furthermore, the kernelization algorithm also brings good news for the Steiner Network problem: when s = 0 Feldmann and Marx in [START_REF] Emil | The complexity landscape of fixed-parameter directed Steiner network problems[END_REF] showed that the tractability of the Steiner Network problem when parameterized by the number of requests depends on how the requests are structured. Our result adds to the latter by showing that the problem remains FPT if we drop this structural condition on the request set but add d, the number of vertices occurring in at most s paths of the solution, as a parameter. More details can be found in Section 2.

Table 1 shows a summary of our algorithmic and complexity results, which altogether provide an accurate picture of the parameterized complexity of the DEDP problem for distinct choices of the parameters.

Organization.

In Section 2 we present some preliminaries and formally define the Disjoint Enough Directed Paths problem. 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 for completeness we recall some basic definitions in the full version of this article, available at https://arxiv.org/abs/1909.13848. Due to space limitations, the basic definitions of arboreal decompositions and directed tree-width can also be found in the full version. We provide the hardness results in Section 3. The XP algorithm with parameters k and w for DEDP in graphs with directed tree-width at most w can be found in the full version. The algorithms with d as a parameter are given in Section 4. We conclude the article in Section 5 with some open questions for further research. The proofs of the three results marked with '( )' can be found in the full version.

Preliminaries and definitions

All paths mentioned henceforth, unless stated otherwise, are considered to be directed. For a graph G = (V, E), directed or not, and a set X ⊆ V (G), we write G -X for the graph resulting from the deletion of X from G and G[X] for the graph induced by X. If e is an edge of a directed or undirected graph with extremities u and v, we may refer to e as (u, v).

For v ∈ V (G), we write deg G (v) to be the degree of v in G, and N + (v), N -(v) for the set of out-neighbors and in-neighbors of v, respectively, when G is a digraph. We also write G ⊆ G to say that G is a subgraph of G. A weak component of a directed graph D is set of vertices inducing a connected component in the underlying graph of D. Unless stated otherwise, n will always denote the number of vertices of the input graph. For an integer ≥ 1, we denote by [ ] the set {1, 2, . . . , }. We also make use of Menger's Theorem [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF] for digraphs. Here a (u, v)-separator is a set of vertices X such that there is no path from u to v in D -X.

Theorem 1 (Menger's Theorem). Let D be a digraph and u, v ∈ V (D) such that (u, v) ∈ E(D). Then the minimum size of a (u, v)-separator equals the maximum number of pairwise internally vertex-disjoint paths from u to v.

For two positive integers a and b with a ≥ b, the Stirling number of the second kind [START_REF] Khristo | Close Encounters with the Stirling Numbers of the Second Kind[END_REF], denoted by Stirling(a, b), counts the number of ways to partition a set of a objects into b non-empty subsets, and is bounded from above by

1 2 a b • b a-b .
Before defining the problem, we define requests and satisfying collections.

Definition 2 (Requests and satisfying collections). Let D be a digraph and P be a collection of paths of D. A request in D is a pair of vertices of D. For a request set I = {(s 1 , t 1 ), (s 2 , t 2 ), . . . , (s k , t k )}, we say that the vertices {s 1 , s 2 , . . . , s k } are source vertices and that {t 1 , t 2 , . . . , t k } are target vertices, and we refer to them as S(I) and T (I), respectively. We say that P satisfies

I if P = {P 1 , . . . , P k } and P i is a path from s i to t i , for i ∈ [k].
We remark that a request set may contain many copies of the same pair, and that when considering the union of two or more requests, we keep all such copies in the resulting request set. For instance, if

I 1 = {(u 1 , v 1 )} and I 2 = {(u 1 , v 1 ), (u 2 , v 2 )} then I 1 ∪ I 2 = {(u 1 , v 1 ), (u 1 , v 1 ), (u 2 , v 2 )},
and this indicates that a collection of paths satisfying this request set must contain two paths from u 1 to v 1 . The DEDP problem is defined as follows.

Disjoint Enough Directed Paths (DEDP)

Input:

A digraph D, a request set I of size k, and two non-negative integers c and s.

Output: A collection of paths P satisfying I such that at most c vertices of D occur in at least s + 1 paths of P and all other vertices of D occur in at most s paths of P.

Unless stated otherwise, we consider d = n -c for the remaining of this article. Intuitively, c imposes an upper bound on the size of the "congested" part of the solution, while d imposes a lower bound on the size of the "disjoint" part. For a parameterized version of DEDP, we sometimes include the parameters before the name. For instance, we denote by (k, d)-DEDP the Disjoint Enough Directed Paths problem with parameters k and d.

Notice that if c ≥ n or s ≥ k, the problem is trivial since every vertex of the graph is allowed to be in all paths of a collection satisfying the requests, and thus we need only to check for connectivity between the given pairs of vertices. Furthermore, if there is a pair (s i , t i ) in the request set such that there is no path from s i to t i in the input digraph D, the instance is negative. Thus we henceforth assume that c < n, that s < k, and that there is a path from s i to t i in D for every pair (s i , t i ) in the set of requests.

Let 0 < α ≤ 1. Choosing the values of k, d, and s appropriately, we show in Table 2 that the DEDP problem generalizes several problems in the literature. The last line of Table 2 is of particular interest, and we focus on it in the next two paragraphs. In the Steiner Network problem, we are given a digraph D and a request set I and we are asked to find an induced subgraph D of D with minimum number of vertices such that D admits a collection of paths satisfying I. For a request set I in a digraph D, let D(I) be the digraph with vertex set S(I) ∪ T (I) and edge set {(s, t) | (s, t) ∈ I}. The complexity landscape of the Steiner Network problem when parameterized by the size of the request set was given by Feldmann and Marx [START_REF] Emil | The complexity landscape of fixed-parameter directed Steiner network problems[END_REF]. They showed that the tractability of the problem depends on D(I). Namely, they proved that if D(I) is close to being a caterpillar, then the Steiner network problem is FPT when parameterized by |I|, and W[1]-hard otherwise. When parameterized by the size of the solution, Jones et al. [START_REF] Jones | Parameterized Complexity of Directed Steiner Tree on Sparse Graphs[END_REF] showed that the Steiner Network problem is FPT when D[I] is a star whose edges are all oriented from the unique source and the underlying graph of the input digraph excludes a topological minor, and W[2]-hard on graphs of degeneracy two [START_REF] Jones | Parameterized Complexity of Directed Steiner Tree on Sparse Graphs[END_REF].

Our algorithmic results for DEDP for the particular case s = 0 yield an FPT algorithm for another parameterized variant of the Steiner Network problem. In this case, we want to decide whether D admits a large set of vertices whose removal does not disconnect any pair of requests. That is, we want to find a set X ⊆ V (D) with |X| ≥ d such that D -X contains a collection of paths satisfying I. In Theorem 15 we give an FPT algorithm (in fact, a kernel) for this problem with parameters |I| and d. We remark that this tractability does not depend on D(I). As mentioned in [START_REF] Jones | Parameterized Complexity of Directed Steiner Tree on Sparse Graphs[END_REF], the Steiner Network problem is W[2]-hard when parameterized by the size of the solution (as a consequence of the results of [START_REF] Mölle | Enumerate and expand: improved algorithms for connected vertex cover and tree cover[END_REF]). Hence (c)-DEDP is W[2]-hard for fixed s = 0. As discussed in the introduction, the Directed Disjoint Paths problem is NP-complete for fixed k = 2 [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF] and W[1]-hard with parameter k in DAGs [START_REF] Slivkins | Parameterized tractability of edge-disjoint paths on directed acyclic graphs[END_REF]. Allowing for vertex congestion does not improve the tractability of the problem: Disjoint Paths with Congestion parameterized by number of requests is also W [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hard in DAGs for every fixed congestion c ≥ 1, as observed in [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]. When c = 0 and s ≥ 1, DEDP is equivalent to the Directed Disjoint Paths with Congestion problem and thus the aforementioned bounds also apply to it. In the following theorem we complete this picture by showing that DEDP is NP-complete for fixed k ≥ 3 and s ≥ 1, even if c is quite large with respect to n (note that if c = n all instances are trivially positive), namely for c as large as n -n α with α being any fixed real number such that 0 < α ≤ 1. The same reduction also allows to prove W [START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hardness in DAGs with parameter k. The idea is, given the instance of DDPC, build an instance of DEDP where the "disjoint" part corresponds to the original instance, and the "congested" part consists of c new vertices that are necessarily used by s + 1 paths. This is why we restrict the value of d to be of the form n α , but not smaller; otherwise, the "disjoint" part, which corresponds to the instance of DDPC, would be too small compared to the total size of the graph, and a brute-force algorithm could solve the problem in polynomial time. Next, we show that (d)-DEDP is W[1]-hard, even when the input graph is acyclic and all source vertices of the request set are the same. The reduction is from Independent Set parameterized by the size of the solution, which is W[1]-hard [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF]. Theorem 4. The DEDP problem is W[1]-hard with parameter d for every fixed s ≥ 0, even when the input graph is acyclic and all source vertices in the request set are the same.

Proof. Let (G, d) be an instance of the Independent Set problem, in which we want to decide whether the (undirected) graph G contains an independent set of size at least d, and s be a non-negative integer. Let V E be the set {v e | e ∈ E(G)} and D a directed graph with vertex set V (G) ∪ {r} ∪ V E . Add to D the following edges:

• for every v ∈ V (G), add the edge (r, v); and • for every edge e ∈ E(G) with endpoints u and w, add the edges (u, v e ) and (w, v e ). Finally, for every v e ∈ V E , add to I 2s + 1 copies of the pair (r, v e ). Figure 1 For the necessity, let X be an independent set of size d in G and let u ∈ X. Start with a collection P = ∅. We classify the edges of G into two sets: the set E 1 containing all edges with both endpoints in V (G) -X, and the set E 2 containing all edges with exactly one endpoint in X. Now, for each e ∈ E 1 , chose arbitrarily one endpoint u of e and add to P 2s + 1 copies of the path in D from r to v e using u. For each e ∈ E 2 with e = (u, w) and w ∈ X, add to P 2s + 1 copies of the path in D from r to v e using w. Since X is an independent set, no vertex in X occurs in any path of P, and since E(G) = E 1 ∪ E 2 , P satisfies I and the necessity follows as c = n -d.

Let P be a solution for (D, I, k, c, s) and X ⊆ V (D) be a set of vertices with |X| = d and such that each vertex of X occurs in at most s paths of P. Such choice is possible since d = n -c. For contradiction, assume that X is not an independent set in G. Then there is an edge e ∈ E(G) with e = (u, w) and u, w ∈ X, and 2s + 1 copies of the request (r, v e ) in I. Thus each path satisfying one of those requests uses u or w, but not both, and therefore either u or w occurs in at least s + 1 paths of P, a contradiction. We conclude that X is an independent set in G and the sufficiency follows.

Algorithms for DEDP including d as a parameter

In this section we focus on algorithmic results for DEDP. In Theorem 3 we showed that DEDP is NP-complete for fixed k ≥ It is worth mentioning that this kind of dual parameterization has proved useful in order to improve the tractability of several notoriously hard problems (cf. for instance [1-3, 6, 10]).

The following definition will be useful in the description of the algorithms of this section.

Definition 5.

Let D be a graph, I be a request set with I = {(s 1 , t 1 ), . . . , (s k , t k )}, and s be an integer. We say that a set X ⊆ V (D) is s-viable for I if there is a collection of paths P satisfying I such that each vertex of X occurs in at most s paths of P. We also say that P is certifying X.

Thus an instance (D, I, k, c, s) of DEDP is positive if and only if D contains an s-viable set X with |X| ≥ d. Since we now consider d as a parameter instead of c, from this point onwards we may refer to instances of DEDP as ( D,I,k,d,s).

Theorem 6 ( ).

There is an algorithm running in time O(n d+2 • k d•s ) for the Disjoint Enough Directed Paths problem.

We now proceed to show that (k, d, s)-DEDP is FPT, by providing a kernel with at most d • 2 k-s • k s + 2k vertices. We start with some definitions and technical lemmas. We remark that any vertex in D whose deletion disconnects more than s pairs in the request set cannot be contained in any solution for an instance of DEDP. Hence we make use of an operation to eliminate all such vertices from the input graph while maintaining connectivity. We use the following definitions. We remind the reader that, for a request set That is, V * (D) is the set of non-terminal (i.e., neither source nor target) vertices of D. (D,I,k,d,s) be an instance of DEDP. For X ⊆ V * (D), we define I X as the subset of I that is blocked by X, that is, there are no paths from s to t in D -X for every (s i , t i ) ∈ I X . We say that a vertex v ∈

Definition 8 (Congested vertex and blocking collection). Let

V * (D) is an (I, s)-congested vertex of D if |I {v} | ≥ s + 1. The blocking collection of I is the collection {B 1 , . . . , B k } where B i = {v ∈ V * (D) | (s i , t i ) ∈ I {v} }, for i ∈ [k].
We say that D is clean for I and that ( D,I,k,d,s) is a clean instance if there are no congested vertices in V * (D). When I and s are clear from the context, we drop them from the notation.

We use the following operation (cf. Figure 2) to eliminate congested vertices of D while maintaining connectivity. It is used, for instance, in [START_REF] Chitnis | Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset[END_REF] (as the torso operation) and in [START_REF] Kratsch | Fixed-parameter tractability of multicut in directed acyclic graphs[END_REF]. We restrict our attention to vertices in V * (D) in Definition 8 because we want to avoid bypassing source or target vertices, and work only with vertices inside V * (D). Since |S(I) ∪ T (I)| ≤ 2k, we show later that this incurs an additive term of 2k in the size of the constructed kernel.

In [START_REF] Kratsch | Fixed-parameter tractability of multicut in directed acyclic graphs[END_REF] it is shown that the ending result of bypassing a set of vertices in a digraph does not depend on the order in which those vertices are bypassed. Furthermore, bypassing a vertex of D cannot generate a new congested vertex: if u is a congested vertex of D/v, then u is also a congested vertex of D, for any v ∈ V (D) \ {u}. Thus any instance (D, I, k, d, s) of DEDP is equivalent to the instance (D/v, I, k, d, s), if v is a congested vertex of D, and arbitrarily bypassing a vertex of D can only make the problem harder. We formally state those observations below. ,I,k,d,s). Then, X is a solution for the former if and only if X is a solution for the latter.

Proof. Let X be a solution for (D, I, k, d, s). We claim that X ∩ B = ∅. Otherwise, at least s + 1 paths of any collection satisfying I must intersect in X, contradicting our choice for X. Hence X ⊆ V (D ) and is a solution for (D , I, k, d, s). Similarly, if X ⊆ V (D ) then X ∩ B = ∅ and the sufficiency follows. Thus, any solution for an instance resulting from bypassing a set of vertices in V * (D) is also a solution for the original instance. The main ideas of the kernelization algorithm are the following. Let (D, I, k, d, s) be an instance of DEDP and {B 1 , . . . , B k } be the blocking collection of I. First, we show that, if D is clean for I, there is an i ∈ [START_REF] Emil | The complexity landscape of fixed-parameter directed Steiner network problems[END_REF]. Then, we show that if D is clean and sufficiently large, and |I| = s + 1, then the instance is positive and a solution can be found in polynomial time (Lemma 13).

[k] such that |V * (D) -B i | ≥ n/(k -s)k (Lemma
Lemma 13 is used as the base case for our iterative algorithm. We start with the first instance, say (D, I, k, d, s), and proceed through k -s + 1 iterations. At each iteration, we will choose one path from some s i to its destination t i such that a large part of the graph remains unused by any of the pairs chosen so far (by Lemma 12) and consider the request set containing only the remaining pairs for the next iteration. We repeat this procedure until we arrive at an instance where the number of requests is exactly s + 1, and show that if n is large enough, then we can use Lemma 13 to output a solution for the last instance. From this solution, we extract a solution for (D, I, k, d, s) in polynomial time.

|B i | = v∈V * (D) |I v | ≤ n * • s. (1) Now, if |B i | > n * • s/k for every i ∈ [k],
we have a contradiction with Equation (1). We conclude that there is an i ∈

[k] such that |B i | ≤ n * • s/k. Thus, V * (D/B i ) = n * -|B i | ≥ n * (k -s)/k, as desired.
If there is only one path P from s i to t i in D/B i , then V * (P ) = ∅ since every path from s i to t i in D is contained in B i ∪ S(I) ∪ T (I) and the result follows. Thus we can assume that there are at least two paths from s i to t i in D/B i and at least one of them intersects V * (D/B i ) (see Figure 3). Let X = (S(I) ∪ T (I)) \ {s i , t i }. By Menger's Theorem, there ∈ S(I) ∪ T (I) are two internally disjoint paths P 1 and P 2 from s i to t i in (D/B i )/X. Without loss of generality, assume that P 1 is the shortest of those two paths, breaking ties arbitrarily. Then |V * (P 1 )| ≤ |V * (D/B i )|/2 since P 1 and P 2 are disjoint, and the result follows.

s i t i
Figure 4 illustrates the procedure described in Lemma 12. We find a set B i containing at most n * • s/k vertices, and bypass all of its vertices in any order. Then we argue that a shortest path from s i to t i in D/B i avoids a large set of vertices in D. Proof. Let {B 1 , . . . , B k } be the blocking collection of I and

D i = D/B i , for i ∈ [k]. By Lemma 12, there is an i ∈ [k] such that |V * (D i )| ≥ n * /(s + 1) and a path P from s i to t i such that V * (P ) ≤ |V * (D i )|/2. Let D i = D i /V * (P ). Now, |V * (D i )| ≥ |V * (D i )| 2 ≥ n * 2(s + 1)
and since |I \ {(s i , t i )}| = s, we are free to choose arbitrarily any collection of paths satisfying I \ {(s i , t i )} in D i . Reversing the bypasses done in D, this collection together with P i yields a collection of paths satisfying I in D such that all vertices in V * (D i ) are contained in at most s of those paths. Since n * ≥ 2d(s + 1) by hypothesis, we have that |V * (D i )| ≥ d as required. Proof. Let B 0 = {B 1 , . . . , B k } be the blocking collection of I. We consider B 0 to be sorted in non-decreasing order by the size of its elements and, by rearranging I if needed, we assume that this order agrees with I.

s i t i D/(B i ∪ V * (P )) B i
For i ∈ [k -(s + 1)], we construct a sequence of sets {D i , B i , P i } where n * i = |V * (D i )| and (i) B i = {B i+1 , . . . , B k };
(ii) P i is a collection of paths {P 1 , P 2 , . . . , P i } such that P j is a path from s j to t j in D j , for j ∈ [i]; and (iii) n * i-1 is large enough to guarantee that we can find a path from s i to t i avoiding a large part of D i-1 . Formally, we want that

n * i ≥ n * 0 • (k -s)(k -s -1) • • • (k -s -i + 1) 2 i • k(k -1) • • • (k -i + 1
) .

We begin with D 0 = D, n * 0 = n * , and P 0 = ∅. Let D 1 = D 0 /B 1 . By applying Lemma 12 with input (D 0 , I, k, d, s), we conclude that |V * (D 1 )| ≥ n * (k -s)/k and there is a path P

1 from s 1 to t 1 in D 1 with |V * (P 1 )| ≤ |V * (D 1 )|/2. Let D 1 = D 1 /V * (P 1 ) and P 1 = {P 1 }. Now, n * 1 ≥ |V * (D 1 )| 2 ≥ n * 0 (k -s) 2k
and conditions (i), (ii), and (iii) above hold for (D 1 , B 1 , P 1 ). Assume that i -1 triples have been chosen in this way.

As before, we assume that B i-1 is sorted in non-increasing order by the size of its elements, and that this order agrees with

I \ I i-1 . Furthermore, as D 0 is clean, so is D i-1 . Let D i = D i-1 /B i . Applying Lemma 12 with input (D i-1 , I \ I i-1 , k -i + 1, d, s), we conclude that |V * (D i )| ≥ n * i (k -i + 1 -s)/(k -i + 1
) and there is a path

P i from s i to t i in D i with |V * (P i )| ≤ |V * (D i )|/2. Let P i = P i-1 ∪ {P i } and D i = D i /B i . Then n * i ≥ n * i-1 • k -i + 1 -s 2(k -i + 1)
M F C S 2 0 2 0 68:12 A Relaxation of the Directed Disjoint Paths Problem and by our assumption that (iii) holds for n i-1 it follows that

n * i ≥ n * 0 • (k -s)(k -s -1) • • • (k -s -i + 2) 2 i-1 k(k -1) • • • (k -i + 2) • k -s -i + 1 2(k -i + 1) = n * 0 • (k -s)(k -s -1) • • • (k -s -i + 1) 2 i • k(k -1) • • • (k -i + 1
) , as desired and thus (i), (ii), and (iii) hold for (D i , B i , P i ). The algorithm ends after iteration k -(s + 1). Following this procedure, we construct the collection P k-(s+1) = {P 1 , P 2 , . . . , P k-(s+1) } satisfying (ii) and the graph D k-(s+1) with n k-(s+i) satisfying (iii). Noticing that |I -I k-(s+1) | = s + 1 (that is, only s + 1 pairs in I are not accounted for in P k-(s+1) ), it remains to show that our choice for n * is large enough so that we are able to apply Lemma 13 on the instance (D k-(s+1) , I -I k-(s+1) , s + 1, d, s) of DEDP. That is, we want that n * k-(s+1) ≥ 2d(s + 1). By (iii) it is enough to show that

n * k-(s+1) ≥ n * 0 • (k -s)(k -s -1) • • • 3 • 2 2 k-(s+1) • k(k -1) • • • (s + 3)(s + 2)
≥ 2d • (s + 1), and rewriting both sides of the fraction as k! and k!/(s + 1)!, respectively, we get

n 0 • (k -s)! 2 k-(s+1) ≥ 2d • (s + 1) • k! (s + 1)! = 2d • k! s! ,
which holds for We acknowledge that it is possible to prove Theorem 14 without using Lemma 13 by stopping the iteration at the digraph D k-s instead of D k-s-1 . However we believe it is easier to present the proof of Theorem 14 by having separate proofs for the iteration procedure (Lemma 12) that aims to generate an instance of DEDP for which we can apply our base case (Lemma 13).

n 0 ≥ 2 k-(s+1) • 2d • (s + 1) (s + 1)! • k! (k -s)! = d • 2 k-s • k s ,
Since any instance can be made clean in polynomial time, the kernelization algorithm for

6 A

 6 Parameters Generalizes Complexity d = n, s = 1 Disjoint Paths NP-complete for k = 2 [13] d = n, s ≥ 2 Disjoint Paths with Congestion NP-complete for k ≥ 3 d ≥ 1, s = 0 Steiner Network FPT with parameters k and d M F C S 2 0 2 0 68:Relaxation of the Directed Disjoint Paths Problem

3

  Hardness results for DEDPIn this section we provide hardness results for the DEDP problem. Namely, we first provide in Theorem 3 a simple reduction from Disjoint Paths with Congestion, implying NPcompleteness for fixed values of k, c, d and W[START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hardness in DAGs with parameter k. We then prove in Theorem 4 that DEDP is W[START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hard in DAGs with parameter d.

Theorem 3 (

 3 ). Let 0 < α ≤ 1, d = n α , and c = n -d . Then: (i) DEDP is NP-complete for every fixed k ≥ 3 and s ≥ 1; and (ii) (k)-DEDP is W[START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hard in DAGs for every fixed s ≥ 1.

Figure 1

 1 Figure 1 Example of the construction from Theorem 4 with s = 1 and e = (u, w). A dashed line indicates a request in I.

M 8 A

 8 3 and a large range of values of c. The proof does not hold, for example, when c = n -d for a constant d. We also showed that considering only d Relaxation of the Directed Disjoint Paths Problem as a parameter is still not enough to improve the tractability of the problem: Theorem 4 shows that (d)-DEDP is W[START_REF] Saeed Akhoondian Amiri | Routing with congestion in acyclic digraphs[END_REF]-hard in DAGs even if all requests share the same source. The situation changes when we consider stronger parameterizations including d: we show that the problem is XP with parameters d and s (cf. Theorem 6), and FPT with parameters k and d (hence s as well, since we may assume that k > s as discussed below; cf. Theorem 15).

  I, we denote by S(I) the set of source vertices in I and by T (I) the set of target vertices in I (cf. Definition 2). Definition 7 (Non-terminal vertices). Let (D, I, k, d, s) be an instance of DEDP. For a digraph D such that V (D ) ⊆ V (D), we define V * (D ) = V (D ) \ (S(I) ∪ T (I)).

v⇒Figure 2 Definition 9 (

 29 Figure 2 Bypassing a vertex v.

Lemma 10 .

 10 Let (D, I, k, d, s) be an instance of DEDP and B be the set of (I, s)-congested vertices of D. Let D = D/B and consider the instance (D

Remark 11 .

 11 Let (D, I, k, d, s) be an instance of DEDP and Y ⊆ V * (D). If X is a solution for (D/Y, I, k, d, s), then X is also a solution for (D, I, k, d, s).

Lemma 12 . 10 A

 1210 Let (D, I, k, d, s) be an instance of DEDP, {B 1 , . . . , B k } be the blocking collection of I, andn * = |V * (D)|. If D is clean, then there is an i ∈ [k] such that |V * (D/B i )| ≥ n * (k -s)/k and there is a path P in D/B i from s i to t i such that |V * (P )| ≤ |V * (D/B i )|/2.Relaxation of the Directed Disjoint Paths Problem Proof. Consider the undirected bipartite graph H with vertex set {b i | i ∈ [k]} ∪ V * (D), where each b i is a new vertex. Add to H one edge linking a vertex b i to a vertex v if and only if v ∈ B i . Now, the size of each B i is exactly the degree deg H (b i ) of b i in H, and the size of |I v |, for v ∈ V * (D), is exactly the degree of v in H. Also notice that |I v | ≤ s for every v ∈ V * (D), since D is clean for I. As H is bipartite, we have that i∈[k] deg H (b i ) = v∈V * (D) deg H (v), which in turn implies that i∈[k]

Figure 3

 3 Figure 3 Three paths from si to ti in D/Bi. Square vertices are used to identify vertices in S(I) ∪ T (I), which may not be bypassed.

Lemma 13 .

 13 Let (D, I, k, d, s) be an instance of DEDP, m = |E(D)|, and n * = V * (D). If D is clean, n * ≥ 2d(s + 1), and k = s + 1,then (D, I, k, d, s) is positive and a solution can be found in time O(k • n(n + m)).

Figure 4 A

 4 Figure 4 A path P from si to ti avoiding a large part of D.

  as desired. Applying Lemma 13 with input (D k-(s+1) , I \ I k-(s+1) , s + 1, d, s) yields a collection P satisfying I -I k-(s+1) and a set X ⊆ V (D) of size d such that X is disjoint from all paths in P k-(s+1) , since all vertices in V * (P ) were bypassed in D k-(s+1) for every P ∈ P k-(s+1) , and all vertices in X occur in at most s paths of P. We can construct a collection of paths satisfying I from P ∪ P k-(s+1) by reversing all the bypasses done in D and connecting appropriately the paths in the collections. We output this newly generated collection together with X as a solution for (D, I, k, d, s). For the running time, let m = |(E(D)|. We need time O(k log k) to order the elements of B 0 , O(k • n(n + m)) to find the sets B i , for i ∈ [k], and O(n + m) to find each of the paths {P 1 , . . . , P k }. Hence the algorithm runs in time O(k • n 2 (n + m)).

  (k, d, s)-DEDP follows easily. Given an instance (D, I, k, d, s), we bypass all congested vertices of D to generate D . If |V * (D )| is large enough to apply Theorem 14, the instance is positive and we can find a solution in polynomial time. Otherwise, we generated an equivalent instance (D , I, k, d, s) with |V (D )| bounded from above by a function depending on k, d, and s only. As we restrict |S(I) ∪ T (I)| ≤ 2k, if D is clean and V (D) ≥ d • 2 k-s • k s + 2k we get the desired bound for |V * (D)|. Thus, the following is a direct corollary of Theorem 14.

Table 1

 1 Summary of hardness and algorithmic results for distinct choices of the parameters. A horizontal line in a cell means no restrictions for that case. In all cases, we have that c = n -d.

	k	d	s	w	Complexity
	fixed ≥ 3	n α	fixed ≥ 1	-	NP-complete (Theorem 3)
	parameter	n α	fixed ≥ 1	0	W[1]-hard (Theorem 3)
	input	parameter	fixed ≥ 0	-	W[1]-hard (Theorem 4)
	parameter	-	-	parameter XP (see full version)
	input	parameter parameter	-	XP (Theorem 6)
	parameter parameter parameter	-	FPT (Theorem 15)

Table 2

 2 Summary of related problems and complexity results.

M F C S 2 0 2 0

-CE40-0028) and ESIGMA (ANR-17-CE23-0010).

68:13

Theorem 15. There is a kernelization algorithm running in time O(k • n 2 (n + m)) that, given an instance (D, I, k, d, s) of DEDP, outputs either a solution for the instance or an equivalent instance (D , I, k, d, s) with |V (D )| ≤ d • 2 k-s • k s + 2k.

Concluding remarks

We introduced the Disjoint Enough Directed Paths problem and provided a number of hardness and algorithmic results, summarized in Table 1. Several questions remain open. We showed that DEDP is NP-complete for every fixed k ≥ 3 and s ≥ 1. We do not know whether DEDP is also NP-complete for k = 2 and s = 1.

We provided an algorithm running in time O(n d+2 • k d•s ) to solve the problem. This algorithm tests all partitions of a given X ⊆ V (D) in search for one that respects some properties. Since there are at most n d subsets of V (D) of size d, this yields an XP algorithm. The second term on the time complexity comes from the number of partitions of X we need to test. The problem may become easier if X is already given or, similarly, if d is a constant. In other words, is the (s)-DEDP problem FPT for fixed d?

Our main result is a kernel with at most d • 2 k-s • k s + 2k vertices. The natural question is whether the problem admits a polynomial kernel with parameters k, d, and s, or even for fixed s. Notice that if there is a constant such that k -s = , then the size of the kernel is d • 2 • k , which is polynomial on d and k. The case s = 0 is also particularly interesting, as DEDP with s = 0 is equivalent to the Steiner Network problem. In this case, we get a kernel of size at most d • 2 k + 2k.

While we do not know whether (k, d, s)-DEDP admits a polynomial kernel, at least we are able to prove that a negative answer for s = 0 is enough to show that (k, d, s)-DEDP is unlikely to admit a polynomial kernel for any value of s ≥ 1 when k is "far" from s, via the following polynomial time and parameter reduction. Any solution for the first instance is also a solution for the second, and thus the necessity holds. For the sufficiency, let X be a s-viable set for (D, I , k , d, s) with certifying collection P . Since k = k • d • s + 1 and at most d • s paths in P can intersect X, for each pair (s, t) ∈ I there is path P ∈ P from s to t in D -X. Choosing all such paths we construct a collection P satisfying I in D -X and the result follows.

In the undirected case, the Steiner Tree problem is unlikely to admit a polynomial kernel parameterized by k and c, with c = n -d (in other words, the size of the solution); a simple proof for this result can be found in [START_REF] Cygan | Parameterized Algorithms[END_REF]Chapter 15]. Even if we consider a stronger parameter (that is, d instead of c), dealing with directed graphs may turn the problem much harder. We also remark that the problem admits a polynomial kernel in the undirected case if the input graph is planar [START_REF] Pilipczuk | Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs[END_REF]. It may also be the case for directed graphs.


Yann Girard
email: yann.girard@u-paris.fr

Quentin Berrahal

Cyril Chacon

Hakim Amara

Amandine Bellec

Sylvain Latil

Vincent Repain

Sylvie Rousset

Jerome Lagoute

Jérôme Lagoute

High density synthesis of topological point defects in graphene on 6H-SiC(000 1 ¯)

Keywords: Graphene, Grain Boundaries, Defect engineering, Growth, Silicon carbide, Scanning tunelling microscopy/ spectroscopy, Density functional theory

Introduction

Control of defect formation (either point-like or extended) in graphene is a challenge as they have long been seen as major drag on the pursuit of good quality graphene. However, they gained interest in the last few years as tuning knobs for the unique properties of graphene [START_REF] Wu | Spectroscopic investigation of defects in two-dimensional materials[END_REF]. One can, for example, change the position of the Dirac point through atomic substitution (doping) for n or p conductivity [START_REF] Joucken | Localized state and charge transfer in nitrogen-doped graphene[END_REF][START_REF] Zhao | Visualizing Individual Nitrogen Dopants in Monolayer Graphene[END_REF][START_REF] Zhao | Local Atomic and Electronic Structure of Boron Chemical Doping in Monolayer Graphene[END_REF][START_REF] Joucken | Electronic properties of chemically doped graphene[END_REF], or create resonant state through single atomic vacancies for monitoring the grafting or functionalization of molecules [START_REF] Ducastelle | Electronic structure of vacancy resonant states in graphene: A critical review of the single-vacancy case[END_REF]. Origin of defects in graphene is threefold: they either are native, induced by an external parameter during the synthesis or created afterwards. In polycrystalline graphene, Grain Boundaries (GB) are of the first kind. These 1D defects, mainly composed of pentagons, hexagons, heptagons and vacancies, mark out the separation between two domains of graphene which have different orientation with respect to each other [START_REF] Tison | Grain Boundaries in Graphene on SiC[END_REF][START_REF] Yang | Structure of graphene and its disorders: A review[END_REF]. Having almost all the possible orientations they can eventually form loops encompassing domains of small sizes. They are called Grain Boundary Loops (GBL) and the smallest GBL encompassing 24 atoms, called a one grain boundary loop or a "Flower Defect"(FD), can be seen as a ±π/6 rotation of seven rings inside a graphene grain [START_REF] Cockayne | Grain boundary loops in graphene[END_REF].

Recently, those FD have attracted great interest towards nanotechnological electronic applications. First, they induce very large modifications of transport properties compared to other point-like defects [START_REF] Linhart | Accurate modeling of defects in graphene transport calculations[END_REF]; second, they create a high spin polarization in zigzag graphene nanoribbon [START_REF] Kang | Spin Transport in Zigzag Graphene Nanoribbon with a Flower Defect[END_REF]; third, they are able to filter electrons from holes, which have applications for electron energy filtering [START_REF] Cresti | Growth, charge and thermal transport of flowered graphene[END_REF]; fourth, they are good candidates for allelectronic valley based-devices [START_REF] Chen | Structure and electronic properties of closed-ring defects in epitaxial graphene[END_REF]. From theoretical point of view, it is also interesting to note that similar flat geometric defects in honeycomb arrangement have been observed on hexagonal bilayer silica [START_REF] Björkman | Defects in bilayer silica and graphene: Common trends in diverse hexagonal two-dimensional systems[END_REF] and rubrene on Au(111) [START_REF] Pivetta | Two-Dimensional Tiling by Rubrene Molecules Self-Assembled in Supramolecular Pentagons, Hexagons, and Heptagons on a Au(111) Surface[END_REF]. Nevertheless, their formation on substrates is interesting for applications at wafer scale, but are very rare and rather uncontrolled. So, it is a challenging task to obtain an experimental process which induces selectively a large density of this defect. Some rare FD appear on various substrates, as a native defect in epitaxial graphene grown on silicon carbide (Si rich SiC(0001) and C rich SiC(0001) surfaces) [START_REF] An | Graphitization of 6H-SiC(000\bar1) Surface by Scanning Tunneling Microscopy[END_REF][START_REF] Rutter | Scattering and Interference in Epitaxial Graphene[END_REF][START_REF] Guisinger | Atomic-scale investigation of graphene formation on 6H-SiC[END_REF][START_REF] Simon | Symmetry of standing waves generated by a point defect in epitaxial graphene[END_REF], as an externally-induced defect during the Chemical Vapor Deposition (CVD) growth of graphene on copper or nickel [START_REF] Zhao | Local Atomic and Electronic Structure of Boron Chemical Doping in Monolayer Graphene[END_REF][START_REF] Park | Growth and properties of chemically modified graphene[END_REF][START_REF] Rasool | Atomic-Scale Characterization of Graphene Grown on Copper (100) Single Crystals[END_REF], as a result of a post-synthesis annealing in graphene on rhodium [START_REF] Yan | Electronic structures of graphene layers on a metal foil: The effect of atomic-scale defects[END_REF]. High density of FD, around 10 11 cm -2 , has already been obtained after a few tens of minutes annealing of SiC(0001) surface around 1 250-1 350 • C [START_REF] Cui | Structural Evolution of Flower Defects and Effects on the Electronic Structures of Epitaxial Graphene[END_REF], or assisted by bismuth (Bi) during the graphene synthesis on SiC(0001) [START_REF] Hu | Bismuth mediated defect engineering of epitaxial graphene on SiC[END_REF]. Nevertheless, FD are always associated with an equivalent den-sity of other atomic and nanoscale defects as vacancies, mounds and nanotubes or substitutional atoms [START_REF] Guisinger | Atomic-scale investigation of graphene formation on 6H-SiC[END_REF][START_REF] Cui | Structural Evolution of Flower Defects and Effects on the Electronic Structures of Epitaxial Graphene[END_REF][START_REF] Hu | Bismuth mediated defect engineering of epitaxial graphene on SiC[END_REF]. So, none of the existing works provide a procedure to achieve selectively a high density of FD.

We also have to mention that numerous experiments performed on suspended graphene have studied their formation, migration and annihilation under the beam of Transmission Electron Microscopy (TEM) [START_REF] Meyer | Direct Imaging of Lattice Atoms and Topological Defects in Graphene Membranes[END_REF][START_REF] Kurasch | Atom-by-Atom Observation of Grain Boundary Migration in Graphene[END_REF]. Associated to theoretical developments [START_REF] Cockayne | Grain boundary loops in graphene[END_REF][START_REF] Kotakoski | Mechanical properties of polycrystalline graphene based on a realistic atomistic model[END_REF][START_REF] Cockayne | Graphing and grafting graphene: Classifying finite topological defects[END_REF] and simulations [START_REF] Zhuang | Evolution of domains and grain boundaries in graphene: A kinetic Monte Carlo simulation[END_REF], it is now clear that this defect belongs to the family of topological defects conserving both the sp 2 hybridization character of the C-C bounds and also the number of C atoms par graphene unit area [START_REF] Terrones | The role of defects and doping in 2D graphene sheets and 1D nanoribbons[END_REF]. The basic units are elementary disclinations (rings of 5 or 7 atoms) which form 5|7 pair known as dislocation in order to minimize the elastic energy. The well known Stone-Wales (SW) defect is composed of two dislocations compare to the FD which has six of them. It must be noticed that among all the GB based on those dislocations, FD has the lowest formation energy per dislocation (1.2 eV) [START_REF] Cockayne | Grain boundary loops in graphene[END_REF] because of its nearly full strain relaxation. This explains its stability and its relative frequency of observation. Unfortunately, there is no known atomistic mechanism which could conduct to specific FD formation and simulations are required [START_REF] Zhuang | Evolution of domains and grain boundaries in graphene: A kinetic Monte Carlo simulation[END_REF][START_REF] Karoui | Nickel-Assisted Healing of Defective Graphene[END_REF].

In the following, we report Scanning Tunelling Microscopy and Spectroscopy (STM, STS) studies of a gold (Au) assisted two steps growth process that allows to produce selectively a high density of FD in the top Graphene Layer (GL) grown on 6H-SiC(0001). (Step 1) prepares the surface in order to have connected irregular small graphene islands presenting a high density of borders and stressed areas. We call it proto-graphene. (Step 2) conducts to : (i) extend laterally the previous graphene islands; (ii) form new GL below the first one and (iii) release elastic energy induces by irregular GB. This is completed by : (iv) the fundamental effect of Au which favors the formation of localized defects. (Step 1) and (step 2) drive together all the parameters which are crucial to obtain a high density of FD. This result is complemented by first-principles calculations which show that Au decreases significantly the FD formation energy. Moreover, we show by fine STS measurements and in depth analysis of FD electronic structure, that those GBL exhibit more localized states than previously reported. STS results are also mentioned concerning resonant states which arise around the Fermi energy E F , inside the phonon pseudo-gap [START_REF] Zhang | Giant phonon-induced conductance in scanning tunnelling spectroscopy of gate-tunable graphene[END_REF].

Methods

Sample preparation

Prior to graphene synthesis (step 1 & 2), the SiC(0001) single-crystals (10 × 5 × 0.5 mm -3 , C-face epi-ready, Si-Face optically polished) bought from Novasic SA were degassed under ultra-high vacuum (UHV) conditions by direct current heating for 6 hours at 700 • C before a 15 minute annealing at 850 • C in front of a Si evaporator to get rid of surface oxygen. During (step 1 & 2)'s annealing performed at high temperature, the pressure stays lower than 10 -8 mbar. After annealing, we stopped abruptly the heating power and the temperature decreased within a one minute characteristic time below 300 • C.

Temperatures are measured by a pyrometer in the 1.45-1.80 µm spectral bandwidth with a 0.9 emissivity. The sample is maintained laterally by two tantalum stripes on the sample holder and only 1/3 of the sample area is covered by graphene after synthesis. Gold was deposited using an electron beam evaporator EFM 3 (Focus GmbH) at a rate of 1.4 10 14 Au /cm 2 /min, calibrated by Rutherford back scattering.

STM/STS measurements

Except STM pictures reported Fig. 1(a,d) acquired at room temperature (RT), our STM/STS measurements were performed at 4.6 K using a Scienta Omicron Low Temperature STM running on liquid helium. STS spectra were recorded through lockin detection at frequencies around 700-800 Hz and with a peakto-peak modulation of 24 mV for the large energy scale spectra and 6 mV for the small energy scale spectra to reduce the broadening of the peaks. Prior to measurements on graphene, tungsten tips were systematically calibrated on Au(111) until the Shockley surface state is clearly measured in the STS spectra.

First-principles calculations

To investigate the formation energy of the flower defect in presence of Au atoms, we performed first-principles calculations based on density functional theory. We used the Quantum Espresso [START_REF] Giannozzi | QUANTUM ESPRESSO: A modular and opensource software project for quantum simulations of materials[END_REF] code within the projector-augmented wave (PAW) method [START_REF] Blöchl | Projector augmented-wave method[END_REF]. The generalized gradient approximation [START_REF] Perdew | Generalized gradient approximation made simple[END_REF] was employed for all calculations. Integrations over the Brillouin zone are based on a 3×3×1 Monkhorst-Pack threedimensional grid for 162 atom cells. The size of the supercell in the c direction was set to 15 Å to avoid the interaction between neighboring defects. Calculations were performed at zero pressure, i.e., the relaxation of the atoms and the shape of the simulation cell are considered using the conjugate gradient minimization scheme. The initial lattice parameter is equal to 2.45 Å and is allowed to change during the simulations. The atomic positions were relaxed until the magnitude of the forces on all the atoms was smaller than 1.10 -5 Ha/Bohr. Description of the van der Waals dispersive forces has been accounted for via the D2 dispersion correction of Grimme [START_REF] Perdew | Generalized gradient approximation made simple[END_REF]. No SiC substrate was included in the DFT calculations insofar as our investigation has sought to highlight the intrinsic role played by Au in flower defect formation. In this context, DFT calculations were performed with various amounts of simulated deposited Au atoms ranging from 1 to 12 isolated atoms and also a 25-atom Au cluster. Moreover, the adsorption energy, E ads , is defined as :

E ads = E Au/substrate -E substrate -E Au , (1)
where E Au/substrate is the total energy of carbon substrate (graphene or FD) with the Au adatom attached, E substrate is the total energy of the pristine graphene or the FD layer, and E Au the total energy of an isolated Au atom. The more negative E ads is, the more strongly the atom of Au adheres to the carbon substrate.

Results and Discussion

3.1. Gold assisted flower defects synthesis : a two step process studied by scanning tunnelling microscopy In order obtain a large amount of FD, we improved usual process where rotationally faulted Few Layer Graphene (FLG) is produced by silicon (Si) sublimation from the substrate annealed between 1 100 -1 300 • C [START_REF] Mishra | Graphene growth on silicon carbide: A review[END_REF][START_REF] Hass | Why Multilayer Graphene on 4H-SiC(000-1) Behaves Like a Single Sheet of Graphene[END_REF]. Before our graphene synthesis, the SiC(0001) sample was cleaned in UHV as described in the Methods 2.1 section. Then, after this cleaning preparation, we proceeded in two steps. First step (step 1 in the following), around 14 10 14 Au /cm 2 , i.e. one monolayer (ML) of gold, is deposited onto the clean SiC substrate at RT (forming three-dimensional islands, not shown) and the sample is then annealed five minutes at an intermediate temperature of 1 050 • C (see Fig. 1(a)), the lowest temperature needed to synthesize graphene [START_REF] Forbeaux | High-temperature graphitization of the 6H-SiC (0001) face[END_REF]. At this point, the graphenization is not complete and one can see trenches between domains which can be seen in the line profile of Fig. 1(b). Those trenches disappear during the step 2 graphene synthesis and are the source of GB [START_REF] Tiberj | Multiscale investigation of graphene layers on 6H-SiC(000-1)[END_REF][START_REF] Biró | Grain boundaries in graphene grown by chemical vapor deposition[END_REF].

Second step (step 2 in the following), around one ML of Au is deposited at RT once more. This second Au ML follows also a Volmer-Weber (VW) growth mode on graphene at RT [START_REF] Liu | Slow Gold Adatom Diffusion on Graphene: Effect of Silicon Dioxide and Hexagonal Boron Nitride Substrates[END_REF]42]. Then, the sample is annealed at three increasing temperatures : 1 100 • C, 1 150 • C and 1 200 • C, 5 minutes each. Fig. 1(c) shows the surface after (step 2) and exhibits three graphene domains separated by rotational GB. Note that the bulk Au melting temperature is 1 064 • C (even lower for nanoparticles of 1-2 nm) and we can suppose that Au atoms are completely removed from the surface after (step 2) because of evaporation, or diffusion into the bulk [START_REF] Li | From the Au nano-clusters to the nanoparticles on 4H-SiC[END_REF]. We get FD (circled in red) with a density n around 7 • 10 11 cm -2 . As a FD is composed of 24 atoms, we can also say that ∼ 0.5 % of the atoms are part of FD. The defect-defect first neighbor mean distance is equal to 5.4 ± 2.3 nm (the minimum distance is the size of an isolated FD, i.e. around 2 nm). This result is consistent with a Poisson distribution where the nearest neighbor mean distance is 1/(2 √ n) = 6 nm. This shows that FD positions are random. In Fig. 1(c) one can see that larger GBL such as double FD (circled in green) are very scarce with a density around 10 11 cm -2 . Single FD are by far prevailing. This result is consistent with the fact that bigger GBL are less energetically favored than FD [START_REF] Cockayne | Grain boundary loops in graphene[END_REF]. Similar double FD have already been observed and some of them (with a non-conserved number of atoms) have been called conjoined-twin defect [START_REF] Cui | Structural Evolution of Flower Defects and Effects on the Electronic Structures of Epitaxial Graphene[END_REF]. The three graphene domains exhibit Moiré Patterns (MP) with different periodicity (mainly related to the twist angle between the two first graphene layers) and the amounts of FD are nearly equal on each one. On one side, this indicates a homogeneous distribution of FD all over the surface independently of the relative orientation of the underlying GL. On the other side, this shows that FD are not surrounded by the same atomic environment, and consequently, could have different mechanical and electronic properties. Effectively: i) FD belonging to a same grain are more or less in interaction laterally with each other's (and the surrounding GB) and these interactions could induce inhomogeneous stresses, which have a great importance concerning local mechanical properties [START_REF] Zhang | Mechanical properties of bilayer graphene with twist and grain boundaries[END_REF]; ii) FD seem to be randomly distributed, thus their electronic properties should also depend on their positions relatively to the underlying layer. A point which is discussed below in relation with local electronic spectroscopy.

Despite the fact that after this synthesis, either by STM or Auger electron spectroscopy we did not find any trace of Au, we cannot exclude the formation of gold carbides or silicides during the high temperature graphene synthesis. Effectively, AuC complexes have already been observed by TEM [START_REF] Westenfelder | Bottom-up formation of robust gold carbide[END_REF] and previous calculations [START_REF] Stolbov | Gold-doped graphene: A highly stable and active electrocatalysts for the oxygen reduction reaction[END_REF] have shown that Au-C binding energy could be around 0.5 eV higher than the cohesive energy of bulk Au (3.81 eV). Moreover, we can suppose that during annealing around 1 100 • C, as deposited Au form small liquid droplets before evaporation and constitute temporary sources for Au atoms/clusters diffusion on the surface, which could also form AuSi complexes.

Discussion about the importance of each step

Starting from the cleaning procedure, all the parameters in this double step process seem to be crucial. For example, we carried out (steps 1 & 2) without Au deposition and ended up with no FD. This means that Au (especially when deposited during (step 2)) plays a key role in the formation of the FD as catalyst. But proto-graphene is also essential.

Synthesis without proto-graphene

If (step 1) is not carried out, i.e. only one Au ML is deposited on the clean SiC substrate and the sample is then heated gradually until 1 200 • C, it exhibits no FD as shown on Fig. 1(d). Effectively, Au melting temperature being lower than 1 100 • C, we can assume that most of the Au evaporates from the surface before it can create defects. Thus, this case is similar to the usual FLG synthesis without Au and our results presented in Fig. 1(d) are comparable to previously obtained results [START_REF] Tison | Grain Boundaries in Graphene on SiC[END_REF][START_REF] Varchon | Rotational disorder in few-layer graphene films on 6 H -Si C ( 000 -1 ) : A scanning tunneling microscopy study[END_REF]. If we compare Fig. s 1(c) and (d), we remark that without (step 1) the final typical domain size is around five times smaller and the sample exhibits a high density of GB. This is also explained by the proto-graphene which, once created, could reduce the area available for new graphene nucleation sites during the (step 2) synthesis performed at higher temperature [START_REF] Norimatsu | Growth of graphene from SiC{0001} surfaces and its mechanisms[END_REF][START_REF] Biedermann | Insights into few-layer epitaxial graphene growth on 4H-SiC(000-1) substrates from STM studies[END_REF] and so, could increase the final grain size by limiting the proliferation of graphene flake boundaries.

Proto-graphene as a template for gold anchoring

The first very important point to notice is that after (step 1) graphene is not flat. As shown in Fig. 1(a,b), (step 1) is not sufficient to create extended graphene domains and the surface is rather similar to graphene obtained on various SiC reconstructions [START_REF] Hiebel | Graphenesubstrate interaction on 6 H -SiC ( 000-1 ) : A scanning tunneling microscopy study[END_REF]. The large atomic roughness in Fig. 1(b) indicates the presence of small islands or clusters of undefined species (Au, C, Si or their combination). We think that those areas are one way toward FD synthesis, as they induce locally important strain in the graphene, that increases the elastic energy. During (step 2), this energy will be released locally and consequently may promote a reorganization favorable to the FD. Note also that after (step 1), graphene island borders are connected to the SiC substrate which induces also a residual stress inside islands [START_REF] Tiberj | Multiscale investigation of graphene layers on 6H-SiC(000-1)[END_REF]. So, we argue that there are two main places where (step 2)'s Au would catalyze defects more easily : the small strained area in the graphene flakes and the graphene borders.

Gold as catalyst for the flower defects formation

Au on graphene at RT follows a VW growth mode but the Au island density depends strongly on the graphene defect density such as vacancies, graphene borders and GB [42,[START_REF] Pulido | Theoretical investigation of gold clusters supported on graphene sheets[END_REF]. All those defects are nucleation areas for island growth [START_REF] Irawan | Size-dependent morphology of gold clusters grown on nanostructured graphite[END_REF]. This means that proto-graphene, which exhibits a very high defect density, acts as a perfect template in order to obtain a high density of Au islands during (step 2). We think that it is this association which is the driving force for FD formation. We argue that Au islands of nanometer size trapped in the proto-graphene defects modify locally the formation/relaxation of graphene and the healing processes during (step 2). One consequence is the generation of small domains isolated from the rest by GBL such as FD or conjoined-twin defects. Containment of small areas within the rest of the environment has already been observed by TEM [START_REF] Cresti | Growth, charge and thermal transport of flowered graphene[END_REF] and a bulge nucleation mechanism has been proposed which has great similarities with our hypothesis. This could be confirmed by molecular dynamic simulations of GB migration [START_REF] Kurasch | Atom-by-Atom Observation of Grain Boundary Migration in Graphene[END_REF][START_REF] Zhuang | Evolution of domains and grain boundaries in graphene: A kinetic Monte Carlo simulation[END_REF][START_REF] Annevelink | Grain boundary structure and migration in graphene via the displacement shift complete lattice[END_REF] in presence of Au islands.

Comparisons with bismuth and platinum

(Step 2) is carried out at high temperature (around 1 150 • C) and the stability of Au islands during this step is the key point to increase the FD density. If islands evaporate before the carbon disclinations interact with each other under or at the island edges in order to form GBL, there will be no increase of FD density and no gain relatively to a situation without Au. On the contrary, if Au islands do not evaporate (as observed in the first two annealing at 1 100 • C and 1 150 • C, not shown), there could be defects under these islands, but they will obviously be invisible to STM. Since the Au melting temperature is lower than the second graphene synthesis temperature, it is the Au island size, and therefore their lifetime before total evaporation (which is related to the sublimation rate at this temperature) that controls two things. On the one hand, getting FD, and, on the other hand, removing all the residual Au islands or atoms which could modified the intrinsic flowered-graphene properties. An indirect proof of the importance of the metal melting temperature and the quantity of deposited atoms in (step 2) is to compare our results with those obtained with two other elements which have very different bulk melting temperatures (BMT) : platinum (Pt) and bismuth (Bi) with respective BMT of 1 380 • C and 271 • C, i.e. respectively above and below the (step 2) synthesis temperature. We used Pt instead of Au in (step 1 & 2) and, excepted a lot of residual big Pt islands, we didn't obtain any observable FD. Nevertheless, we cannot exclude the possibility that FD are located below those islands. Concerning Bi, we recall below that previous experiments [START_REF] Hu | Bismuth mediated defect engineering of epitaxial graphene on SiC[END_REF] realized on the Si-rich face have also generated a great flower-like density, around 10 12 cm -2 , but associated with a nearly equal amount of undefined point defects. For Bi on SiC(0001) [START_REF] Hu | Bismuth mediated defect engineering of epitaxial graphene on SiC[END_REF], (step 1) was not performed and (step 2) was repeated several times with two major differences compared to our experiments : a larger Bi thickness and a higher temperature, 1 350 • C. The consequence was a low amount of potential sites for the nucleation of Bi islands which could have catalyzed FD formation. Associated with its very low BMT (and so a very high sublimation rate at those temperatures), this explains why (step 2) has to be repeated several times before reaching a significant density of FD. Moreover, it must be pointed out that the graphene growth on the Si-rich surface is intrinsically not a good candidate to obtain selectively a high density of FD. The growth modes of graphene on the Si-rich and C-rich faces are very different. On the former, it is a rolling-carpet mechanism starting at the SiC step edges, while on the latter, it is a nucleation growth mode from the SiC terraces. It follows that on the Si-rich face, the first successive graphene planes (included the buffer layer) are in epitaxial relationship with the substrate and have very few grain boundaries, whereas on the C-rich face, the graphene planes are rotated relatively to each other, thus forming both MP and having a high density of grain boundaries constituted mainly by disclinations and vacancies. Since flower defects are obtained from the organized clustering of disclinations, it is clear that the more disclinations there are, the greater the density of flower defects will be. However, this is directly related to the density of point defects present during graphene synthesis. It is therefore expected to be more "difficult" to obtain a high density of flower defects on the Si side compared to the C side. This is indeed what is observed with bismuth assisted FD formation on the Si-rich face [START_REF] Hu | Bismuth mediated defect engineering of epitaxial graphene on SiC[END_REF] or the necessity to synthetize the graphene at high temperature [START_REF] Cui | Structural Evolution of Flower Defects and Effects on the Electronic Structures of Epitaxial Graphene[END_REF] in order to obtain a high density of defects, among which a certain amount of FD.

First-principles calculation of FD formation energy

Once we have understood that after (step 1) a great amount of potential FD sites (among other extended defects) have been created along graphene flake borders and stressed regions, we theoretically investigate the role of Au during FD formation. So we calculate the FD formation energy, E f , by first-principles calculations (see Methods 2.3). We define E f as

E f = E(FD + n.Au) -E(GR + n.Au) (2)
where the first right-hand side term is the total energy of the FD in contact with n Au atoms, and the second one is the total energy of the corresponding pristine graphene structure also with n Au. To emphasize the catalytic role played by gold to form FD, E f is calculated for n Au atoms (n =1 to 12) located in direct contact with the defects. More precisely, our calculations show that the most stable position for one Au atom is in bridge between the pentagonal and heptagonal rings. Therefore, different configurations will be investigated further when the n Au atoms are close or far from each other on these specific sites. First of all, it can be seen that the formation energy without Au atom is equal to 7.20 eV which is in agreement with previous results [START_REF] Cockayne | Grain boundary loops in graphene[END_REF][START_REF] Kurasch | Atom-by-Atom Observation of Grain Boundary Migration in Graphene[END_REF]. Interestingly, our calculations show clearly that E f decreases significantly in presence of Au atoms to reach 3.05 eV for n = 12. As seen in Fig. 2, the decrease is not continuous. Indeed, it depends on the way Au atoms interact locally with the topological defects present in the graphene.

To go further, a flake of 25 Au atoms fully covering the FD is considered. They are forming a closed-packed structure which can be assimilated to the contact zone characterizing the interaction of a (111) facet of a nanoparticle with the FD. By doing so, the decrease in E f is even more pronounced and achieves a value of about 2.5 eV. Consequently, those results clearly show that Au promotes formation of FD. This catalytic role of Au is achieved through its strong interaction with the topological defects present in graphene. To highlight this mechanism, the adsorption energy (E ads ) of an Au atom on a SW defect is calculated and compared with pristine graphene (see Methods 2.3). The adsorption of Au atoms on graphene has been studied on several graphene sites, including the highly symmetric sites (top, bridge and hollow). According to our calculations, the most stable positon for the Au adatom is on top of a C atom for an adhesion energy of about -0.51 eV in line with data from the literature [START_REF] Chan | First-principles study of metal adatom adsorption on graphene[END_REF][START_REF] Nakada | Migration of adatom adsorption on graphene using DFT calculation[END_REF][START_REF] Manadé | Transition metal adatoms on graphene: A systematic density functional study[END_REF]. In the presence of the SW defect, E ads is equal to -2.51 eV revealing that the interaction of Au atoms with topological defects is very strong which suggests that Au atoms can play a crucial role for the formation of FD.

It is interesting to note that similar calculations have shown that the energy barrier for the elimination of SW defects (around 5 eV) [START_REF] Li | Defect energies of graphite: Densityfunctional calculations[END_REF] can be drastically decreased by adsorbed transition metal atoms [START_REF] Charlier | Catalytically Assisted Tip Growth Mechanism for Single-Wall Carbon Nanotubes[END_REF][START_REF] Wang | Metal-promoted restoration of defective graphene[END_REF]. In the present work, we were also able to highlight this effect. We performed the same kind of study done for FD with a SW defect. In a similar way, we observe a strong reduction of the formation energy in the presence of Au atoms. Indeed, the formation energy of a SW defect is 5.3 eV according to our calculations. In this particular case, the Au atom occupies the bridge position and tends to strongly decrease the defect formation energy by about 25% to reach 3.92 eV. Starting from 3 atoms, the E f value tends to stabilize around 3 eV. Note that once 5|7 pairs or SW defects are formed, by an unknown out of equilibrium atomic process during the graphene formation, they are stable in the temperature range that we use. So, our experimental and theoretical results show that Au, acting as a catalyst, decreases FD formation energy.

Finally, we can say that two main mechanisms act to form a high density of FD. On one hand, Au (and eventually Bi, Pt and other species) catalyzes FD and flower-like defects because it decreases the SW and loops formation energy. And, on the other hand, (step 1) increases the number of local stressed areas induced by trenches and graphene defects in the protographene, which thus prepares a lot of potential sites for Au anchoring during (step-2) and so favoring the formation of point- The topography of a FD is reported in more details in Fig. 3(a) and its appearance is similar to that previously reported [START_REF] Cockayne | Grain boundary loops in graphene[END_REF][START_REF] Hu | Bismuth mediated defect engineering of epitaxial graphene on SiC[END_REF] (an atomic model is superimposed to the experimental image). The defect appears as a grey center located on the seven central hexagons, surrounded by a white crown located on the joined 5|7 pairs, prolonged by six lobes emerging from the heptagons. Far from the defect (bottom left part), one can see the honeycomb lattice of graphene and closer to it one can see the (

√ 3 × √ 3)R30
• electronic pattern due to electrons scattering by the defect [START_REF] Rutter | Scattering and Interference in Epitaxial Graphene[END_REF]. Note that all apparent heights (and so the grey scale from 0 to 1.1 Å) are not related to atomic corrugation but mostly to local variations of the electronic densities. Fig. 3(b) shows a STM image of five FD belonging to the same graphene domain exhibiting a unique moiré pattern (MP). Whatever the MP, we never noticed a clear crystallographic relationship between FD location and the apparent moiré periodicity. It means that, on one side, the underlying GL plays no role in the FD location, and, on the other side, that the seven rotated central hexagons are not exactly above the same underlying carbon stacking. Fig. 3(c) shows three differential conductance (dI/dV) spectra taken on three of the FD in Fig. 3

(b).

There are two broads peaks around -0.9 eV and 0.8 eV and a series of fine peaks at positive energies between 0.1-0.5 eV, just above the pseudo-gap [START_REF] Zhang | Giant phonon-induced conductance in scanning tunnelling spectroscopy of gate-tunable graphene[END_REF] centered at E F (see also Fig. 4(e)). These features in the eV range are consistent with previous reports [START_REF] Zhao | Local Atomic and Electronic Structure of Boron Chemical Doping in Monolayer Graphene[END_REF][START_REF] Cockayne | Grain boundary loops in graphene[END_REF][START_REF] Yan | Electronic structures of graphene layers on a metal foil: The effect of atomic-scale defects[END_REF][START_REF] Cui | Structural Evolution of Flower Defects and Effects on the Electronic Structures of Epitaxial Graphene[END_REF][START_REF] Hu | Bismuth mediated defect engineering of epitaxial graphene on SiC[END_REF] but our measurements display a better resolved fine structure. More precisely, FD electronic fingerprint is usually observed as a broad resonant peak in the graphene empty states located around 300 to 400 meV above the Dirac Point (DP). This localized resonance is characteristic of isolated SW defects [START_REF] Amara | Scanning tunneling microscopy fingerprints of point defects in graphene: A theoretical prediction[END_REF][START_REF] Lherbier | Two-Dimensional Graphene with Structural Defects: Elastic Mean Free Path, Minimum Conductivity, and Anderson Transition[END_REF] and similar to van Hove singularities which emerge in one-dimensional ordered GB [START_REF] Tison | Grain Boundaries in Graphene on SiC[END_REF][START_REF] Yazyev | Electronic transport in polycrystalline graphene[END_REF][START_REF] Luican-Mayer | Localized electronic states at grain boundaries on the surface of graphene and graphite[END_REF]. Note that FD which are within the same graphene grain, as in Fig. 3(b), exhibit very similar spectra (this has been systematically observed on several domains) : same peaks at the same energies with slightly different intensities. The number and energy position of these fine FD peaks centered around 0.25 eV in Fig. 3(c) strongly depend on the scanned graphene grain which suggests that these states are sensitive to the surrounding atomic arrangement (see also spectra reported in Fig. 3(d,e) obtained on two different grains, but with a lower resolution), but they are always in the empty states. Correlatively, the mapping of those states is very sensitive to the orientation of underlying GL. Those two observations are a strong indication that FD may interact not only with their lateral atomic environment, but also they couple with the underlying surface. This coupling could explain the multiple peaks structure observed between 0.1-0.5 eV and not predicted by first-principles calculations [START_REF] Cockayne | Grain boundary loops in graphene[END_REF] but presenting great similarities with previous STS measurements performed on flat regular GB on SiC(0001) [START_REF] Tison | Grain Boundaries in Graphene on SiC[END_REF]. Despite the large energy range we have experimentally explored ±1.5 eV, there is no localized state in the filled states.

Mapping of low energy states

Zooming the low energy range, i.e. few tens of meV, it is intriguing to see that spectra taken on the different lobes (heptagons) of a FD, see Fig. 4(a), have several clear peaks inside the gap and rather close to E F , see Fig. 4(e). We recall that most of the effective electron tunelling in graphene is inelastic electron tunelling mediated by phonons [START_REF] Červenka | Local enhancement of inelastic tunnelling in epitaxial graphene on SiC[END_REF] and that a typical STS spectrum on pristine graphene exhibits a gap-like feature (see also Fig. 3(c)) between -64 mV and +64 mV (which we confirmed using d 2 I/dV 2 measurements). Through an extended study of several defects at different positions on the sample and with different tips we always noticed that diametrically opposed lobes have very similar spectra. Differential conductance maps obtained from grid spectroscopy at different energies are reported in Fig. 4(b-d). That shows that opposing lobes "light up" at the same energy. We also notice that two or four lobes "light up" at the same time but never all six of them. This is surprising in the sense that it breaks the obvious six-fold symmetry that one could expect from the defect. Two possibilities are open. On one hand, the surrounding electronic modulation (induced by defects proximity, anisotropic strain, etc.) could be coupled to those electronic states and thus breaks the sixfold symmetry. On the other hand, FD belonging to the same grain are surrounded by the same MP induced by the twist angle of the graphene bilayer. It follows that the periodic transition from AB to AA local stackings of the graphene bilayer are locally disturbed by each FD. Thus, because of the FD ran- domness location, one should expect variable electronic states from FD to FD. For example, if a flower is in an AA stacking bilayer, its symmetry is not broken, and we should observe a 6-fold symmetry. In case of a Bernal-stacked bilayer we should observe a 3-fold symmetry, as already suggested [START_REF] Cockayne | Grain boundary loops in graphene[END_REF]. Note that a similar symmetry breaking processes induced by a defect in a graphene bilayer has previously been invoked in order to explain the shape of FD [START_REF] Simon | Symmetry of standing waves generated by a point defect in epitaxial graphene[END_REF]. Due to randomness of FD positions in a same grain (and also the same MP), they have not the same underlying stacking (except for the AA or AB stacking which are rather rare), which also breaks their symmetry. This second possibility is the more likely of the two because it is coherent with the spectroscopy done at high energy where all FD residing on the same MP exhibit the same spectrum whatever their proximity with other defects. We can not explain the physical origin of those in-gap states (these states have already been measured in a very different atomic configurations, i.e. along graphene nanoribbons on Au(111) [START_REF] Tao | Spatially resolving edge states of chiral graphene nanoribbons[END_REF] and along ridges on SiC(0001) [START_REF] Ridene | STM/STS investigation of edge structure in epitaxial graphene[END_REF])), but the FD special topology coupled to the interaction with the underlying graphene could induce new states due to electronic confinement. Recent calculations on circular quantum dots in twisted bilayer graphene are certainly a hint to understand those states [START_REF] Mirzakhani | Circular quantum dots in twisted bilayer graphene[END_REF].

Conclusion

In summary, scanning tunelling microscopy and spectroscopy studies of flower defect formation catalyzed by gold on fewlayer graphene on SiC(0001) have been presented. A very high density of flower defects is obtained thanks to a two-steps process. A proto-graphene layer creates a template for anchoring gold clusters which promotes the formation of those quasi-point like topological defects during the second step. First-principles calculations provide clear evidence for a drastic decrease of their formation energy with gold. These flowers exhibit localized electronic states all over the defect at high energy, and interestingly low energy states localized asymmetrically on the heptagons breaking the apparent flower defect 6-fold symmetry. The complex formation of those defects during the graphene synthesis on SiC could be studied by molecular dynamic simulations. The unknown in-gap states deserve future experiments and theoretical developments.

Figure 1 :

 1 Figure 1: (a) STM image of proto-graphene on SiC(0001) synthesized after (step 1), i.e. : one Au monolayer deposition at room temperature and a 5 minute synthesis at 1 050 • C (100×74 nm 2 ). (b) Topography along the red line showing the trenches between domains. (c) STM image of three domains of few layer graphene obtained after (step 1) followed by (step 2), i.e. : a second Au deposition and three successive 5 minute synthesis at 1 100 • C, 1 150 • C and 1 200 • C. On each of the domains, one have circled in red the flower defects. Bigger grain boundary loops are circled in green (100×100 nm 2 ).(d) STM image of several domains of few layer graphene obtained without (step 1), i.e. : one Au monolayer deposition at room temperature and a 15 minute direct synthesis at 1 200 • C (100×100 nm 2). For all the images V=1 V, I=50 pA.

Figure 2 :

 2 Figure 2: Flower defect formation energy as a function of the number of gold atoms. Insets : relaxed atomic positions of a flower defect without (left) and with 1, 8 and 25 Au atoms (left). Carbon atoms are in black and Au atoms are in yellow. Pentagonal and heptagonal rings are filled in red and blue, respectively.

Figure 3 :

 3 Figure 3: (a) Scanning tunelling microscopy image of a flower defect with the qualitative atomic model superimposed over it (4×4 nm 2 , V=1 V, I=100 pA).(b) Topographic image of 5 other flower defects (15×15 nm 2 , V=220 mV, I= 1 nA).(c) dI/dV spectra taken on three of the defects in (b). Offsets have been added for clarity. (d, e) dI/dV spectra taken on FD belonging to two other grains.

Figure 4 :

 4 Figure 4: (a) Topographic image of another flower defect (3.5×3.5 nm 2 , V=500 mV, I=400 pA) and differential conductance intensity maps taken from grid spectroscopy at (b) 63 mV (c) 4 mV and (d) -20 mV on the same defect. (e) dI/dV spectra taken on (a) with a set point at 500 mV and 400 pA. The black curve is taken on the graphene (white '+' in (a)) and shows the phonon gap. The red and blue curves are taken on two different lobes of the defect (red and blue '+'s in (a)) and show both the phonon gap and several peaks inside the gap.

Acknowledgments

The authors received no specific funding for this work.