Guillaume Fertin
email: guillaume.fertin@univ-nantes.fr

Julien Fradin
email: julien.fradin@univ-nantes.fr

Géraldine Jean
email: geraldine.jean@univ-nantes.fr

The Maximum Colorful Arborescence Problem: How (Computationally) Hard can it be ? $

Keywords: Complexity, FPT algorithms, approximation algorithms, Maximum colorful arborescence, tandem mass spectometry

 in the context of de novo identification of metabolites by tandem mass spectrometry. However, a thorough analysis of the initial motivation shows that the formal definition of MCS should be amended, since the input graph G actually possesses extra properties, which have been unexploited so far. This leads us to describe in this paper a more precise model that we call Maximum Colorful Arborescence (MCA), which we extensively study in terms of algorithmic complexity. In particular, we show that exploiting the implied Color Hierarchy Graph of the input graph G can lead to exact polynomial algorithms and approximation algorithms. We also develop Fixed-Parameter Tractable (FPT) algorithms for the problem parameterized by the "dual parameter" C , defined as the minimum number of vertices of G which are not kept in the solution.

Introduction

Metabolites are small molecules that are involved in cellular reactions, most of them remaining unknown to this date [START_REF] Fernie | Metabolite profiling: from diagnostics to systems biology[END_REF]. Consequently, identifying molecular structures of metabolites is a key problem in biology [START_REF] Last | Innovations: Towards the plant metabolome and beyond[END_REF][START_REF] Neumann | Computational mass spectrometry for metabolomics: identification of metabolites and small molecules[END_REF], and in particular in drug design [START_REF] Li | Drug discovery and natural products: end of an era or an endless frontier?[END_REF][START_REF] Schmidt | Revisiting the ancient concept of botanical therapeutics[END_REF]. Tandem mass spectrometry is one of the most commonly used technologies to achieve this goal. In a tandem mass spectrometry experiment, a metabolite is fragmented into smaller molecules. The mass spectrometer then outputs a fragmentation spectrum that consists of a series of peaks where, ideally, each peak corresponds to the mass of one of the generated fragments. If we are able to "explain" the spectrum by finding the molecule which corresponds to each peak it contains, then the input metabolite can in turn be infered. Such an identification can be achieved by comparison with some reference database(s) [START_REF] Oberacher | On the inter-instrument and inter-laboratory transferability of a tandem mass spectral reference library: 1. Results of an Austrian multicenter study[END_REF]; however, the databases at hand are largely incomplete [START_REF] Fernie | Metabolite profiling: from diagnostics to systems biology[END_REF][START_REF] Tautenhahn | An accelerated workflow for untargeted metabolomics using the METLIN database[END_REF][START_REF] Wishart | HMDB: a knowledgebase for the human metabolome[END_REF]. This is why de novo interpretation of the fragments, directly from the spectra, is a promising alternative.

Determining the chemical formula of metabolites is generally used as a first step in the identification of their molecular structure. In [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF], Böcker et al. initiated such study, where the problem of de novo identifying the chemical formulas of metabolites from tandem mass spectrometry spectra was formally modeled by the Maximum Colorful Subtree (or MCS) problem. Let µ be an unknown metabolite and s µ a tandem mass spectrum of µ. Intuitively, a solution of MCS represents the best possible "fragmentation scenario", called a fragmentation tree, of µ. Böcker et al. showed that computing the fragmentation tree of µ allows to determine the chemical formula of the studied metabolite [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF]. Further studies then showed how to use these fragmentation trees in order to determine the molecular structures of these metabolites [START_REF] Rasche | Computing fragmentation trees from tandem mass spectrometry data[END_REF][START_REF] Rasche | Identifying the unknowns by aligning fragmentation trees[END_REF][START_REF] Hufsky | Fast alignment of fragmentation trees[END_REF][START_REF] Dührkop | Molecular formula identification using isotope pattern analysis and calculation of fragmentation trees[END_REF][START_REF] Böcker | Fragmentation trees reloaded[END_REF].

In the following, we describe the main ideas behind MCS. First, for each peak p in s µ representing a mass, a set of chemical formulas is generated such that the mass of any molecule having one of those chemical formulas lies in the same range as p. A directed acyclic graph (DAG) G = (V, A) is then created as follows: every node v ∈ V represents a chemical formula; two nodes u and v are linked by an arc (u, v) if one molecule, whose chemical formula is represented by vertex v, is possibly the result of the fragmentation of another molecule whose chemical formula is represented by vertex u; each vertex possesses a color corresponding to its mass (or better said, its mass range). A weight function w : A → R is also assigned to the arcs of G. Informally, weights correspond to some degree of confidence concerning the fragmentation of a molecule into its sub-molecule; it is also important to note that in most applications, the weight function w is logarithmic, and thus arc weights in G may be negative. Note finally that in such a graph, there exists a unique vertex of indegree 0 (that can be seen as the "root" of G), whose color is also unique: this particular vertex represents one possible candidate chemical formula for metabolite µ. Now the MCS problem, introduced in [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF], is defined as follows: given a DAG G = (V, A), a set C of colors, a coloring function col : V → C and a weight function w : A → R, find a subtree T of G such that [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF] no two vertices of T carry the same color (we then say that T is colorful) and (2) T is of maximum weight (where the weight of T is the sum of the weights of the arcs it contains).

However, a finer-grained analysis shows that modeling the initial problem as the MCS problem does not completely reflect the precise structure of the input. First, it is easy to see that G is not any DAG: more precisely, as discussed above, it has a unique root r having indegree 0. Moreover, let us define H(G) as the directed graph that is built from G as follows: V (H(G)) is the set C of colors used to color V (G), and there is an arc from c to c in H(G) if there is an arc in G from a vertex of color c to a vertex of color c . Since vertices are colored according to the masses of the molecules they represent and since an arc (x, y) represents the fragmentation of a molecule of chemical formula x into a molecule of chemical formula y, there necessarily exists a partial order among colors, which implies that H(G) is necessarily a DAG too; therefore H(G) is called the Color Hierarchy Graph of G. Finally, by the nature of the initial problem, the output tree T must necessarily contain the root r. Thus, T is formally an arborescence, i.e., a directed graph T = (V T , A T ) with a designated root r such that there exists only one path from r to any node v ∈ V T . This leads us to reformulate the MCS problem into the following Maximum Colorful Arborescence (or MCA) problem, which better reflects the initial motivation.

Maximum Colorful Arborescence (MCA)

• Input: A DAG G = (V, A) rooted in some vertex r, a set C of colors, a coloring function col : V → C s.t. H(G) is a DAG and an arc weight function w : A → R.

• Output: A colorful arborescence T = (V T , A T ) rooted in r and of maximum weight w(T ) = a∈A T w(a).

We say that an optimization problem Q is FPT (for Fixed-Parameter Tractable) with respect to a given parameter k if it can be exactly solved in time O(f (k)•poly(|I|)) for some computable function f and any instance I of Q, i.e., if the exponential part of its complexity depends only on k. If k is small in practice, designing Fixed-Parameter Tractable algorithms is of interest since they are exact and possibly run in reasonable time, even for large inputs. For more details on the theory of fixed-parameter tractability, we refer the reader to [START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]. Now, because the definition of MCA is more accurate, it seems interesting to provide a detailed analysis of the computational complexity of the problem, as done in this paper. Indeed, studying MCA contributes to a better understanding of the initial biological problem. In particular, we will see that the fact that H is a DAG can be positively exploited in some situations. Moreover, since any instance of MCA is also an instance of MCS, any positive result (such as polynomial-time, approximation and FPT algorithms) for MCS also applies to MCAwith a time complexity and/or approximation ratio that may even be improved for MCA. Besides, a negative result for MCS does not necessarily imply the same result for MCA. In this paper, we study MCA under an algorithmic viewpoint: a first goal is to distinguish tractable instances from intractable ones; a second one is to provide new polynomial and FPT algorithms for the problem.

This paper, which is an extended version of [START_REF] Fertin | Algorithmic aspects of the maximum colorful arborescence problem[END_REF], is organized as follows. In Section 2, we introduce notations that will be used throughout the paper. We then show in Section 3 that MCA remains hard even when the input instances consist in very specific arborescences. In this extended version, we also propose approximation algorithms for such instances, that essentially take advantage of the fact that H is a DAG. Using this property of H, we describe in Section 4 a new range of instances that are polynomial-time solvable, and provide new FPT algorithms. Finally, in Section 5, we present FPT algorithms for MCA parameterized by parameter C , defined as the minimum number of vertices not present in the solution. In particular, we show in this extended version a new FPT algorithm whenever (1) G is a tree and (2) the arc weights are uniform.

Preliminaries

Notations. For any positive integer k, we use the notation [k] = {1, 2, . . . , k}. For any vertex-colored and arc-weighted DAG G = (V, A) given as input of MCA, we let n = |V | and m = |A|. Since the input DAG of MCA instances is rooted in a single vertex, we always denote by r the root of G. For any v ∈ V , N + (v) denotes the set of outneighbors of v (thus excluding v) and, for any

V ⊆ V , N + (V ) = v ∈V N + (v ) is the set of outneighbors of all v ∈ V (excluding V ). For any v ∈ V , d + (v) (resp. d -(v)) denotes the outdegree (resp. indegree) of v. Moreover, for all V ⊆ V and v ∈ V , G v [V ] denotes the induced DAG of G[V ] that is rooted in v.
When G is an arborescence, for any vertex v ∈ V we let f (v) be the father (i.e., the unique inneighbor) of v in G. For any subset V of V , col(V ) denotes the multiset of colors assigned to the vertices of V and col * (V ) its underlying set. We say that V is colorful when col(V ) = col * (V ) and that G is colorful when V (G) is itself colorful. For a vertex v ∈ V , we let d(r, v) denote the oriented distance from r to v in (the unweighted version of) G, that is the minimum number of arcs needed to reach v from r in G. The Color Hierarchy Graph of G is denoted by H(G) = (C, A C ) or, when clear from the context, simply H.

The problem MCA + denotes the restriction of MCA to DAGs with positive weights, whereas UMCA denotes the restriction of MCA + to instances having unit arc weights, i.e., w(a) = 1 for all a ∈ A. Note that the root r of G is a trivial solution to any instance which only contains negative arcs; therefore, there is no need to define a restriction of MCA to DAGs with only negative arc weights. The problem MCA-x is the restriction of MCA in which any color c ∈ C appears at most x times in col(V ). Finally, we can also constrain the input instances of MCA both on the weights and on the maximal number of occurrences of a color, and thus combine any the three abovementioned variants. In that case, the problem will be naturally denoted by combining the corresponding notations. For instance, the UMCA-x problem considers input DAGs with positive and uniform weights, and in which any color appears at most x times in G.

Note that although G, the solution arborescence T and the Color Hierarchy Graph H are by definition directed, in the rest of the paper we will often, for simplicity and when clear from the context, refer to the underlying undirected graph of some graph H (rather than H itself). For instance, when we talk about MCA "in trees", we actually mean that the underlying undirected graph of G is a tree. Two parameters will be of importance in the algorithmic study of MCA: C = n -|C| is the minimum number of vertices that are not part of the solution, and s is the minimum number of arcs that need to be removed from H in order to turn it into an arborescence.

Previous results. We summarize here known results about MCS, and also note that every result mentioned below concerning MCS also applies to MCA. Indeed, MCA being a particular case of MCS, any positive result for MCS also holds for MCA. Moreover, for all negative results below, the MCS instances that are built in the corresponding proofs turn out to be either MCA instances themselves, or can easily be transformed into such instances.

MCS is known to be NP-hard even when every arc weight is equal to 1 [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF], and it can be seen that the result also applies to UMCA. MCS is also APX-hard on binary trees [START_REF] Rauf | Finding maximum colorful subtrees in practice[END_REF][START_REF] Dondi | Complexity issues in vertex-colored graph pattern matching[END_REF], a result that also applies to UMCA-2. However, the problem is FPT parameterized by |C|, by a dynamic programming algorithm that runs in O * (3 |C| ) time and uses O * (2 |C| ) space [START_REF] Scott | Efficient algorithms for detecting signaling pathways in protein interaction networks[END_REF][START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF].

Theorem 1 from [START_REF] Rauf | Finding maximum colorful subtrees in practice[END_REF], which shows hardness results for MCS, is directly applicable to MCA-1, since the MCS instance constructed in the reduction turns out to be an MCA-1 instance. Besides, it can be slighlty modified, while preserving the results, into an MCA-2 instance in which G is a tree. Thus we derive from Theorem 1 in [START_REF] Rauf | Finding maximum colorful subtrees in practice[END_REF] the following results: MCA-1 and MCA-2 in trees both are W [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF]-hard when parameterized by the weight w of the solution ; MCA-1 is W [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF]-hard when parameterized by C = n -|C| ; unless P = NP, there is no polynomial-time approximation algorithm achieving a ratio of O(n 1 2 -) with > 0 for both MCA-1 and MCA-2 in trees. 1MCA has also been studied in [START_REF] Fertin | On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure[END_REF], under a parameterized complexity point of view. It has been proved that MCA is FPT in the number of vertices of indegree at least 2 in H and W [START_REF] Fernie | Metabolite profiling: from diagnostics to systems biology[END_REF]-hard parameterized by the treewitdh t H of H. An FPT algorithm in C + t H is also given.

Our results. The main results obtained in this paper are summarized in Tables 1 and2. They will be developed in the following sections.

MCA in Trees

In this section, we focus on MCA in the case where the input graph G is a tree, aiming at determining which tree structures lead to (in)tractable (resp. (in)approximable) results. We start with the following theorem, that applies to the general case of trees.

Theorem 1. For any δ < 1, UMCA in trees cannot be approximated within

Maximum Level Motif (MLM)

• Input: A rooted tree H = (V, E), a color set C, a leveled coloring function col : V → C.

• Output: A maximum cardinality subset V ⊆ V such that the induced subgraph H[V ] is connected and colorful.

Let I be any instance of MLM. We construct an instance I of MCA as follows:

graph G is built on V , and each edge in H is changed into an arc in G, between the same vertices, such that each arc is oriented from parent to child; clearly, G is a tree. We let w(a) = 1 for any arc, and we also apply the same coloring function col , given as input of MLM, to color the vertices of G. Since col is a leveled coloring function, the colors in C are partially ordered and therefore H is a DAG. Thus, I is a correct UMCA instance. We now show that there exists a solution V of cardinality at least k for MLM iff there exists a colorful arborescence T = (V T , A T ) such that w(T ) ≥ k -1 in G.

(⇒) Suppose there exists a solution V of MLM such that |V | ≥ k. Let T be the spanning arborescence of V in G, with V T = V . Trivially, T is colorful and of weight at least k -1. If r / ∈ V T , we search for a vertex x ∈ V T such that d(r, x) = min{d(r, u) : u ∈ V T }. Let V r,x (resp. A r,x ) be the set of vertices (resp. arcs) in the path from r to x in G. We construct a new arborescence T = (V T , A T ), with V T = V T ∪ V r,x and A T = A T ∪ A r,x . According to col , V r,x is colorful and each vertex in V r,x has a different color from any of the vertices in V T . Thus, V T is colorful.

(⇐) Suppose there exists a colorful arborescence T = (V T , A T ) of weight at least k -1 in G. Then, we choose V = V T . Trivially, V is colorful and |V | ≥ k.

Dondi et al. proved that, under the condition that NP ⊆ DTIME[2 poly log n ], MLM cannot be approximated within 2 log δ n , δ < 1, in polynomial time [START_REF] Dondi | Complexity issues in vertex-colored graph pattern matching[END_REF]. By linearity of the above reduction, we reach the same conclusion for UMCA in trees.

We just showed that UMCA is highly inapproximable in trees. However, an approximation algorithm for UMCA can be obtained in binary trees. Indeed, note that a path from the root to any other vertex is always colorful as H is a DAG. Since the eccentricity of the root in any such tree is at least log n , and since any solution for UMCA in trees has weight less then or equal to n -1, we obtain the following result.

Proposition 2. UMCA in binary trees can be approximated within ratio O( n log n ).

From Theorem 1, it seems natural to further restrict the structure of the input tree in order to draw the line between tractable and intractable cases. We begin by the particular case where G is a star, i.e., a tree with one internal vertex, say z, that is connected to all other vertices. In case the internal vertex of G is the root r, an optimal solution to MCA is obtained as follows: for every color c ∈ C, consider all arcs from r to a vertex of color c, and keep the one with maximum weight if it is positively weighted, or discard it otherwise. In case z = r, z is the unique outneighbor of r. Since r must belong to the solution, we proceed in two steps. First, consider the star G[V \ {r}] and apply the same strategy as before with z playing the role of r. We obtain a partial solution of positive total weight containing at least z. Second, we try to add the arc (r, z) to the partial solution. Note that the arc (r, z) can be positively or negatively weighted. Therefore, the final solution is obtained by adding the arc (r, z) to the partial solution if the total weight is still positive. Otherwise, it means that the arc (r, z) is too negatively weighted and the final solution is restricted to the vertex r. We then get the following easy result, which will prove useful in some of our FPT algorithms in Section 4. Proposition 3. MCA in stars is polynomial-solvable.

Superstars, defined as rooted trees of height 2, are a natural extension of stars. However, in that case the MCA problem turns out to be hard, as shown by the following result.

Theorem 4. UMCA-2 is APX-hard, even if G is a superstar.
Proof. The proof is by reduction from Max-2-SAT(3), which is known to be APXhard [START_REF] Ausiello | Complexity and approximation: Combinatorial optimization problems and their approximability properties[END_REF]. It can be seen as an extension of proof of Theorem 1 in [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF].

Max-2-SAT(3) • Input: A set X = {x 1 , x 2 . . . x p } of variables, a CNF-formula φ on a set of size-2 clauses C 1 , C 2 . . . C q built from
X, such that each variable occurs in at most 3 clauses.

• Output: A boolean assignment β : X → {true, false} that maximizes the number of satisfied clauses from φ.

Recall that f (v) denotes the unique inneighbor of any v ∈ V as G is a tree. For every j ∈ [q], let l j,1 and l j,2 be the two literals that appear in clause C j . The reduction is as follows: for any instance of Max-2-SAT(3), we create a directed superstar G = (V, A) that we can see as a three-leveled graph (see Figure 1). The root r is at level 1, two vertices v i and v i are created for every i ∈ [p] at level 2, and two vertices C j,1 , C j,2 are created for every j ∈ [q] at level 3. There exists an arc from r to every level-2 vertex. For all i ∈ [p] and j ∈ [q], there exists an arc from v i (resp.

v i ) to C j,1 if l j,1 = x i (resp. l j,1 = x i ) or from v i (resp. v i ) to C j,2 if l j,2 = x i (resp. l j,2 = x i ).
The intuition is that an arc (v i , C j, ) (resp. (v i , C j, )) appearing in an arborescence represents the situation where setting x i = true (resp. x i = false), modeled by vertex v i (resp. v i ), satisfies clause C j . The coloring function on V (G) is defined as follows: the root r is assigned a unique color; for all i ∈ [p], vertices v i and v i are assigned the same color c(v i ); for all j ∈ [q], vertices C j,1 and C j,2 are assigned the same color c(C j ). Clearly, each color occurs at most twice in G, and the coloring function is partially ordered because any two vertices having the same color lie at the same level. Finally, every arc in G is assigned a weight of 1.

We now show that there exists a boolean assignment β for X that satisfies at least k clauses in φ iff there exists a colorful arborescence T = (V T , A T ) of weight w(T ) ≥ p+k in G.

(⇒) Suppose there exists an assignment β for X that satisfies at least k clauses of φ. We define:

S T = {v i : i ∈ [p] s.t. x i = true in β} and S F = {v i : i ∈ [p] s.t. x i = false in β}
Then, we define:

r v 1 v 1 v 2 v 2 v 3 v 3 C1,1 C1,2 C2,1 C2,2 C3,1 C3,2 C4,1 C4,2 G Figure 1: Construction of an instance of UMCA-2 from the following Max-2-SAT(3) instance: φ = (x 1 ∨ x 2 ) ∧ (x 1 ∨ x 3 ) ∧ (x 2 ∨ x 3 ) ∧ (x 1 ∨ x 3 )
. By definition, all arc weights are equal to 1, and are not represented for clarity. The assignment x 1 = true, x 2 = false and x 3 = false satisfies φ and corresponds to the UMCA-2 solution T in G with bold red arcs.

V T ={r} ∪ S T ∪ S F ∪ {C j,1 : j ∈ [q] s.t. f (C j,1 ) ∈ (S T ∪ S F )} ∪ {C j,2 : j ∈ [q] s.t. f (C j,2 ) ∈ (S T ∪ S F ) and f (C j,1 ) / ∈ (S T ∪ S F )}
We denote by T the spanning arborescence of V T . By construction, there cannot exist j ∈ [q], h ∈ {1, 2} such that C j,h ∈ V T and f (C j,h ) / ∈ V T . Thus, T is connected. Moreover, since β satisfies at least k clauses, there exists at least k distinct vertices of type C j,h that belong to T , in addition to the p vertices in S T ∪ S F and the root r. Besides, T is necessarily colorful and w(T ) ≥ p + k.

(⇐) Suppose there exists a colorful arborescence T = (V T , A T ) of weight w(T ) ≥ p + k in G. If V T does not contain p vertices from level 2, then it is always possible to extend it to a set V T such that V T ⊆ V T , V T is colorful and contains p vertices from level 2. Let T be the spanning arborescence of V T . Note that since T is colorful, for any 1 ≤ i ≤ p, either v i or v i is in V T but not both. We now construct a truth assignment β that satisfies at least k clauses from φ:

for every i ∈ [p], if v i ∈ V T (resp. v i ∈ V T ) then we let x i = true (resp. x i = false) in β. We now claim that β satisfies at least k clauses from φ. Indeed, if a vertex C j,h , j ∈ [q] and h ∈ {1, 2} is in V T , then necessarily f (C j,h ) ∈ V T
and, by construction, C j is satisfied by β. Moreover, C j,1 and C j,2 cannot both belong to V T because T is colorful. Since T has weight w(T ) ≥ p + k, V T must contain at least k vertices from level 3, which means that β satisfies at least k clauses.

To conclude the proof, recall that k ≤ q since no more than q clauses can be satisfied. Note also that 2q ≤ 3p as every variable appears at most three times in φ, while every clause is of size 2. This gives us p ≥ 2q 3 ≥ 2k 3 and p + k ≥ 2k 3 + k ≥ 5k 3 . Thus, there exists an assignment β that satisfies at least k clauses of φ iff there exists a colorful arborescence T = (V T , A T ) of weight w(T ) ≥ 5k 3 in G. The linearity of the reduction combined with the APX-hardness of Max-2-SAT(3) shows APX-hardness of UMCA-2, even on superstars.

Although Theorem 4 suggests that no PTAS exists for UMCA-2 in superstars, we are able to provide in that case a constant ratio approximation algorithm, as described below.

Proposition 5. UMCA-2 is 2-approximable in superstars.

Proof. In the following, for any v ∈ V (resp. any V ⊆ V ), let col + (v) (resp. col + (V )) be the underlying set of col(N + (v)) (resp. col(N + (V ))). We first assume that the root r of the superstar G is also the center of G, i.e., that there does not exist any vertex v ∈ V such that d(r, v) > 2 -the case where r is not the center will be discussed later. If G is a superstar, we can see it as a three-leveled graph where the root r belongs to the first level, V 2 = N + (r) belongs to the second level, and

V 3 = N + (V 2 )
belongs to the third level. For any color c ∈ C, let V c = {v ∈ V : col(v) = c} be the set of all vertices of color c in G. Finally, recall that any arc in G is of weight 1 in a UMCA-2 instance. As a consequence, if there exist two vertices v 2 ∈ V 2 and v 3 ∈ V 3 such that v 2 and v 3 share the same color and such that v 3 belongs to a solution T = (V T , A T ) of UMCA-2 in G, then we can replace v 3 by v 2 in V T without decreasing the weight of T . In the following, we thus assume without loss of generality that col(V 2 ) ∩ col(V 3 ) = ∅.

For any 1 ≤ | col + (r)| ≤ |C| -1, we prove by induction that there exists a colorful arborescence T = (V T , A T ) of weight w(T ) ≥ |C| 2 in G. To begin, if | col + (r)| = 1, then V 2 contains either a single vertex or two vertices which share the same color, since no color can appear more than twice in a UMCA-2 instance. In the first case, the single vertex in V 2 has an outgoing arc towards all the vertices in V 3 . In the second case, at least one of the vertices in V 2 has an outgoing arc towards at least |C| 2 -1 vertices of distinct colors in V 3 . Therefore, in both cases, there exists a trivial colorful arborescence T of weight w(T )

≥ |C| 2 . For any k ∈ [|C| -2], if | col + (r)| = k,
then we suppose by induction hypothesis that there exists a colorful arborescence

T = (V T , A T ) of weight w(T ) ≥ |C| 2 in G.
Suppose now that | col + (r)| = k + 1. Let c be an arbitrary color in col + (r), from which we define

V + = {r} ∪ V c ∪ N + (V c ) and V -= {r} ∪ (V 2 \ V c ) ∪ (V 3 \ {v ∈ V 3 : col(v) ∈ col + (V c )}), with C + = col * (V + ) and C -= col * (V -). By induction, notice that G[V + ] (resp. G[V -]) contains a UMCA-2 solution T + (resp. T -) of weight w(T + ) ≥ |C + | 2 (resp. w(T -) ≥ |C -| 2 ). We now show that T = T + ∪T -is a UMCA-2 solution in G.
First, recall that r necessarily is the root of T + and T -. Since r is the only vertex which belongs both to V + and V -, T is an arborescence in G. Second, by construction, observe that C = C + ⊕ (C -\ {col(r)}), where operator ⊕ represents the disjoint union between two sets. In fact, except for the root r that belongs to both sets, all vertices from the second level are kept either in V + or V -in such a way that vertices of the same color belong to the same set. Concerning the third level, the only vertices that are not considered are outneighbors of level-2 vertices from V -whose color is already present in V + . As a consequence, T is colorful and w(T ) = w(T + ) + w(T -), which leads to w(T )

≥ |C + | 2 + |C -| 2
and thus to w(T ) ≥ |C| 2 . Finally, if the center of G, say z, is such that z = r, then we consider two cases: (a) either r and z are neighbors, or (b) they lie at distance 2. In case (a), we have r ∈ V 2 meaning that all outneighbors of r except z belong to the third level of G and consequently, all its outneighbors except z are leaves. Let us study the graph G by ignoring r and its neighbors from level three. To do so, we define

V r = {r} ∪ (N + (r) \ {z}) and V = V \ V r , with C r = col * (V r ) and C = col * (V ). Notice that G[V ]
is still a superstar centered in z and, according to the proof above, it contains a UMCA-2 solution T rooted in z of weight w(T ) ≥ |C |

2

. Now, we define C u = C r \ C as the set of colors that are uniquely present in V r , i.e., that are present in V r but not in V and we build the colorful set V u as follows: for each color c ∈ C u , pick exactly one vertex v ∈ V r such that col(v) = c and add it to V u . Recall that r belongs to V r and its color is unique, thus r ∈ V u . Consequently, T u = G[V u ] is a colorful arborescence rooted in r and of weight w(T u ) = |C u | -1. We construct the final arborescence T by connecting the two colorful ones T u and T with the arc (r, z) between their corresponding roots. Since V ∩ V u = ∅ and C ∩ C u = ∅, T is a colorful arborescence rooted in r and w(T ) = w(T ) + w(T u ) + 1 which leads to w(T )

≥ |C | 2 + |C u |. Since C = C ⊕ C u , we can conclude w(T ) ≥ |C| 2 .
In case (b), r ∈ V 3 , it means that there exists a unique vertex z ∈ V 2 that lies on the path from r to z. Moreover, since G is a superstar centered in z and r is on level three, then r has a unique outneighbor that is z . Consequently, the color of z is unique. Therefore, we can apply case (a) by considering z playing the role of r. Once again, since r is connected to z and r has a unique color, r is part of the solution and this concludes the proof.

Theorem 4 shows that MCA remains APX-hard even in trees of height 2. Hence, another option, if one wants to find tractable instances, consists in constraining the maximum degree of the input tree, which motivates the study of comb-graphs. If d(v) denotes the degree of a vertex v in a graph, a comb-graph is defined as a tree for which d(v) ≤ 3 for any v ∈ V , and where all vertices of degree 3 lie on a path, called the spine. Unfortunately, we show in Theorem 8 that UMCA-2 remains APX-hard (with a large inapproximability ratio) even when the input tree is a comb-graph.

We obtain this result by reduction from Maximum Independent Set (or MIS), a proof somewhat similar to proof of Proposition 1 in [START_REF] Rizzi | Some results on more flexible versions of graph motif[END_REF]. In the following, we first explain our reduction from MIS to UMCA-2. Then, we will prove two intermediate lemmas, namely Lemmas 6 and 7, to show how to obtain a solution of MCA (resp. MIS) from a solution of MIS (resp. MCA) in the constructed instances.

We recall that MIS takes a graph H = (U, E) as input, and asks for a maximum cardinality set U ⊆ U such that no two vertices in U are connected by an edge in H. In the following, let U = {u 1 , u 2 . . . u n } and E = {e 1 , e 2 . . . e m }. For all i ∈ [n ], let L i = (j 1 , . . . , j d ) such that j 1 < . . . < j d , and e j h is incident to u i for all h ∈ [d] be the ordered list of indices of edges that are incident to u i , and note that

|L i | = d(u i ) is the degree of vertex u i . For all k ∈ [d(u i )], we denote by L i (k) the k-th element in L i .
We create a directed comb-graph G = (V, A), with:

V ={r i : i ∈ [n ]} ∪ {x Li(k) i : i ∈ [n ], k ∈ [d(u i )]} ∪ {z p i : i ∈ [n ], p ∈ [n 2 ]} and A ={(r i , r i+1 ) : i ∈ [n -1]} ∪ {(r i , x
Li(1) i

) : i ∈ [n ]} ∪ {(x Li(k) i , x
Li(k+1) i

) : i ∈ [n ], k ∈ [d(u i ) -1]} ∪ {(x Li(d(ui)) i , z 1 i ) : i ∈ [n ]} ∪ {(z p i , z p+1 i ) : i ∈ [n ], p ∈ [n 2 -1]}
For an illustration, see Figure 2. Informally, the vertices of type r i represent the vertices of U and constitute the spine of G, which is rooted in r 1 , and that we can visualize as a horizontal path. Then, to every r i we attach a vertical path composed first of vertices of type x h i , that represent the edges incident to vertex u i in U (ordered by their index), followed by n 2 vertices of type z p i . Since G is rooted in r 1 , the orientation of the arcs directly follows and G is clearly a comb-graph. Now let us describe the colors assigned to the vertices of G: each of the vertices of type r i and z j i has its own color, which is thus unique. For all h ∈ [m ], we assign the same color c(h) to the two vertices x h i1 , x h i2 ∈ V . Since x h i1 and x h i2 represent the two extremities u i1 and u i2 from E of the edge e h in U of H, this means that c(h), for any h ∈ [m ], appears exactly twice.

We can easily see that the coloring is partially ordered, since the vertices of type x h i (which are the only ones that can have repeated colors) are ordered according to the edge number they correspond to. Finally, each arc a ∈ A(G) is assigned a weight w(a) = 1, which altogether ensures that G is a valid instance of UMCA-2. In the following, for a given i ∈ [n ], we will denote by Z i the path induced by vertices of type z j i . We now prove Lemmas 6 and 7. Lemma 6. If there exists an independent set I of size k in H, then there exists a colorful arborescence Proof. We let

T = (V T , A T ) of weight W ≥ k • n 2 in G.
V T = {r i : i ∈ [n ]} ∪ {x Li(j) i : i s.t. u i ∈ I, j ∈ [d(u i )]} ∪ {z p i : i s.t. u i ∈ I, p ∈ [n 2
]}, and we define T as the spanning arborescence of V T . In that case T is colorful, otherwise there would exist x h i1 , x h i2 ∈ V T , which means by construction that vertices u i1 and u i2 from I are connected by edge e h , a contradiction. Moreover, T contains k paths Z i , each of size n 2 . Consequently, W ≥ k • n 2 . Lemma 7. If there exists a colorful arborescence T = (V T , A T ) of weight W in G, then there exists an independent set

I of size k ≥ W +1-n -m n 2 in H.
Proof. We build I according to the following rule: for all i ∈ [n ], if there exists p ∈ [n 2 ] such that z p i ∈ V T then u i ∈ I. In other words, I is composed of every i ∈ [n ] for which there exists at least one vertex of type z p i in V T . We first prove that I is an independent set. Indeed, suppose by contradiction there exists u i1 , u i2 ∈ I such that u i1 and u i2 are adjacent. In that case, there would exist h ∈ [m ] such that col(x h i1 ) = col(x h i2 ) while x h i1 and x h i2 belong to V T , which contradicts the fact that T is colorful.

We now prove that k

≥ W +1-n -m n 2
. First, note that we can always extend T to a colorful arborescence T = (V T , A T ) in such a way that the following conditions hold: (i) V T ⊆ V T , (ii) for every i ∈ [n ], r i ∈ V T and (iii) if a vertex of type z p i belongs to V T , then the whole path Z i belongs to T . Let W denote the weight of T . Since V T contains n vertices of type r i , k • n 2 vertices of type z j i and at most m vertices of type x h i , and since all arcs have weight 1, we have that W ≤ n + m -1 + k • n 2 . Now it suffices to note that W ≤ W to conclude.

We are now able to prove Theorem 8. Theorem 8. UMCA-2 cannot be approximated within O(n 1 3 -), for any > 0, even if G is a comb-graph.

Proof. Suppose UMCA-2 is approximable in polynomial time within some ratio ρ. Then, in particular one can find in polynomial time an approximate solution of weight W for the instance we built, such that W ≥ W * ρ , where W * denotes the weight of an optimal solution. According to Lemma 6, from an optimal solution of MIS of size k * , an optimal solution of weight

W ≥ k * • n 2 exists for UMCA-2, which implies that W * ≥ W ≥ k * • n 2 . By substitution, we obtain W ≥ k * •n 2
ρ . According to Lemma 7, if there exists a solution of weight W for UMCA-2, then there exists a solution of size k ≥ W +1-n -m n 2 for MIS. By substitution again, we

obtain k ≥ k * •n 2 ρ +1-n -m n 2
. Note that m +n -1

n 2 ≤ 1 as m ≤ n (n -1)

2

. Thus, we obtain k ≥ k * ρ -1. As a consequence, any approximation algorithm of ratio ρ for UMCA-2 would imply an approximation algorithm of ratio ρ for MIS. We recall that MIS cannot be approximated in polynomial time within O(n 1-) for any > 0, unless P = NP [START_REF] Zuckerman | Linear degree extractors and the inapproximability of Max Clique and Chromatic Number[END_REF] and that |V | = O(n 3 ), which concludes our theorem.

Note that in the above argument, if we replace each vertical path of n 2 vertices of type z p i by a single vertex of type z i and if we set all weights to 0 except for the incoming arcs of all vertices of type z i , Lemmas 6 and 7 easily show that there exists a independent set I of size k in the instance H of MIS if and only if there exists a colorful arborescence T = (V T , A T ) of weight w(T ) = k in the MCA + -2 instance G built from H. This observation directly implies the following result.

Corollary 9. MCA + -2 cannot be approximated within O(n

1 2 -), > 0, even if G is a comb-graph.
Similarly to Theorem 1, Theorem 8 and Corollary 9 provide large inapproximability ratios, i.e. ratios which are function of n, the number of vertices of the input graph G. However, we provide in Proposition 11 an approximation algorithm for UMCA in comb-graphs which, as in the proof of Proposition 2, relies on the fact that H is a DAG. We first need to prove the following lemma.

Lemma 10. Let G = (V, A) be a comb-graph rooted in r ∈ V , and let p be an arbitrary positive integer. If d(r, v) ≤ p for any vertex v ∈ V , then G contains at most (p + 1) 2 vertices.

Proof. By definition, any comb-graph G = (V, A) contains a spine having vertex set S ⊆ V , and for any vertex v ∈ S, G may contain a hanging path which is attached to v, i.e. a path such that only one of the two extremities of the path belongs to S.

We first assume that we want to build a comb-graph G having a maximum number of vertices n, and such that d(r, v) ≤ p for any vertex v ∈ V . To begin with, we create two vertices v a ∈ S and v b / ∈ S such that r belongs to the hanging path from v a to v b . Let a ≤ p (resp. b ≤ p) be the distance from r to v a (resp. v b ) in G. Because of the distance constraint, we know that for any vertex v ∈ S, d(v a , v) ≤ pa. As a consequence, for any v ∈ S such that d(v a , v) = d , with d ∈ {1, . . . , p -a}, the hanging path from v is of length at most pad (see Figure 3 for an illustration). Proof. In the following, recall that G contains n vertices. According to Lemma 10, if d(r, v) ≤ √ n -2 for any v ∈ V , then G contains at most ( √ n -2 + 1) 2 vertices, which contradicts the fact that G contains n vertices. As a consequence, in any MCA instance such that G is a comb-graph, there exists at least one vertex v ∈ V such that d(r, v) ≥ √ n -1. Now, recall that any solution of UMCA in G is of weight at most n -1. Moreover, recall that any path from the root in G is colorful as H is a DAG. Therefore, the longest path from the root is a solution to UMCA, of weight at least √ n -1. Since no solution of weight more than n -1 exists, this shows UMCA admits an approximation algorithm of ratio O(n

1 2 ).
Recall that Theorem 8 does not forbid any O(n 1 3 )-approximation algorithm for UMCA in comb-graphs. Therefore, determining if there exists such an approximation algorithm remains an open question. Although the approximation algorithm from Proposition 11 does not apply to comb-graphs with non-uniform weights, there exists a trivial |C|-approximation algorithm for MCA + in such graphs. If T is the optimal solution of an instance G and W * is the largest weight of G, then w(T ) ≤ W * • (|C| -1) since T cannot contain more than |C| vertices. Moreover, recall that any path from r to a vertex v ∈ V is colorful as H is a DAG. Hence, the |C|-approximation algorithm consists in taking any path from r which includes the largest weighted arc of G.

We have seen that MCA remains hard even in superstars (Theorem 4) and combgraphs (Theorem 8 and Corollary 9). Another way of restricting the input tree structure is to consider trees that are "close to paths". When G is a path, it can be easily seen that MCA is in P. The next step is to study caterpillars, which are trees that become paths after removal of their leaves. Note that a superstar becomes a star, i.e., a special case of caterpillar, after removal of its leaves. Moreover, MCA is APX-hard in superstars (see Theorem 4), and MCA is in P in stars (see Proposition 3). As shown below, more generally, MCA in caterpillars is in P. Thus, the following theorem allows us to draw a more precise line between intractable and tractable instances for MCA in trees.

Proposition 12. MCA in caterpillars is in P.

Proof. The main purpose of the algorithm we present in this proof is to show polynomiality of MCA when G is a caterpillar; no particular effort is made here on optimizing the running time. Let S = {r}∪{v ∈ V : d + (v) = 0} contain the root r and all vertices of G which are not leaves. Clearly, G[S] is connected by definition of a caterpillar. The proposed algorithm works as follows. First, we generate all colorful subsets S ⊆ S such that r ∈ S and G[S ] is connected. Second, for each such S , we denote by N ++ (S ) = {v ∈ N + (u) : u ∈ S and v / ∈ S}, we create a set S = S and we proceed as follows: for all colors c ∈ col * (N ++ (S )) \ col(S ), take x ∈ N ++ (S ) of color c with the maximum weighted incoming arc a x and add x to S only if w(a x ) > 0. From this newly built set S , we compute the spanning arborescence T , and finally output the arborescence that reaches the maximum weight among all the computed arborescences.

Clearly, the algorithm is correct because we generated all possible connected and colorful subsets S . Moreover, for any such subset S , computing a maximum spanning arborescence in a caterpillar which contains S can be achieved greedily. Since there are O(n 2 ) subsets of vertices S such that r ∈ S and G[S ] is connected, and since each S is treated in polynomial time, the whole algorithm is thus polynomial.

A closer look at the Color Hierarchy Graph H

One major difference between MCS and MCA lies in the fact that H is imposed to be a DAG in any MCA instance. In this section, we exploit this particularity and prove that MCA belongs to P whenever H is a tree. We first give the following reduction rule, and prove its correctness.

Reduction Rule 13. Let I = (G, C, col, w, r) be an MCA instance. If there exists a color c ∈ C such that (i) c does not have any outneighbor in H and (ii) c has a unique inneighbor c -= col(r) in H, then we do the following:

• for any vertex v -∈ V (G) of color c -, add max {0, max v∈N + (v -) | col(v)=c {w(v -, v)}} to the weight of each incoming arc of v -;
• remove all vertices of color c in V (G), alongside to all arcs which are incident to a vertex of color c in A(G).

Lemma 14. Reduction rule 13 is correct.

Proof. Let I = (G , C , col , w , r ) be the MCA instance which is obtained after applying Reduction rule 13 on I. We show that there exists a colorful arborescence T = (V T , A T ) of weight at least W in I if and only if there exists a colorful arborescence T = (V T , A T ) of weight at least W in I . We only show the first direction of the equivalence; the other can obtained by using a symmetric reasoning. First, if T does not contain any vertex of color c, then we can trivially set T = T . Otherwise, if T contains a vertex v of color c and an arc (u, v), then we set V T = V T \ {v} and

A T = A T \ {(u, v)}. Clearly, T is a colorful arborescence in G . Moreover, if u - is the inneighbor of u in T (and thus in T ), then w(T ) = w(T ) since w (u -, u) = w(u -, u) + w(u, v).
Figure 4 shows an illustration of the application of Reduction rule 13. Now, we show how to use this rule in order to prove that MCA belongs to P when H is a tree.

Theorem 15. MCA belongs to P when H is a tree.

Proof. First, recall that Reduction rule 13 removes at most n -1 vertices from G and modifies in polynomial time the weight of at most m -1 arcs of G. Hence, this reduction rule can be executed in polynomial time. Moreover, it can be executed at most |C| -2 times from an initial instance of MCA. Finally, let I = (G, C, col, w, r) be an initial instance of MCA such that H is a tree. If we apply Reduction rule 13 on I until it can no longer be applied, then G is clearly a star in the final instance which is obtained from I (see Figure 5 for an illustration). As MCA in stars is in P (see Proposition 3), we conclude that MCA is in P when H is a tree. We recall that s is defined as the number of arcs that need to be removed from H = (C, A C ) in order for H to become a tree. In the following, let X = {c ∈ C : d -(c) > 1} be the set of difficult colors in H, i.e., colors that have indegree strictly more than one; clearly, H is not a tree whenever X is not empty. For any X = ∅, we let p = min{d -(c) : c ∈ X }. We now show how to use Theorem 15 in order to obtain an FPT algorithm for MCA parameterized by s + p. Proof. We design a branching algorithm that recursively computes every spanning arborescence of H. To do so, we create a set Z, where initially Z = A(H), and we consider a graph H = (C, Z). For every difficult color c ∈ X , we recursively branch on the d -(c) different cases where only one incoming arc of c is not removed from Z.

r a b c 1 c 2 d 1 d 2 1 2 -1 1 2 2 8 -3 G r a b c d H(G) r a b c 1 c 2 1 2 7 1 2 G r a b c H(G )
At the end of these branching steps, each color c ∈ C has indegree 1 in H and thus the connected component of H which contains col(r) -where r is the root of G -is a tree. We then create a graph G = (V, A Z ) with A Z = A \ {(x, y) ∈ A: (col(x), col(y)) / ∈ Z} and we consider the connected component G of G which contains the root of G . Informally, G is a subgraph of G, which is built from Z and such that H(G ) is a tree. Hence, by Theorem 15, we know that computing a colorful arborescence of maximum weight in G is polynomial-time solvable. Now, for any solution T of MCA in G, recall that the color hierarchy graph of T is necessarily a tree. As a consequence, computing a solution of MCA in every such subgraph G ⊆ G ensures that the above described algorithm is correct. is a tree, we iteratively apply Reduction Rule 13, in this order, on the orange (h 1 and h 2 ), green (g 1 to g 4 ), pink (f ), dark purple (e 1 and e 2 ), light blue (c 1 and c 2 ) and finally on the red color (d). The new MCA instance is displayed in graphs G at the bottom left, and H(G ) at the bottom right. In both graphs G and G , we represent the arcs of an optimal solution to MCA in bold red.

r a b 2 b 3 b 1 b 4 c 1 c 2 d e 1 e 2 f g 2 g 3 g 1 g 4 h 1 h 2 1 -1 2 1 3 2 1 4 -1 3 2 7 1 4 1 -1 -2 1 -1 -2 1 2 G r b a g c d h e f H(G) r a b 2 b 3 b 1 b 4 5 6 15 5 5 G r b a H(G )
We now discuss the complexity of the above algorithm. To do so, let T be the search tree of the above algorithm and observe that each step that contributes to constructing T is achieved in polynomial time. The complexity of the above algorithm is thus only exponential in the number of nodes |V (T )| = c∈X d -(c) of T . We now show that |V (T )| ≤ p For instance, if p = 3, then by Proposition 16 we obtain a running time of O * (1.733 s ) for solving MCA. In general, we always have p ≥ 2 for graphs G for which H is not a tree. Thus, by setting p to 2, it leads to an FPT algorithm of the problem parameterized by s alone and we obtain the following "universal" corollary.

Corollary 17. MCA can be solved in time O * (2 s ).

FPT results with respect to parameter C

In [START_REF] Fradin | graphes complexes en biologie : problèmes, algorithmes et évaluation)[END_REF], some statistics concerning more than 600,000 biological instances of MCS (provided by Sebastian Böcker's group from Friedrich-Schiller-Universität Jena, Germany), were provided. In particular, it can be seen that after applying the reduction rules from [START_REF] White | Speedy colorful subtrees[END_REF], the average value for parameter C = n -|C| is below 16, whenever the weight of the studied metabolite is below 500 Daltons. Therefore, the study of parameter C is of particular interest for the MCA problem. Unfortunately, as noted in Section 2, MCA-1 parameterized by C is W[1]-hard. However, we show in the following that MCA is FPT parameterized by C + m -, where m -denotes the number of negative arcs in the input instance. Although in practice C + m -may appear too large -for instance, in the abovementioned experimental data, C +m -reaches (on average) almost 221 for metabolites of weight at most 500 Daltons -, this result remains of interest as it allows us to draw a border between W[1]-hardness (for C alone) and fixed-parameter tractability (for C +m -). Moreover, arcs of negative weight represent arcs for which the degree of confidence (into the actual fragmentation it corresponds to) is low: the initial data can thus be modified so as to delete the less relevant arcs (by means of a threshold), which consequently decreases the value of m -.

In order to show that MCA is FPT parameterized by C + m -, we first introduce the following notion: a fully-colorful subgraph of a graph G is a subgraph of G that contains exactly one occurrence of each color from C. We recall the following lemma from [START_REF] Fertin | On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure[END_REF]. Lemma 18 ([20]). Given any graph G with |C| colors, there exist at most 2 C fullycolorful subgraphs of G.

We are now ready to prove the next proposition. Proposition 19. MCA can be solved in O * (2 C +m -) time.

Proof. In the following, let G = (V , A ) be an arbitrary fully-colorful subgraph of G. We say that a subset X of arcs of negative weights is correct if no vertex from V has two or more incoming arcs from X. For any correct subset X ⊆ A , we will first describe how to build a subgraph G X = (V X , A X ) of G such that any spanning arborescence T X of G X necessarily contains all the arcs from X ∩ A X . Then, we will prove the following claim: if T is a solution of MCA in G, then there exists a fullycolorful subgraph G = (V , A ) of G, a correct subset of arcs X ⊆ A and a solution T X of MCA in G X such that w(T X ) = w(T ). Proof. Recall that f (v) denotes the unique inneighbor of any v ∈ V \ {r} as G is a tree. We improve the branching algorithm discussed in proof of Proposition 21 above, by using a different branching procedure. Let S = V and let us apply the following branching rule: if there exists u, v ∈ S such that (i) col(u) = col(v) and (ii) |N + (u)| > 0 or |N + (v)| > 0 (where N + (u) and N + (v) apply here in G[S]), then we branch on two cases: either

V (G u [S]) or V (G v [S]
) is removed from S. We repeat this branching procedure until it cannot longer be applied on S.

For any S which corresponds to a leaf of the search tree T , we now show how to compute a solution of MCA + in G[S]. For any such S, let U S be the set of vertices having a unique color in S. Note that because of condition (ii), two vertices u, v ∈ S can have the same color only if they are both leaves of G[S], and thus G[U S ] is connected. Besides, recall that G is a tree and that for any arc a ∈ A, its weight w(a) is positive. Thus, G[U S ] is necessarily contained in a maximum colorful arborescence T = (V T , A T ) built from G[S]. We now need to compute T from S: we start by taking in T all vertices from U S . Then, for every color c ∈ col(S) \ col(U S ), we add to V T the vertex v ∈ S of color c such that w((f (v), v)) is maximum -note that f (v) necessarily belongs to U S . Finally, T is defined as the tree which is induced by V T in G[S] (see Figure 6). It can be easily seen that T is connected, colorful and of maximum weight in G[S]. This ensures the correctness of our algorithm as any solution of MCA is necessarily contained in the graph G[S] which is produced from at least one leaf of T . The computational complexity of our algorithm derives from the fact that, at each step, if

|N + (u)| = 0 (resp. |N + (v)| = 0) then |N + (v)| > 0 (resp. |N + (u)| > 0).
Therefore, the branching vector is [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF][START_REF] Fernie | Metabolite profiling: from diagnostics to systems biology[END_REF], which leads to an O * (1.62 C ) algorithm (for an introduction to the analysis of branching vectors, see e.g. [START_REF] Cygan | Parameterized Algorithms[END_REF]).

Finally, we show that Proposition 22 can also be improved when all arcs in A have uniform weights. Proof. In the following, for any v ∈ V , if v has a unique outneighbor u in G and if u is a leaf in G, then we say that v is a near-leaf in G. Moreover, for any vertex v ∈ V such that v is neither a leaf nor a near-leaf in G, we call v a trunk-vertex in G.

We create a set S = V on which we recursively apply the following branching rule: if there exists u, v ∈ S such that (i) col(u) = col(v), (ii) u (resp. v) is a trunk-vertex in G[S] and (iii) v (resp. u) is a trunk-vertex or a near-leaf in G[S], then we remove either V (G u [S]) or V (G v [S]) from S. If we assume without loss of generality that u is a trunk-vertex, the branching vector of this rule is [START_REF] Last | Innovations: Towards the plant metabolome and beyond[END_REF][START_REF] Fernie | Metabolite profiling: from diagnostics to systems biology[END_REF]. Indeed, we remove either at least three vertices while removing V (G u [S]) -as u is a trunk-vertex -or at least two vertices while removing V (G v [S]) -as v is a trunk-vertex or a near-leaf.

For any S which corresponds to a leaf of the search tree T , let S 1 be the set of trunkvertices in G[S], S 2 be the set of near-leaves in G[S], and S 3 be the set of leaves in G[S]. We may assume that any color c ∈ C appears in only one set among col(S 1 ), col(S 2 ) and col(S 3 ). First, if S corresponds to a leaf of T , then col(S 1 )∩col(S we would have applied the above branching rule on S. Second, notice that G[S 1 ] is colorful -as S is a leaf of T -and necessarily connected. As col(S 1 ) ∩ col(S 2 ) = ∅, there exists at least one solution T of UMCA in G[S] which contains all vertices from S 1 . Indeed, if T contains a vertex v 3 ∈ S 3 such that col(v 3 ) ∈ col(S 1 ), then we can substitute v 3 in T by a vertex of the same color which belongs to S 1 . The weight of T will not be decreased as any arc weight is equal in G and as v 3 is a leaf of G. Therefore, we can remove all vertices v 3 ∈ S 3 such that col(v 3 ) ∈ col(S 1 ) and thus assume without loss of generality that col(S 1 ) ∩ col(S 3 ) = ∅. Finally, we may also assume that col(S 2 ) ∩ col(S 3 ) = ∅ according to a similar reasoning.

2 ) = ∅, otherwise r a 1 b c 1 d e 2 f 2 g 1 h 1 g 2 i 1 i 2 h 2 i 3 1 2 1 3 4 2
1 3 2 2 3 1 5
G[S] U S r a 1 b a 2 c 1 d e 2 f 2 f 1 c 2 e 1 g 1 h 1 g 2 i 1 i 2 h 2 i 3 1 2 1 3 4 2
1 3 2 2 3 1 5
For any S which corresponds to a leaf of T , we now describe how to obtain a solution T = (V T , A T ) of UMCA in G[S]. First, recall that we may assume that any vertex from S 1 belongs to V T . We now show how to select the vertices from S 2 and S 3 which also belong to V T . Let M be a maximum matching in H(G[S 2 ∪ S 3 ]) (see Figure 7 for an illustration). For any arc (c, c ) ∈ M , we add to V T a pair of vertices u, v ∈ S such that col(u) = c, col(v) = c and (u, v) ∈ A(G[S]). Finally, for any color c ∈ col(S 2 ) such that c / ∈ col(V T ), we add an arbitrary vertex of color c from S 2 to V T . Clearly, the spanning arborescence T of G[V T ] is connected and colorful. Moreover, recall that S 1 ∈ V T and that col(S 2 ) ⊆ col(V T ). As a consequence, if there exists a solution T of UMCA such that w(T ) > w(T ) in G[S], then T contains more vertices from S 3 than T , which contradicts the fact that M is a maximum matching in H(G[S 2 ∪ S 3 ]). Therefore, T is a solution of UMCA in G[S]. Besides, the proposed algorithm is correct as any solution of UMCA is necessarily contained in a graph G[S] such that S corresponds to a leaf of T . As the branching vector is (3, 2) and as the maximum matching problem can be solved in polynomial time [START_REF] Edmonds | Optimum branchings[END_REF], we conclude that UMCA can be solved in O * C ) time. We now turn to proving a lower bound on the computational complexity of MCA with respect to C . In particular, our result proves that the FPT algorithm given in Proposition 19 is essentially optimal for MCA + .

Theorem 24. The UMCA-2 problem cannot be solved in time O * ((2 -) C ) unless the Strong Exponential-Time Hypothesis fails.

Proof. First note that the Strong Exponential-Time Hypothesis (SETH) states that the CNF-SAT problem defined on p variables cannot be solved in time O * ((2 -) p ) for any > 0 [START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF]. The reduction from CNF-SAT we present here is adapted from proof of Theorem 1 in [START_REF] Fertin | Graph Motif problems parameterized by dual[END_REF]. We first formally define CNF-SAT.

CNF-SAT

• Input: A set X = {x 1 , x 2 . . . x p } of variables, a CNF-formula φ on a set C = {C 1 , C 2 . . . C q } of clauses built from X.

• Output: An assignment β : X → {true, false} that satisfies φ.

Starting from any instance φ of CNF-SAT, we build an instance of UMCA-2 in the form of a three-level graph G (see Figure 8). First, level 1 only consists of the root r. For each variable x i ∈ X, 1 ≤ i ≤ p, we create two vertices v i and v i at level 2. For each clause C j ∈ C, 1 ≤ j ≤ q, we create a vertex z j at level 3. We then add an arc from r to v i and to v i for all i ∈ [p]. There is also an arc from v i (resp. v i ) to z j iff literal x i (respectively x i ) appears in clause C j , for all i ∈ [p] and for all j ∈ [q]. The root r (level 1) and every level 3 vertex is assigned a unique color. At level 2, for all i ∈ [p], v i and v i share the same color c i . Thus, every color c ∈ C can appear at most twice, and these colors can easily be partially ordered (and thus totally ordered) based on their level in the graph. Finally, the weight of every arc is 1, and it can be seen that G is indeed an instance of UMCA-2.

We now show that there exists an assignment β that satisfies φ iff there exists a colorful arborescence of weight p + q (and thus of order p + q + 1) in G.

(⇒) Suppose there exists an assignment true/false of each x i ∈ X, say β, that satisfies φ. Let I T (resp. I F ) be the set of indices i ∈ [p] such that x i is set to true (resp. false) by β. Let S = {r} ∪ {v i for all i ∈ I T } ∪ {v i for all i ∈ I F } ∪ {z j for all j ∈ [q]}. Necessarily, G[S] is connected: first, r is connected to every level-2 vertex; second, a vertex z j corresponds to a clause satisfied by some x i (resp. x i ), and by definition G[S] contains v i (resp. v i ), which is connected to z j . Now, let T = (V T , A T ) be a spanning arborescence of G[S]. Clearly, T is colorful and of total weight p + q.

(⇐) Suppose there exists a colorful arborescence T = (V T , A T ) of weight p + q in G, thus of order p + q + 1. Note that T contains at most p vertices from level 2, and thus at least q vertices from level 3. However, level 3 contains exactly q vertices. Thus, V T must be composed of the root, exactly p vertices at level 2 and exacty q vertices at level 3. Since level 2 is composed of 2p vertices where each color appears twice, and since T is colorful, for all i ∈ [p], either v i or v i is in V T . The assignment β is thus the following: if v i ∈ V T (resp. v i ∈ V T ) then x i is set to true (resp. false). Since T is connected, then for any z j with j ∈ [q], there exists f (z j ) ∈ T , which means that every clause in φ is satisfied by at least one literal in β.

r v 1 v 1 v 2 v 2 v 3 v 3 v 4 v 4 z 1 z 2 z 3
Hence, since n = 2p + q + 1 and |C| = p + q + 1, we have that C = n -|C| = p. As a consequence, every algorithm running in time O * ((2 -) C ) for UMCA-2 would imply an algorithm running in time O * ((2 -) p ) for CNF-SAT, which would contradict SETH.

Conclusion

In this paper, we introduced the MCA problem, a constrained version of the MCS problem, where the input graph G and its Color Hierarchy Graph H must be two rooted DAGs. MCA is designed to better represent the initial motivation of de novo inference of metabolites from tandem mass spectra, and leads to better-shaped algorithms. Although we showed that MCA remains APX-hard even for constrained inputs, we also showed that it is possible to take advantage of the fact that H is a DAG to describe new polynomial-time and FPT algorithms, alongside to new approximation algorithms. It remains an open problem whether other polynomial-time algorithms based on the structure of H can be designed.

We also provided algorithmic results concerning parameter C = n -|C|. Although MCA is W [START_REF] Böcker | Towards de novo identification of metabolites by analyzing tandem mass spectra[END_REF]-hard when parameterized by C , we were able to provide several FPT results parameterized by C for some variants of MCA. Some of these may still be improved, even though other results taking C as a parameter were recently obtained in [START_REF] Fertin | On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure[END_REF]. Many problems remain open for the MCA problem, and notably (in)approximability gaps remain to be filled. A more general question, based on the fact that, in experimental data, C remains high when the weight of a metabolite is greater than 500 Daltons, is whether it is possible to obtain new data reduction rules which would make our FPT algorithms parameterized by C even more efficient.

Figure 2 :

 2 Figure 2: Construction of a UMCA-2 instance (on the right) from an MIS instance (on the left). The edges of H are called e 1 , e 2 , . . . , e 5 . Each non-colored vertex of G in the above picture has a unique color. For clarity, we do not represent the weights of the arcs -which are all equal to 1 by definition. The subset I = {u 1 , u 3 , u 5 } (in bold red) is an MIS solution in H and corresponds to the UMCA-2 solution T in G with bold red arcs.

Figure 3 :

 3 Figure 3: Construction of a comb-graph G maximizing |V (G)| and such that d(r, v) ≤ p for any v ∈ V , where p is a given positive integer). The braces represent a maximum distance between two vertices: the symbol * means "pa -1" and * * means "pa -2". Now let us turn to computing the maximum number of vertices n in such a combgraph G. Note that n ≤ 1 + a + b + 2 • p-a d =1 d , which leads to n ≤ 1 + a + b + 2 • (p-a)(p-a+1) 2 and n ≤ (pa) 2 + p + b + 1. Now, observe that n is maximized by setting a to 0 (which in turn implies r ∈ S), and b = p. As a consequence, we have that n ≤ (p + 1) 2 , which concludes the proof. Lemma 10 now allows us to prove the next result. Proposition 11. UMCA in comb-graphs can be approximated in polynomial time within a ratio O(n 1 2 ).

Figure 4 :

 4 Figure 4: Example of application of Reduction rule 13 on the orange color (vertices marked d 1 and d 2 )of an initial MCA instance, whose initial graph G is at the top left and whose initial Color Hierarchy Graph is at the top right. We create a new MCA instance whose graph G is at the bottom left and whose Color Hierarchy Graph is at the bottom right. We initialize G = G, then we remove all orange vertices (d 1 and d 2 ) in G (together with their incident arcs). Finally, we set w (a, c 1 ) = -1 + max{0, max{2, 8}} = 7, w (a, c 2 ) = 1 + max{0, -3} = 1 and w (b, c 2 ) = 2 + max{0, -3} = 2 in G . In both graphs G and G , we represent the arcs of an MCA solution in bold red.

Figure 5 :

 5 Figure 5: Example of iterative applications of Reduction Rule 13 on an initial MCA instance, whose initial graph G is at the top left and whose initial Color Hierarchy Graph is at the top right. As H(G)is a tree, we iteratively apply Reduction Rule 13, in this order, on the orange (h 1 and h 2 ), green (g 1 to g 4 ), pink (f ), dark purple (e 1 and e 2 ), light blue (c 1 and c 2 ) and finally on the red color (d). The new MCA instance is displayed in graphs G at the bottom left, and H(G ) at the bottom right. In both graphs G and G , we represent the arcs of an optimal solution to MCA in bold red.

s p- 1 1 d 1 x- 1 1 p- 1 1 d

 1111111 which in turn shows that MCA can be solved in O * (p s p-1 ) time. Assuming X is not empty, we look for the smallest real number α such that the inequality (1)d -(c) ≤ α d -(c)-1 holds for all colors c ∈ X . From (1), we have log(d -(c)) ≤ (d -(c) -1) • log(α), thus α ≥ e log(d -(c)) d -(c)-1 , which gives us α ≥ d -(c) -(c)-1 . The corresponding function f (x) = x ismonotonously decreasing for all x ∈ [2; +∞[. By definition of p, this implies that we can set α to p in order to ensure that α ≥ d -(c) -(c)-1 for any c ∈ X . As |V (T )| ≤ c∈X α d -(c)-1 and as s = c∈X d -(c) -1, we obtain |V (T )| ≤ p s p-1 and the time complexity of the above algorithm is O * (p s p-1 ).

Proposition 22 .

 22 MCA + in trees can be solved in O * (1.62 C ) time.

Proposition 23 .

 23 UMCA in trees can be solved in O * (1.33 C ) time.

GFigure 6 :

 6 Figure 6: of application of the algorithm proposed in Proposition 22. Here, S corresponds to a leaf in the search tree such that we iteratively removed V (Ga 2 [S]) and then V (G f 1 [S]) from S = V . Subset U S contains all vertices of unique color which belong to S. As G[U S ] is connected, G[U S ] necessarily belongs to any solution T of MCA + in G[S]. For any color c ∈ col(S \ U S ), it remains to add to V T the vertex v ∈ S of color c such that w((f (v), v)) is maximum in G[S]. In both G and G[S], we represent a solution of MCA with bold red arcs.

GFigure 7 :

 7 Figure 7: Example of application of the algorithm proposed in Proposition 23. Here, S corresponds to a leaf in the search tree. For clarity, we do not represent the weights of the arcs, which are all equal to 1 by definition. Observe that the spanning arborescence of G[S 1 ] necessarily belongs to any solution of UMCA in G[S] as the color of any vertex from G[S 1 ] is unique and as G[S 1 ] is connected. As a consequence, any solution of UMCA also contains a vertex of color c for any c ∈ col(S 2 ). By solving the instance H(G[S 2 ∪ S 3 ]) of Maximum Matching (framed), we then compute the subset of vertices from S 3 which belongs to a solution of UMCA.

Figure 8 :

 8 Figure 8: Construction of a UMCA-2 instance from φ= (x 1 ∨ x 2 ∨ x 3 ) ∧ (x 1 ∨ x 4 ) ∧ (x 2 ∨ x 4 ) of SAT.For clarity, arc weights (which are all equal to 1 by definition) are not represented. The arcs of a solution T of UMCA-2 are colored in bold red. From this solution, the assignment β consisting of setting x 1 = true, x 2 = false, x 3 = true and x 4 = false satisfies φ.

2 log δ n in polynomial time, unless NP ⊆ DTIME[2 poly log n ]. Proof. Dondi et al. introduced the Maximum Level Motif (or MLM) prob- lem [18], a maximization variant of the Graph Motif problem [21] dealing with colorful motifs on trees

  . Besides, MLM incorporates the notion of a leveled coloring function col : V → C for which two vertices can have the same color only if they are at the same distance from the root. The formal definition of MLM is given below.

			Constraint	Variant	Result
			tree	UMCA	no 2 log δ n approx., δ < 1 (Th. 1)
					O( n log n ) approx. in binary trees (Prop. 2)
	Restriction	on G	superstar comb-graph	UMCA-2 UMCA-2 UMCA	APX-hard (Th. 4) 2-approx. (Prop. 5) no O(n 1 3 -) approx. (Th. 8) O(n 1 2 -) approx. (Prop. 11)
			caterpillar	MCA	belongs to P (Prop. 12)
		H
		on	tree	MCA	belongs to P (Th. 15)

Table 1 :

 1 Overview of the approximation and exact results presented in this paper for the MCA problem and its variants. Here, n is the number of vertices in G. Positive results are obtained based on the fact that H is a DAG.

	Variant	Restriction on G	Result
	MCA	-	O * (2 C +m -) (Prop. 19)
	MCA +	-	O * (2 C ) (Cor. 20)
	MCA	G is a tree	O * (2 C ) (Prop 21)
	MCA +	G is a tree	O * (1.62 C ) (Prop. 22)
	UMCA	G is a tree	O * (1.33 C ) (Prop. 23)
	UMCA-2	-	no O * ((2 -) C ) algorithm (Thm. 24)

Table 2 :

 2 Overview of the parameterized results presented in this paper for the MCA problem and its variants. Here, n is the number of vertices in G, C is the color set of G, C = n -|C| and m -is the number of arcs with negative weight in G.

As a side note, we point out an error in the inapproximation ratio given in Theorem 1 in[START_REF] Rauf | Finding maximum colorful subtrees in practice[END_REF], which should be O(n 1

-) instead of O(n 1-).

Acknowledgments

We would like to thank the referees for their numerous valuable comments, which helped improve the quality of the paper.

This work was partially supported by the PHC PROCOPE project "Efficient

We show how to build a subgraph G X = (V X , A X ) of G from a fully-colorful subgraph G = (V , A ) and a correct subset X ⊆ A . First, we initialize G X = G . Second, for any vertex v ∈ V , if v has an incoming arc which belongs to X, then we remove from A X all the other incoming arcs of v. Third, we remove from G X all the vertices v ∈ V X (and their incident arcs) such that there does not exist any path from r to v in G X . Now, notice that any spanning arborescence of G X necessarily contains every arc of X which belongs to G X , as any vertex which is incident to an arc from X is necessarily of indegree 1.

We can now prove our claim. Let T = (V T , A T ) be a solution of MCA in G and let G = (V , A ) be a fully-colorful subgraph of G such that T ⊆ G . As G is fully-colorful, there does not exist any pair of vertices u ∈ V T and v ∈ (V \ V T ) such that w(u, v) > 0, otherwise T would not be a solution of MCA in G -and thus in G. As a consequence, we set X = {a ∈ A T | w(a) < 0} and build G X as described above. Clearly, T is also an arborescence of maximum weight in G X . Therefore, to ensure that an optimal solution of MCA in G is found, we generate all fully-colorful subgraphs G of G and any correct subset of arcs X in G , build all corresponding graphs G X , and for each find a maximum weight spanning arborescence. Now, recall that computing such a spanning arborescence takes polynomial time [START_REF] Chu | On shortest arborescence of a directed graph[END_REF][START_REF] Edmonds | Optimum branchings[END_REF]. Besides, observe that G contains at most 2 m -correct subsets of arcs and recall by Lemma 18 that G contains at most 2 C fully-colorful subgraphs. Hence, altogether, our algorithm has a running time of O * (2 C +m -).

By setting m -= 0, the above theorem implies the following corollary.

Corollary 20. MCA + can be solved in O * (2 C ) time.

In the following, we will see that constraining the input instances allows us to derive several other positive results -for instance, if we constrain the input graph of an MCA instance, instead of constraining the weight function as in Corollary 20.

Proposition 21. MCA in trees can be solved in O * (2 C ) time.

Proof. We design a recursive branching algorithm based on the colors of the input graph G. We first let S = V . If S is not colorful, we consider u, v ∈ S such that col(u) = col(v) and recursively branch on two cases: either

) is the induced DAG of G[S] that is rooted in u (resp. v). Clearly, for each set S we finally obtain, G[S] is a colorful tree. As a consequence, H(G[S]) is itself a tree, and by Theorem 15, we can compute a maximum weighted arborescence in G[S] in polynomial time. Clearly, the above described algorithm is correct, and its running time is exponential only in the number of nodes of the search tree. Since this search tree is binary and of height C = n -|C|, our algorithm runs in O * (2 C ).

We now show that Proposition 21 can be improved when all arcs a ∈ A have positive weights, based on the fact that, in that case, finding a maximum weighted colorful arborescence when repeated colors appear as leaves in the input tree is polynomial.