Riccardo Dondi
email: riccardo.dondi@unimib.it

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

Stéphane Vialette
email: vialette@univ-mlv.fr

Complexity Issues in Vertex-Colored Graph Pattern Matching ✩,✩✩

problem to be fixed-parameter tractable when parameterized by the size of the motif, and we give a faster algorithm in case the target graph is a tree. Furthermore, we prove the Min-CC problem for trees not to be approximable within ratio c log n for some constant c > 0, where n is the order of the target graph, and to be W[2]-hard when parameterized by the number of connected components in the occurrence of the motif. Finally, we give an exact exponential-time algorithm for the Min-CC problem in case the target graph is a tree.

We prove that the Maximum Motif problem is APX-hard even in the case where the target graph is a tree of maximum degree 3, the motif is actually a set and each color occurs at most twice in the tree. Next, we strengthen this result by proving that the problem is not approximable within factor 2 log δ n , for any constant δ < 1, unless NP ⊆ DTIME(2 poly log n ). We complement these results by presenting two fixed-parameter algorithms for the problem, where the parameter is the size of the solution. Finally, we give exact exponential-time algorithms for this problem.

Abstract

Searching for motifs in graphs has become a crucial problem in the analysis of biological networks. In the context of metabolic network analysis, Lacroix et al [V. Lacroix, C.G. Fernandes and M.-F. Sagot, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3 (2006), no. [START_REF] Bonsma | Complexity results for restricted instances of a paint shop problem[END_REF], 360368 ] introduced the NP-hard general problem of finding occurrences of motifs in vertexcolored graphs, where a motif M is a multiset of colors and an occurrence of M in a vertex-colored graph G, called the target graph, is a subset of vertices that induces a connected graph and the multiset of colors induces by this subset is exactly the motif.

Pursuing the line of research pioneered by Lacroix et al. and aiming at dealing with approximate solutions, we consider in this paper the above-mentioned problem in two of its natural optimization forms, referred hereafter as the Min-CC and the Maximum Motif problems. The Min CC problem seeks for an occurrence of a motif M in a vertex-colored graph G that induces a minimum number of connected components whereas the Maximum Motif problem is concerned with finding a maximum cardinality submotif M ′ ⊆ M that occurs as a connected motif in G.

We prove the Min-CC problem to be APX-hard even in the extremal case where the motif is a set and the target graph is a path. We complement this result by giving a polynomial-time algorithm in case the motif is built upon a fixed number of colors and the target graph is a path. Also, extending [M. Fellows, G. Fertin, D. Hermelin, and S. Vialette, Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 4596, Springer, 2007, pp. 340351 ], we prove the Min-CC

Introduction

Searching for motifs in graphs has become a crucial problem in the analysis of biological networks (e.g. protein-protein interaction, regulatory and metabolic networks). Roughly speaking, there exist two different views of graph motifs. Topological motifs (patterns occurring in the network) are the classical view [START_REF] Kelley | Conserved pathways within bacteria and yeast as revealed by global protein network alignment[END_REF][START_REF] Koyutürk | Pairwise local alignment of protein interaction networks guided by models of evolution[END_REF][START_REF] Scott | Efficient algorithms for detecting signaling pathways in protein interaction networks[END_REF][START_REF] Sharan | Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data[END_REF][START_REF] Sharan | Conserved patterns of protein interaction in multiple species[END_REF] and computationally reduce to graph isomorphism, in the broad meaning of that term. These motifs have recently been identified as basic modules of molecular information processing. By way of contrast, functional motifs, introduced recently by Lacroix et al. [START_REF] Lacroix | Motif search in graphs: application to metabolic networks[END_REF], do not rely on the key concept of topology conservation but focus on connectedness of the network vertices sought. This latter approach has been considered in subsequent papers [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF][START_REF] Bruckner | Topologyfree querying of protein interaction networks[END_REF][START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF]. Formally, searching for a functional motif reduces to the following graph problem (referred hereafter as Graph Motif) [START_REF] Lacroix | Motif search in graphs: application to metabolic networks[END_REF]: Given a target vertex-colored graph G = (V, E) and a multiset of colors M of size k, find a subset V ′ ⊆ V , |V ′ | = k (= |M|) such that (i) the vertex induced subgraph G[V ′ ] is connected and (ii) there exists a color-preserving bijective mapping from M to V ′ .

The Graph Motif problem is NP-complete even if G is a tree with maximum degree 3 and M is a set [START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF]. NP-completeness has also been shown in case G is a bipartite graph with maximum degree 4 and M is built over two colors only [START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF]. The seeming intractability of the Graph Motif problem has naturally led to parameterized complexity considerations [START_REF] Downey | Parameterized complexity[END_REF]. The Graph Motif problem can be solved in O(4.32 k k 2 m) randomized time [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF], where m is the number of edges in G, and in O(n 2cω+2 ) time [START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF], where ω is the treewidth of G and c is the number of distinct colors in M. When the number of distinct colors in the motif is taken as a parameter, the Graph Motif problem is, however, W [START_REF] Alon | Color coding[END_REF]-hard even in case G is a tree.

Aiming at accurate models, variants of the Graph Motif problem are greatly needed. To this aim, Betzler et al. [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF] replaced the connectedness demand by more robust requirements, and proved the problem of finding a biconnected occurrence of M in G to be W [START_REF] Alon | Color coding[END_REF]-complete when the parameter is the size of the motif. This result is of particular importance as it sheds light on the fact that a seemingly small step towards motif topology results in parameterized intractability.

Following the investigations of [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF][START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF][START_REF] Lacroix | Motif search in graphs: application to metabolic networks[END_REF], we discuss in this paper issues about formulations of the Graph Motif problem from an optimization point of view. More precisely, we introduce two optimization problems (a minimization one and a maximization one) that deal with approximate occurrences: Min-CC and Maximum Motif.

The Min-CC problem is concerned with minimizing the number of connected components in G[V ′ ], i.e., finding an occurrence of M in G that results in as few connected components as possible. Being a natural generalization of the Graph Motif problem, this problem is clearly NP-hard as well. As we will see soon, the Min-CC problem is APX-hard even in the extremal case where the motif is a set and the target graph is a path and is not approximable within ratio c log n for some constant c > 0 if the target graph is a tree, where n is the order of the target graph. From a parameterized point of view, the Min-CC problem is, however, fixed-parameter tractable when the parameter is the size of the motif but becomes W [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF]-hard when the parameter is the number of connected components in the occurrence of the motif (the problem is, however, only known to be W [START_REF] Alon | Color coding[END_REF]-hard for paths [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF]).

The Maximum Motif problem, a natural NP-hard dual variant of the Graph Motif problem, is concerned with finding a maximum cardinality submotif M ′ ⊆ M that occurs as a connected motif in G. Notice that, although both the Min-CC and Maximum Motif problems deal with approximate solutions, the Min-CC problem focusses on spread-out solutions whereas the Maximum Motif problem considers approximate motifs. We prove here that the Maximum Motif problem is APX-hard even in the case where the target graph is a tree of maximum degree 3, the motif is colorful and each color has at most 2 occurrences in the tree. Then, we strengthen this result by proving that the problem is not in APX and not approximable within factor 2 log δ n unless NP ⊆ DTIME (2 poly log n ). Finally, we give two fixed-parameter algorithms for the Maximum Motif problem problem.

This paper is organized as follows. We recall basic definitions in Section 2. Section 3 is devoted to the Min CC problem and Section 4 to the Maximum Motif problem.

Preliminaries

In this section we introduce preliminary definitions that will be useful in the rest of the paper. Let G = (V, E) be a graph. For any V ′ ⊆ V , we denote by G[V ′ ] the subgraph of G induced by V ′ , that is G[V ′ ] = (V ′ , E ′ ) and {u, v} ∈ E ′ if and only if u, v ∈ V ′ and {u, v} ∈ E(G). Let v ∈ V , we denote by N (v) the set of vertices u ∈ V such that {u, v} ∈ E. Let V ′ ⊆ V , we denote by N (V ′ ) the set of vertices u ∈ (V \ V ′ ) such that {u, v} ∈ E for some v ∈ V ′ .

A coloring of G is a mapping λ : V → C, where C is a set of colors. For any subset V ′ of V , we let C(V ′ ) stand for the multiset of colors assigned to the vertices in V ′ . A motif M is a multiset of colors built over a set of colors C. In case M is actually a set, we call it a colorful motif.

An occurrence of M in G is a subset V ′ ⊆ V such that (i) G[V ′ ] is connected, and (ii) C(V ′ ) = M. A color-preserving injective mapping θ of M to G (equipped with a coloring λ) is an injective mapping θ : M → V(G), such that λ(θ(c)) = c for every c ∈ M.
The subgraph induced by a color-preserving injective mapping θ :

M → V(G) is the subgraph of G induced by the images of θ in G.
A tree where a root has been specified is called a rooted tree. In a rooted tree with root r, for every non-root node x, let e x be the unique edge incident to x that lies on the path from x to r. Then e x can be thought of as connecting each node x to its parent. Two vertices with the same parent are said to be siblings. Rooted trees can also be considered as directed in the sense that all edges connect parents to their children. Given this parent-child relationship, a descendant of a node x in a directed tree is defined as any other node reachable from x.

We can now define the two problems we are interested in.

Min-CC

• Input : A vertex colored graph G and a colored motif M.

• Solution : A color-preserving injective mapping θ : M → V(G), i.e., λ(θ(c)) = c for every c ∈ M.

• Measure : The number of connected components in the subgraph induced by θ.

In other words, the Min-CC problem asks to find a subset V ′ ⊆ V(G) that matches M, and that minimizes the number of connected components of G[V ′ ]. It is thus NP-complete even if the target graph is a tree and the occurrence is required to be connected (i.e., the occurrence of M in G results in one connected component) [START_REF] Lacroix | Motif search in graphs: application to metabolic networks[END_REF].

Maximum Motif

• Input : A vertex colored graph G and a colored motif M. • Solution : A submotif M ′ ⊆ M and a color-preserving injective mapping θ of M ′ to G such that the subgraph induced by θ is connected.

• Measure : The size of the submotif M ′ Intuitively, the Maximum Motif problem thus asks for the largest submotif M ′ ⊆ M that occurs in G as a connected component. Being a mere restriction of the Graph Motif problem, the Maximum Motif problem is NP-complete as well [START_REF] Lacroix | Motif search in graphs: application to metabolic networks[END_REF].

Minimizing the number of connected components: the Min-CC problem

We consider here the Min-CC problem. We show that this problem is APX-hard for paths but is fixed-parameter tractable when parameterized by the size of motif (it is worth mentioning that the Min-CC problem for paths with respect to the parameter "number of components" is W[1]-hard [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF]). In addition, we give a faster fixed-parameter algorithms for trees and a polynomialtime one for paths with a fixed number of colors. Finally, we show that the Min-CC problem for trees with respect to the parameter "number of components" is W [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF]-hard and present an exact -but exponential -algorithm for trees.

Hardness result for paths

In this section we show that the Min-CC problem is APX-hard even in the simple case where the motif M is a set and the target graph is a path in which each color in C occurs at most twice. Our proof consists in a reduction from a restricted version of the Paintshop-For-Words problem [START_REF] Bonsma | Complexity results for restricted instances of a paint shop problem[END_REF][START_REF] Bonsma | Complexity results on restricted instances of a paint shop problem for words[END_REF][START_REF] Hochstättler | Complexity results on a paint shop problem[END_REF].

First, we need some additional definitions. Define an isogram to be a word in which no letter is used more than once (also referred to as p-sequences in the literature, see e.g. [START_REF] Fellows | Analogs and duals of the MAST problem for sequences and trees[END_REF][START_REF] Guillemot | Parameterized complexity and approximability of the SLCS problem[END_REF]). A 2-isogram is a word in which each letter occurs exactly twice. A cover of size k of a word u is an ordered collection of words

C = (v 1 , v 2 , . . . , v k ) such that u = w 1 v 1 w 2 v 2 . . . w k v k w k+1 and v = v 1 v 2 . . . v k is an isogram The cover is called prefix (resp. suffix ) if w 1 (resp. w k+1 ) is the empty word.
A proper 2-coloring of a 2-isogram u is an assignment f of colors c 1 and c 2 to the letters of u such that every letter of u is colored with color c 1 once and colored with color c 2 once. If two adjacent letters x and y are colored with different colors we say that there is a color change between x and y (and that the color change occurs at the position of y). For the sake of brevity, we denote a 2-isogram u together with a proper 2-coloring f of it as the pair (u, f ).

The 1-Regular-2-Colors-Paint-Shop problem is defined as follows: Given a 2-isogram u, find a 2-coloring f of u that minimizes the number of color changes in (u, f ). Bonsma [START_REF] Bonsma | Complexity results for restricted instances of a paint shop problem[END_REF] proved that the 1-Regular-2-Colors-Paint-Shop problem is APX-hard. We show here how to reduce the 1-Regular-2-Colors-Paint-Shop problem to the Min-CC problem for paths. We need the following easy lemmas. Lemma 1. Let u be a 2-isogram and C be a minimum cardinality cover of u. Then C cannot be both prefix and suffix.

Proof. Suppose that there exists a minimum cardinality cover C of u that is both prefix and suffix. Write C = (v 1 , v 2 , . . . , v k ). Then u can be written as Proof. Let u be a 2-isogram and denote the i-th letter of u by u[i]. For ease of exposition, write n = |u| and l = k 2 . Let f be a proper 2-coloring of u with k color changes and suppose that the color changes occur at positions i 1 < i 2 < . . . < i k in u. Without loss of generality, assume that the first letter of u is colored with color c 1 by f . Define the collection of words C = (v 1 , v 2 , . . . , v l ) as follows:

u = v 1 w 1 v 2 w 2 . . . w k-1 v k for appropriate words w 1 , w 2 , . . . , w k-1 . By definition, v = v 1 v 2 ...v k is an isogram. But, since u is a 2-isogram, then w = w 1 w 2 ...w k-1 is an isogram as well. Hence it follows that C ′ = (w 1 , w 2 , ..., w k-1 ) is a cover of u of size k -1, a contradiction.
v j = u[i 2j-1 ]u[i 2j-1 + 1] . . . u[i 2j -1] j = 1, 2, . . . , l -1 v l = u[i k-1 ]u[i k-1 + 1] . . . u[i k -1] if k is even u[i k ]u[i k + 1] . . . u[n] if k is odd.
We claim that C is a cover of u. Indeed, by construction v = v 1 v 2 . . . v l is a monochromatic word that contains all the letters in u colored with color c 2 by f . Since f is a proper 2-coloring of u, exactly one occurrence of each letter is colored with color c 2 , and hence C is a cover of u of size l = k 2 . Conversely, let C = (v 1 , v 2 , . . . , v l ) be a cover of u. By definition, the word v = v 1 v 2 . . . v l is an isogram and u can be written as u = w 1 v 1 w 2 v 2 . . . w l v l w l+1 for appropriate -possibly empty -words w 1 , w 2 , . . . , w l+1 . Define a 2-coloring f of u as follows: color all the letters of the words in C with color c 2 and all the other letters with color c 1 . By construction, f is a proper 2-coloring of u. According to the proof of Lemma 1, there is no loss of generality in assuming that (i) C is suffix or (ii) C is neither prefix nor suffix. If C is neither prefix nor suffix then f is a proper 2-coloring of u with 2l color changes. If C is suffix then f is a proper 2-coloring of u with 2l -1 color changes.

Combining Lemma 2 with the fact that the 1-Regular-2-Colors-Paint-Shop problem is APX-hard, we have the following result.

Proposition 1. The following problem is APX-hard: Given a 2-isogram u, find a minimum cardinality cover of u.

Corollary 1. The Min-CC problem is APX-hard even if M is a set and P is a path in which each color appears at most twice.

Proof. Let u be a 2-isogram over the alphabet Σ. Starting from u construct an instance of the Min-CC problem as follows. Let M = Σ and let P = (x 1 , x 2 , x |u| ) be a vertex-colored path, where each vertex x i is colored u[i], 1 ≤ i ≤ |u|. Since u is a 2-isogram, each color of Σ occurs at most twice. Now, it is a simple matter to check that cardinality covers of u are in bijective correspondence with occurrences of M in P .

Fixed-parameter algorithms

Corollary 1 gives us a sharp hardness result for the Min-CC problem. To complement this negative result, we first prove here that the Min-CC problem is fixed-parameter tractable [START_REF] Downey | Parameterized complexity[END_REF][START_REF] Flum | Parameterized complexity theory[END_REF][START_REF] Niedermeier | Invitation to fixed parameter algorithms[END_REF] when parameterized by the size of the motif M. The algorithm is a straightforward extension of a recent result [START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF] and is based on the color-coding technique [START_REF] Alon | Color coding[END_REF]. Then, we give a faster fixedparameter algorithm in case the target graph is a tree.

The Min-CC problem is fixed-parameter tractable

Let G be a graph and k be a positive integer. Recall that a family F of functions from V(G) to {1, 2, . . . , k} is perfect if for any subset V ⊆ V(G) of k vertices there is a function f ∈ F which is injective on V (see [START_REF] Alon | Color coding[END_REF]). Let (G, M) be an instance of the Min-CC problem, where M is a motif of size k. Then there is an occurrence of M in G, say V ⊆ V(G), that results in a minimum number of connected components. Furthermore, suppose we are provided with a perfect family F of functions from V(G) to {1, 2, . . . , k}. Since F is perfect, we are guaranteed that at least one function in F assigns V with k distinct labels. Let f ∈ F be such a function. We now turn to defining a dynamic programming table T indexed by vertices of G and subsets of {1, 2, . . . , k}. For any v ∈ V(G) and any L ⊆ {1, 2, . . . , k}, we define T L [v] to be the family of all submotifs M ′ ⊆ M, |M ′ | = |L|, for which there exists an exact occurrence of M ′ in G, say V , such that v ∈ V and the set of (unique) labels that f assigns to V is exactly L. We need the following lemma.

Lemma 3 ([12]

). For any labeling function f : V(G) → {1, 2, . . . , k}, there exists a dynamic programming algorithm that computes the table T in O(2 5k kn 2 ) time.

Now, denote by P the set of all pairs (M

′ , L ′ ) ∈ 2 M × 2 L with |M ′ | = |L ′ |
such that there exists an exact occurrence of M ′ in G, say V ′ , such that the set of (unique) labels that f assigns to V ′ is exactly L ′ . Clearly, |P| ≤ 2 2k . Furthermore, by resorting to any data structure for searching and inserting that guarantees logarithmic time [? ] (and observing that any two pairs (M ′ , L ′ ) and (M ′′ , L ′′ ) can be compared in O(k) time), one can construct the set P in O(nk 2 2 2k ) time by running through the table T . Our algorithm now exhaustively considers all subsets of P of size at most k to find an occurrence of M in G that results in a minimum number of connected components. The rationale of this approach is that two pairs (M ′ , L ′ ) and (M ′′ , L ′′ ) with L ′ ∩ L ′′ = ∅ correspond to non-overlapping occurrences in G. The total time of this latter procedure is certainly upper-bounded by

k i=1 k 2 2k i ≤ k 2 2 2k 2 .
Summing up and taking into account the time for computing the table T , the running time for a given

f ∈ F is O(2 5k kn 2 + nk 2 2 2k + k 2 2 2k 2 ).
According to Alon et al. [START_REF] Alon | Color coding[END_REF], we need to use O(2 O(k) log n) functions f : V(G) → {1, 2, . . . , k}, and such a family F can be computed in O(2 O(k) n log n) time. For each f ∈ F we use the above procedure to determine an occurrence of M in G that results in a minimum number of connected components. We have thus proved the following.

Proposition 2. The Min-CC problem is fixed-parameter tractable when parameterized by the size of the motif.

A faster fixed-parameter algorithm for trees

We proved in Section 3.1 that the Min-CC problem is APX-hard even if the target graph is a path. To complement Proposition 2, we give here a dynamic programming algorithm for trees that does not rely on the color-coding technique (notice, however, that the color-coding technique has been recently shown practical, see e.g. [START_REF] Hüffner | Algorithm engineering for colorcoding with applications to signaling pathway detection[END_REF]).

Let (G, M) be an instance of the Min-CC problem for trees where both G and M are built upon a set of colors C. Let k = |M| and q = |C|. Furthermore, for ease of exposition, write V(G) = {1, 2, . . . , n} and assume G is rooted at some arbitrary vertex r(G).

Our dynamic programming algorithm is basically an exhaustive search procedure. More precisely, it consists in storing -in a bottom-up fashion -for each vertex i of G and each submotif M ′ ⊆ M that occurs in T (i), i.e., the subtree rooted at i, the minimum number of connected components that results in an occurrence of M ′ in T (i). More precisely, for each vertex i of G, we compute two dynamic programming tables

X[i] and Y [i]. Table X[i] stores all pairs (M ′ , c),
where M ′ ⊆ M is a submotif and c is a positive integer, such that (1) there exists an occurrence of M ′ in T (i) that matches vertex i, (2) the minimum number of connected components of an occurrence of M ′ in T (i) that matches vertex i is c. Table Y [i] stores all pairs (M ′ , c), where M ′ ⊆ M is a submotif and c is a positive integer, such that (1') there exists an occurrence of M ′ in T (i) that does not match vertex i, (2') the minimum number of connected components of an occurrence of M ′ in T (i) that does not match vertex i is c.

We first claim that both X[i] and Y [i] contain at most k q+1 pairs. Indeed, the number of submotifs M ′ ⊆ M is upper-bounded by k q and any occurrence of any submotif in any subtree of G results in at most k connected components. We now describe how to compute -in a bottom-up fashion -those two dynamic programming tables X and Y . Let i be an internal vertex of G and suppose that vertex i has s i sons in the subtree T (i) rooted at i, say {i 1 , i 2 , . . . , i si }. Notice that s i ≥ 1 since i is an internal vertex of G. The entries X[i] and Y [i] are computed thanks to two auxiliary tables W i and V i . Table W i contains s i entries, one for each son of vertex i in the subtree rooted at i, that are defined as follows:

∀ 1 ≤ j ≤ s i , W i [i j ] = {(M ′ , c, 1) : (M ′ , c) ∈ X[i j ]} ∪ {(M ′ , c, 0) : (M ′ , c) ∈ Y [i j ]}.
In other words, we merge X[i j ] and

Y [i j ] in W i [i j ],
differentiating the origin of a pair by means of a third element (an integer that is equal to 1 for X[i j ] and 0 for Y [i j ]). Clearly, each entry W i [i j ] contains at most 2k q+1 triples, and hence table W i on the whole contains at most 2 s i k q+1 ≤ 2 n k q+1 triples. Table V i also contains s i entries, one for each son of vertex i in the subtree rooted at i, that are computed as follows:

V i [i 1 ] = W i [i 1 ] and ∀ 2 ≤ j ≤ s i , V i [i j ] = W i [i j ] ∪ {(M ′ ∪ M ′′ , c ′ + c ′′ , r ′ + r ′′ ) ⊆ M × k × k : (M ′ , c ′ , r ′ ) ∈ W i [i j ] and (M ′′ , c ′′ , r ′′ ) ∈ V i [i j-1 ]}.
Each entry V i [i j ] contains at most k q+2 triples, and hence table V i on the whole contains at most

s i k q+2 ≤ n k q+2 triples. All the needed information is stored in V i [i si ],
and X[i] and Y [i] can be now computed as follows:

X[i] = {(M ′ , c -r + 1) : (M ′ , c, r) ∈ V i [i si ] and r > 0} Y [i] = {(M ′ , c) : (M ′ , c, 0) ∈ V i [i si ]}.
The two entries X[i] and Y [i] are next filtered according to the following procedure: for each submotif M ′ ⊆ M that occurs in at least one pair of

X[i] (resp. Y [i]), we keep in X[i] (resp. Y [i]) the pair (M ′ , c) with the minimum c.
The base cases, i.e., vertex i is a leaf, are defined as follows:

X[i] = {(λ(i), 1)} and Y [i] = ∅. In other words, X[i] contains exactly one pair (M ′ , c),
where M ′ consists of one occurrence of the color associated to vertex i, and Y [i] does not contain any pair. The solution for the Min-CC problem consists in finding a pair (M, c) in X or Y with minimum c. If such a pair cannot be found in any entry of both X and Y , then the motif M does not occur in the tree G.

Proposition 3. The Min-CC problem for trees is solvable in O(n 2 k 2(q+2) ) time, where n is the order of the target graph, k is the size of the motif M, and q is the number of distinct colors in M.

Proof. Let us consider any internal vertex i. For ease of exposition, we assume no pointer sharing in the implementation and thus consider that each pair or triple in any dynamic programming table is written in O(k) time. We first observe that the construction of the dynamic programming table W i can certainly be done in O(nk q+2 ) time. Second, the construction of the dynamic programming table

V i is done in O(nk 2(q+2) ) time. Finally, computing X[i] and Y [i] is done in O(nk q+2
) time, and so is the time to filter the dynamic programming tables. Therefore, the running time as a whole is in O(n 2 k 2(q+2) ).

The above-mentioned result is of interest in view of the fact that the Min-CC problem for trees parameterized by q is W[1]-hard [START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF].

A polynomial-time algorithm for paths with a bounded number of colors

We complement here the results of the two preceding subsections by showing that the Min-CC problem for paths is polynomial-time solvable in case the motif is built upon a fixed number of colors. Observe, however, that each color may still have an unbounded number of occurrences in the motif.

In what follows, we describe a dynamic programming algorithm for this case. Suppose the path G under study is such that V(G) = {1, 2, . . . , n} and E(G) = {{i, i + 1}|1 ≤ i < n}. The basic idea of our approach is as follows. Suppose we are left by the algorithm with the problem of finding an occurrence of a submotif M ′ ⊆ M in the subpath G ′ of G induced by {i, i + 1, . . . , j}, 1 ≤ i < j ≤ n. Furthermore, suppose that any occurrence of M ′ in G ′ results in at least k ′ connected components. This minimum number of occurrences k ′ can be computed as follows. Assume that we have found one leftmost connected component C left of the occurrence of M ′ in G ′ and let i 2 , i ≤ i 2 < j, be the rightmost (according to the natural order of the vertices) vertex of C left . Let M ′′ be the motif obtained from M ′ by subtracting to each color c ℓ ∈ C the number of occurrences of color c ℓ in the leftmost connected component C left . Then the occurrence of M ′ in G ′ is given by C left plus the occurrence of the motif M ′′ in the subpath G ′′ of G ′ induced by {i 2 + 1, i 2 + 2, . . . , j}, which results in k ′ -1 connected components. From an optimization point of view, the problem thus reduces to finding a subpath {i 1 , i 1 +1, . . . , i 2 }, i ≤ i 1 ≤ i 2 < j, such that the occurrence of the motif M ′′ modified according to the colors in {i 1 , i 1 + 1, . . . , i 2 } in the subpath induced by {i 2 + 1, i 2 + 2, . . . , j} results in a minimum number of connected components.

Let (G, M) be an instance of the Min-CC problem, where G is a (vertexcolored) path built upon the set of colors C, and let q = |C|. We denote by m i the number of occurrences of color c i ∈ C in M. Clearly, ci∈C m i = |M|. We now introduce our dynamic programming table T . Define T [i, j; p 1 , p 2 , . . . , p q ], 1 ≤ i ≤ j ≤ n and 0 ≤ p ℓ ≤ m ℓ for 1 ≤ ℓ ≤ q, to be the minimum number of connected components in the subpath of G that starts at node i, ends at node j and that covers p ℓ occurrences of color c ℓ , 1 ≤ ℓ ≤ q. The base conditions are as follows:

• for all 1 ≤ i ≤ j ≤ n, -T [i, j; 0, 0, . . . , 0] = 0 • for all 1 ≤ i ≤ n -T [i, i; p 1 , p 2 , . . . , p q ] = ∞ if 1≤ℓ≤q p ℓ > 1 -T [i, i; p 1 , p 2 , . . . , p q ] = ∞ if 1≤ℓ≤q p ℓ = 1 and ∃1 ≤ k ≤ q s.t. p k = 1 and λ(i) = c k -T [i, i; p 1 , p 2 , . . . , p q ] = 1 if 1≤ℓ≤q p ℓ = 1 and ∃1 ≤ k ≤ q s.t. p k = 1 and λ(i) = c k
The entry T [i, j; p 1 , p 2 , . . . , p q ] of the dynamic programming table T can be computed according to the following recurrence

T [i, j; p 1 , p 2 , . . . , p q ] = min i≤i1≤i2<j T [i 2 + 1, j; p ′ 1 , p ′ 2 , . . . , p ′ q ] + 1 (1)
where each p ′ ℓ ≥ 0 is equal to p ℓ minus the number of occurrences of color c ℓ in the subpath of G induced by the vertices {i

1 , i 1 + 1, . . . , i 2 }. The optimal solution is clearly stored in T [1, n; m 1 , m 2 , . . . , m q ].
We claim that our dynamic programming table T contains O(n q+2 ) entries. Indeed, there are q colors in M, each color c i ∈ C has at most n occurrences in G and we have O(n 2 ) subpaths in G to consider. We now turn to evaluating the time complexity for computing T [i, j; p 1 , p 2 , . . . , p q ]. Assuming each entry

T [i ′ , j ′ ; p ′ 1 , p ′ 2 , . . . , p ′ q ] with i ≤ i ′ ≤ j ′ ≤ j and |j ′ -i ′ | < |j -i| has already been computed, T [i, j; p 1 , p 2 , . . . , p q ] is obtained by taking a minimum number among O(|j -i + 1| 2 ) = O(n 2 )
numbers, and hence is O(n 2 ) time. We have thus proved the following.

Proposition 4. The Min-CC problem for paths is solvable in O(n q+4 ) time, where n is the number of vertices and q is the number of distinct colors in M.

As an immediate consequence of the above proposition, the Min-CC problem is polynomial-time solvable in case the motif M is built upon a fixed number of colors and the target graph G is a path.

Hardness of approximation for trees

We investigate in this section approximation issues for restricted instances of the Min-CC problem. Unfortunately, as we shall now prove, it turns out that, even if M is a set and G is a tree, the Min-CC problem cannot be approximated within ratio c log n for some constant c > 0, where n is the size of the target graph G. As a side result, we prove that the Min-CC problem is W[2]-hard when parameterized by the number of connected components of the occurrence of M in the target graph G.

At the core of our proof is an L-reduction [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF] from the Set-Cover problem. Let I be an arbitrary instance of the Set-Cover problem consisting of a universe set X(I) = {x 1 , x 2 , . . . , x n } and a collection of sets S(I) = S 1 , S 2 , . . . , S m , each over X(I). For each 1 ≤ i ≤ m, write t i = |S i | and denote by e j (S i ), 1 ≤ j ≤ t i , the j-th element of S i . For ease of exposition, we present the corresponding instance of the Min-CC problem as a rooted tree G. We construct the tree G as follows (see Figure 1). Define a root r and vertices S ′ 1 , S ′ 2 , . . . , S ′ m such that each vertex S ′ i is connected to the root r. For each S ′ i define the subtree G(S ′ i ) rooted at S ′ i as follows: each vertex S ′ i has a unique child S i and each vertex S i has children e 1 (S i ), e 2 (S i ), . . . , e ti (S i ). The set of colors C is defined as follows:

C = {c(S i ) : 1 ≤ i ≤ m} ∪ {c(x j ) : 1 ≤ j ≤ n} ∪ {c(r)}. The coloring mapping λ : V(G) → C is defined by: λ(S i ) = λ(S ′ i ) = c(S i ) for 1 ≤ i ≤ m, λ(x j ) = c(x j ) for 1 ≤ j ≤ n and λ(r) = c(r). The motif M is the set defined as follows: M = {c(S i ) : 1 ≤ i ≤ m} ∪ {c(x i ) : 1 ≤ i ≤ n} ∪ {c(r)}.
Proposition 5. For any instance I of the Set-Cover problem, there exists a solution of size h for I ( i.e., a subset S ⊆ S(I), |S| = h, such that Si∈S S i = X), if and only if there exists an occurrence of M in G that results in h + 1 connected components.

Proof. The "only if " part is obvious, and we only prove the "if " part.

Suppose thus that there exists at least one occurrence of M in G that results in h + 1 connected components. We first make the following important observation: for any occurrence V of M in G, (i) V contains r, (ii) V contains either S i or S ′ i , 1 ≤ i ≤ m, and (iii) V contains exactly one vertex colored with color c(x j ), 1 ≤ j ≤ n. Now, denote by V(M) the set of all occurrences of M in G that result in at most h + 1 connected components. For each V ∈ V(M), define ℓ(V ) to be the number of connected components induced by V that are solely composed of a leaf of G, i.e., a vertex associated to an element of the universe set X(I). We claim that there exists V * ∈ V(M) such that ℓ(V * ) = 0. Indeed, suppose for the sake of contradiction that ℓ(V * ) > 0. Then there exists a connected component induced by V * that is composed of solely a leaf in G, say x j . Write S ⊆ S(I) the set of all subsets that contain the element x j in the instance of the Set-Cover problem. If V * contains a vertex associated to an element of S we are done. Hence we may now assume that V * does not contain a vertex associated to an element of S. Then it follows that V * contains vertex S ′ i , for each S i ∈ S. Consider the subset V ′ ⊆ V(G) which is identical to V except that we add the father of x i in G, say S f , and delete the vertex S ′ f . It is easily seen that V ′ is an occurrence of M in G that results in at most h + 1 connected components and ℓ(V ′ ) < ℓ(V * ). This is the desired contradiction, and hence no connected component of the occurrence of M in G is solely composed of a leaf. Then it follows that all the elements of the universe set are covered by h sets in S(I), which concludes the proof.

r S ′ 1 S1 e1(S1) e2(S1) et 1 (S1) S ′ 2 S2 e1(S2) e2(S2) et 2 (S2) S ′ m Sm e1(Sm)e2(Sm) et m (Sm)
It is easily seen that the above reduction is an L-reduction [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF]. It is known that the Set-Cover problem cannot be approximated within ratio c log n for some constant c > 0 [START_REF] Raz | A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP[END_REF]. Then it follows that there exists a constant c ′ > 0 such that the Min-CC problem for trees cannot be approximated within performance ratio c ′ log n, where n is the number of vertices in the target graph.

As a side result, we also observe that the above reduction is a parameterized reduction. Since the Set-Cover problem is W[2]-hard when parameterized by the size of the solution [START_REF] Paz | Non deterministic polynomial optimization problems and their approximations[END_REF], the following result holds.

Corollary 2. The Min-CC problem for trees is W[2]-hard when parameterized by the number of connected components of the occurrence of the motif in the graph.

An exact algorithm for trees

We proved in Section 3.2 that the Min-CC problem for trees is solvable in O(n 2 k (q+1) 2 +1 ) time, where n is the order of the target tree, k is the size of the motif M and q is the number of distinct colors in M. We propose here a new algorithm for this special case, which turns out not to be a fixed-parameter algorithm, but has a better running time in case the size k of the motif is not that small compared to the order n of the target graph. More precisely, we give an algorithm for solving the Min-CC problem for trees that runs in O(n 2 2 2n/3 ), where n is the order of the target tree.

Let T be the target tree. For any vertex x of T , denote by T (x) the subtree of T rooted at x. The first step of our algorithm is to split the target tree in a balanced way, i.e., in such a way that T is rooted at a vertex r having children, r 1 , r 2 , . . . , r h such that none of the trees T (r i ), 1 ≤ i ≤ h, has order greater than ⌈ n 2 ⌉. Such a root vertex is called a centroid, and it can be shown that every tree has either one centroid or two (in the latter case, the two centroids are connected by an edge) [START_REF] Harary | Graph theory[END_REF]. Goldman [START_REF] Goldman | Optimal center location in simple networks[END_REF] and Megiddo et al. [START_REF] Megiddo | An o(n log 2 n) algorithm for the k-th longest path in a tree with applications to location problems[END_REF] proposed linear algorithms for finding the centroid of a tree.

From now on, suppose the tree is rooted at a centroid node r. We show how to construct two disjoint subsets R 1 and R 2 of r 1 , r 2 , . . . , r h such that

1 3 |T | ≤ ri∈R1 |T (r i )| ≤ 1 2 |T | , and
1 2 |T | ≤ ri∈R2 |T (r i )| ≤ 2 3 |T | Let r i such that |T (r i )| is maximum. If |T (r i )| ≥ 1 3 |T |, then T (r i ) is in R 1 and all the other subtrees T (r j ) are added to R 2 . If |T (r i )| ≤ 1 3 |T |, then perform the following procedure: starting from r 1 , add elements to R 1 until |R 1 | ≥ 1 3 |T |. Thus consider the last element r ℓ added to R 1 . Observe that |T (r ℓ )| ≤ 1 3 |T |, since the maximum element has size less than 1 3 |T |. Moreover, |R 1 | -|T (r ℓ )| ≤ 1 3 |T |, otherwise we would have stopped before adding T (r ℓ ) to R 1 . It follows that 1 3 |T | ≤ |R 1 | ≤ 2 3
|T |, and the same holds for R 2 . Without loss of generality, we can assume that R 1 is the minimum of sets R 1 , R 2 .

Given V ′ ⊆ V , we say that V ′ does not violate M if the multiset of colors C(V ′ ) is a subset of M. Given a subtree T ′ of T , we define a partial solution F for the Min-CC problem over then instance (T ′ , M) as a set of connected components of T ′ that does not violate the multiset M.

Let S be a partial solution for the Min-CC problem over the instance (R i , M), i ∈ {1, 2}. Thus, S consists of a set of connected components of R i . This set of connected components can be obtained as follows: determine the subset V ′ of vertices of R i that do not belong to S and remove V ′ and the edges incident to V ′ from R i . It follows that the set of partial solutions for the Min-CC problem over then instance (R i , M) can be computed by deleting a (possibly empty) subset of vertices of R i such that the connected components obtained do not violate M.

We denote by S 1 and S 2 the sets of partial solutions for the Min-CC problem over the instances (R 1 , M) and (R 2 , M), respectively. In what follows, we describe how the algorithm computes an optimal solution for the entire tree T starting from the partial solutions for (R 1 , M) and (R 2 , M). We need the following definition.

Definition 1. Let S be a feasible solution for the Min-CC problem over the instance (T, M). The restriction of S to a subtree R 1 (resp. R 2 ) consists of the connected components of S having all the vertices in R 1 (resp. R 2 ).

It is easy to see that the following property holds for each feasible solution for the Min-CC problem. Proposition 6. Let S be a feasible solution for the Min-CC problem over the instance (T, M). Then, S restricted to R 1 is a partial solution over the instance (R 1 , M), and S restricted to R 2 is a partial solution over the instance (R 2 , M).

For each partial solution S P over the instance (R i , M), with i ∈ {1, 2}, let C(S P ) be the multiset of colors covered by S P . Recall that the multiset M is built over the set of colors {c 1 , c 2 , . . . , c q }. Let f i be a partial solution having occurrences o i j of each color c j . We represent a multiset as a vector

[o i 1 , o i 2 , . . . , o i q ]
. Moreover, since the algorithm needs to distinguish whether a solution contains the root r of the tree T , the algorithm adds a bit at position q + 1 of the vector o i for each partial solution f i . Now o i q+1 = 1 if f i contains r, else o i q+1 = 0. Observe that the we can order the partial solution of a set (for example S 1 ) on the basis of the covered multisets. The algorithm orders the set of partial solutions S 1 on the basis of their covered multisets. Comparing two multisets requires O(q) time. Hence, the solutions of S 1 can be ordered in time

O(n2 n/2 log 2 n/2 ) = O(n 2 2 n/2 ).
Assume that the partial solutions of S 1 are ordered on the basis of their covered multisets. In what follows we will show how the algorithm rearranges the data in order to compute an optimal solution. Proposition 7. Let S be a solution for the Min-CC problem over the instance (T , M). Observe that if r ∈ S, then the two restrictions S a ∈ S 1 and S b ∈ S 2 both contain r; if r / ∈ S, then the two restrictions S a ∈ S 1 and S b ∈ S 2 both do not contain r.

From the above property, it follows that we can compute a solution S for the whole tree, by merging two solutions of S 1 and S 2 that both contain r, if r ∈ S, or by merging two solutions of S 1 and S 2 that both do not contain r, if r / ∈ S. It follows that combining two partial solutions t 1 ∈ S 1 and t 2 ∈ S 2 , we can restrict ourselves to two kinds of solutions of S 2 for each covered multiset CM:

1. type 1 solution covering multiset CM: a solution that covers CM with the minimum number of connected components and that contains r ; 2. type 2 solution covering multiset CM: a solution that covers CM with the minimum number of connected components and that does not contain r.

Furthermore, next we have to rearrange the ordered solutions of S 1 such that, for each vector, there exists at most one solution associated to that vector. Note that this implies that there exists at most two partial solutions, a solution of type 1 and a solution of type 2, that cover a certain multiset of colors. Recall that for each multiset CM, the solution of type 1 that covers CM is after the solution of type 2 that covers CM, since the last bit is 1 for type 1 solutions and is 0 for type 2 solutions. The rearrangement of S 1 can be easily computed in time O(n2 n/2 ), since each comparison takes O(n) time and since S 1 is ordered.

Observe that the algorithm rearranges the set S 1 such that S 1 contains only solutions of type 1 or type 2. This implies that, for each possible o i , there exists at most one solution associated to this vector. If such a solution exists, it will be a solution that contains the minimum number of connected components among the solutions associated to vertex o i . Now, in order to obtain a solution for T from the set of partial solutions S 1 and S 2 , from Proposition 7 it follows that for each solution t 1 i ∈ S 2 , if t 1 i contains r, we must look for a solution of type 1 (i.e., that contains r) in the rearrangement of S 1 that covers Mc(t 1 i ) + c(r). Similarly, if t 1 i does not contain r, we must look for a solution of type 2 that covers Mc(t 1 i ). If such a solution t 2 j exists, we say that t 2 j completes t 1 i . In the first case, the number of connected components of the solution is

|t 1 i | + |t 2 j | -1, since the connected component containing root r is counted both in t 1
i and in t 2 j . In the second case the number of connected components of the solution is

|t 1 i | + |t 2 j |.
Given a partial solution t of S 2 , we are able to find a partial solution t ′ that completes t in time logarithmic in the size of S 1 .

Maximizing the Number of Colors: the Maximum Motif problem

In this section, we focus on the Maximum Motif problem. We first give in Section 4.1 several results showing that the Maximum Motif problem is hard to approximate. Section 4.2 gives two exact (thus exponential) algorithms for trees. Finally, Section 4.3 gives two FPT algorithms: one for trees, the other for general graphs.

Hardness of approximation

We first prove here APX-hardness of the Maximum Motif problem. Recall that, given a graph G = (V, E), the maximum independent set problem (Independent Set) seeks for a maximum cardinality subset V ′ ⊆ V such that no two vertices in V ′ are joined by an edge. The Independent Set problem is known to be APX-hard even when restricted to cubic graphs [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF].

Proposition 8. The Maximum Motif problem is APX-hard even if the motif is colorful and the target graph is a tree with maximum degree 3.

Proof. The proof is by L-reduction from the Independent Set problem for cubic graphs. Let G = (V, E) be an instance of the Independent Set problem for cubic graphs. Write V(G) = {v 1 , v 2 , . . . , v n } and E(G) = {e 1 , e 2 , . . . , e m }. For each v i ∈ V , let us denote by E(v i ) the three edges of E(G) that are incident to v i . Furthermore, denote by e(v i , j) the j-th edge of E(v i ), 1 ≤ j ≤ 3, where the order is arbitrary. We show how to construct the corresponding instance of the Maximum Motif problem. This instance consists of a vertex-colored tree T = (V T , E T ) of maximum degree 3 and a colorful motif M. The tree T is defined as follows:

V T ={a i , b i , x i,I , x i,C , l i : 1 ≤ i ≤ n} ∪ {d i,j , f i,j , e i,j : 1 ≤ i ≤ n ∧ 1 ≤ j ≤ 3} E T ={{a i , b i }, {b i , x i,I }, {b i , x i,C }, {x i,C , d i,1 }, {x i,I , f i,1 } : 1 ≤ i ≤ n} ∪ {{a i , a i+1 } : 1 ≤ i < n} ∪ {{d i,j , d i,j+1 }, {f i,j , f i,j+1 } : 1 ≤ i ≤ n ∧ 1 ≤ j < 3} ∪ {{d i,j , e i,j } : 1 ≤ i ≤ n ∧ 1 ≤ j ≤ 3}{{f i,3 , l i } : 1 ≤ i ≤ n}
Refer to Figure 2 for a schematic representation of the tree T . Vertex a i ,

1 ≤ i ≤ n, is colored c(a i ), vertex b i , 1 ≤ i ≤ n, is colored c(b i
), the two vertices x i,C and x i,I , 1 ≤ i ≤ n, are colored c(x i ), vertex l i , 1 ≤ i ≤ n, is colored c(l i ), the two vertices d i,j and f i,j , 1 ≤ i ≤ n and 1 ≤ j ≤ 3, are colored c(i, j), and vertex e i,j , 1 ≤ i ≤ n and 1 ≤ j ≤ 3, is colored c(e k ), where e k = e(v i , j). Write C for the set of all colors that occur in T (notice that each color in C occurs at most twice in T ). The motif M is defined by M = C, and is hence colorful. We claim that there exists an independent set of size k in G if and only if there exists a submotif of size 6n + m + k that occurs in T .

Suppose there exists an independent set V ′ of size k in G. For each e = {v i , v j } ∈ E, define min(e) to be

min(e) = v i if (v j ∈ V ′ ) ∨ (v i / ∈ V ′ ∧ v j / ∈ V ′ ∧ i < j), v j otherwise. Consider the subset V ′ T ⊆ V T defined by V ′ T ={a i , b i : 1 ≤ i ≤ n} ∪ {x i,I , f i,1 , f i,2 , f i,3 , l i : v i ∈ V ′ } ∪ {x i,C , d i,1 , d i,2 , d i,3 : v i / ∈ V ′ } ∪ {e i,j : e ∈ E ∧ min(e) = e(v i , j)} T a 1 b 1 x 1,C d 1,1 e 1,1 d 1,2 e 1,2 d 1,3 e 1,3 x 1,I f 1,1 f 1,2 f 1,3 l 1 a 2 b 2 x 2,C d 2,1 e 2,1 d 2,2 e 2,2 d 2,3 e 2,3 x 2,I f 2,1 f 2,2 f 2,3 l 2 a n b n x n,C d n,1 e n,1 d n,2 e n,2
d n,3 e n,3

x n,I

f n,1 f n,2
f n,T,3 Observe that V ′ T induces a connected component in T . Furthermore, C(V ′ T ) = M ′ ⊆ M, contains all colors from M except those c(l i ) with v i / ∈ V ′ . Conversely, suppose that there exists a motif M ′ ⊂ M, |M ′ | ≥ 7, that occurs in T . Fix one occurrence of M ′ in T and write V ′ T ⊆ V T for the vertices of T involved in this occurrence. Without loss of generality, suppose that T ′ is maximal for inclusion (adding any adjacent vertex to T ′ results in a subtree that is not an occurrence of a submotif of M). Since |M ′ | ≥ 7, we can assume that at least one of a i and b i belongs to M ′ . Furthermore, observe that a i , b i ∈ V ′ T , 1 ≤ i ≤ n, since adding any of these missing vertices would result in a larger connected component T ′′ of T , such that C(T ′′ ) ⊆ M, thereby contradicting the maximality of T ′ . Then it follows that c(a

l n
i ), c(b i ) ∈ M ′ , 1 ≤ i ≤ n. Moreover, since M is colorful, V ′
T contains at most one of x i,C and x i,I , 1 ≤ i ≤ n; they indeed both have the same color. Therefore, by the maximality of T ′ , V ′ T contains exactly one of x i,C and x i,I , 1 ≤ i ≤ n, and hence M ′ contains the color c(x i ), 1 ≤ i ≤ n. Pursuing our maximality argument, if

x i,C ∈ V ′ T then V ′
T also contains the three vertices d i,j , 1 ≤ i ≤ n and 1 ≤ j ≤ 3, and if x i,I ∈ V ′ T then V ′ T also contains the three vertices f i,j , 1 ≤ i ≤ n and 1 ≤ j ≤ 3. Therefore, M ′ contains the colors c(i, j), 1 ≤ i ≤ n and 1 ≤ j ≤ 3. In case

x i,I , f i,1 , f i,2 , f i,3 ∈ V ′ T , 1 ≤ i ≤ n, l i ∈ V ′
T , and hence M ′ contains in addition color c(l i ), 1 ≤ i ≤ n. We now claim that we may assume that c(e) ∈ M ′ for all e ∈ E, i.e., submotif M ′ contains the color associated to each edge of G. Indeed, suppose that for some color c(e) ∈ M, say e = {v i , v j }, T ′ has no vertex colored c(e), i.e., c(e) / ∈ M ′ . Then, by the maximality of T ′ (and M ′ ), it follows that {x i,I , f i,1 , f i,2 , f i,3 , l i } ⊆ V ′ T and {x j,I , f j,1 , f j,2 , f j,3 , l j } ⊆ V ′ T , and hence that {x

i,C , d i,1 , d i,2 , d i,3 } ∩ V ′ T = ∅ and {x j,C , d j,1 , d j,2 , d j,3 } ∩ V ′ T = ∅. Therefore, V ′′ T = (V ′ T -{x i,I , f i,1 , f i,2 , f i,3 , l i }) ∪ {x i,C , d i,1 , d i,2 , d i,3
} ∪ e i,p , with c(e i,p ) = c(e), induces a subtree in T , and this subtree is an occurrence of M ′′ = (M ′ -{c(l i )}) ∪ {c(e)}. Applying the above procedure will eventually result in a submotif that contains the color associated to each edge of G. It follows that {v i : x i,C ∈ V ′ T } is a vertex cover of G, and hence {v i : x i,I ∈ V ′ T } is an independent set in G.

We have thus shown that there is an independent set of size k in G if and only if there exists a submotif of size 6n + m + k that occurs in T . But G is a cubic graph, and hence k ≥ n 4 and m = 3n 2 . Then it follows that the described reduction is indeed an L-reduction [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF] from the Independent Set problem for cubic graphs to the Maximum Motif problem for trees, which proves the proposition.

We now strengthen the inapproximability of the Maximum Motif problem for trees and colorful motifs. More precisely, we show that, for any constant δ < 1, the Maximum Motif problem cannot be approximated within factor 2 log δ n in polynomial-time unless NP ⊆ DTIME[2 poly log n ]. The proof is by the self-improvement technique (see for example [START_REF] Hein | On the complexity of comparing evolutionary trees[END_REF][START_REF] Jiang | On the approximation of shortest common supersequences and longest common subsequences[END_REF][START_REF] Karger | On approximating the longest path in a graph[END_REF]). For the sake of clarity, let us introduce the Maximum Level Motif problem which is the restriction of the Maximum Motif problem to colorful motifs and rooted trees in which two vertices can have the same color only if they are at the same level (i.e., at the same distance to the root) in the target tree.

First, we show the following easy lemma that will prove useful in the sequel. Proof. Let T ′ = (V ′ , E ′ ) be a solution for the Maximum Level Motif problem for instance I, and assume that T ′ does not contain the root r of T . Notice that T ′ must be a rooted subtree of T , and let y ∈ V ′ be the root of T ′ . Now consider the unique path P = (r, x ′ 1 , . . . , x ′ p = y), from the root r to y. Two vertices x ′ i and x ′ j of P , 1 ≤ i = j ≤ p, have distinct colors, since they belong to different levels of T . Moreover, each vertex x ′ i , with 1 ≤ i ≤ p -1, has a distinct color from each vertex v ∈ V ′ , since vertices x ′ i and v belong to different levels of T . Define T ′′ as the subtree of T induced by the set of vertices

V ′′ = V ′ ∪ p-1 i=1 x i .
Notice that T ′′ contains the root r of T , and by construction

|V ′′ | ≥ |V ′ |.
It can also be easily seen that Proposition 8 can be modified to prove the following result (this result is indeed is needed for proving, latter, a stronger inapproximabilty result for the Maximum Motif problem). Proposition 9. The Maximum Level Motif problem is APX-hard.

Proof. We prove that the problem is APX-hard by modifying the L-reduction for the Maximum Motif problem on bounded tree presented in Proposition 8. Let G = (V, E) be an instance of the Independent Set problem on cubic graph. Write V(G) = {v 1 , v 2 , . . . , v n } and E(G) = {e 1 , e 2 , . . . , e m }. For each v i ∈ V , let us denote by E(v i ) the three edges of E that are incident to v i . Furthermore, denote by e(v i , j) the j-th edge of E(v i ), 1 ≤ j ≤ 3, where the order is arbitrary. We now show how to construct the corresponding instance of the Maximum Level Motif problem. This instance consists of a rooted vertex-colored tree T = (V T , E T ) and a colorful motif M.

The tree T is defined as follows:

V T ={r} ∪ {b i , x i,I , x i,C , l i : 1 ≤ i ≤ n} ∪ {e i,j : 1 ≤ i ≤ n ∧ 1 ≤ j ≤ 3} E T ={{r, b i }, {b i , x i,I }, {b i , x i,C }, : 1 ≤ i ≤ n} ∪ {{x i,C , e i,j } : 1 ≤ i ≤ n ∧ 1 ≤ j ≤ 3} ∪ {{x i,I , l i } : 1 ≤ i ≤ n} Moreover, we root T at r. Vertex r is colored c(r), vertex b i , 1 ≤ i ≤ n, is colored c(b i ), the two vertices x i,C and x i,I , 1 ≤ i ≤ n, are colored c(x i ), vertex l i , 1 ≤ i ≤ n, is colored c(l i ), vertex e i,j , 1 ≤ i ≤ n and 1 ≤ j ≤ 3, is colored c(e k )
, where e k = e(v i , j). Write C for the set of all colors that occur in T (notice that each color in C occurs at most two times in T The motif M is defined by M = C, and is hence colorful.

First, observe that this is an instance of the Maximum Level Motif problem. Indeed, the tree T is rooted, has 4 levels and all the leaves are at level 4. Two vertices have the same color either if they both are at level 3, i.e., a pair (x i,C , x i,I ), or if they are both at level 4, i.e., they are leaves associated to the same edge e k .

In what follows, we show that, given a cubic graph G, there exists a solution of cardinality k for the Independent Set problem on G iff there exists a solution for the Maximum Level Motif problem, of size 1 + 2n + k + m, on the instance (T, M) built from G.

Let V ′ ⊆ V be a solution for the Independent Set problem on G, such that |V ′ | = k. We define a solution T ′ for the Maximum Level Motif problem on (T, M) as follows. Consider the subset V ′ T ⊆ V T defined as by

V ′ T ={r} ∪ {b i : 1 ≤ i ≤ n} ∪ {x i,I , l i : v i ∈ V ′ } ∪ {x i,C : v i / ∈ V ′ } ∪ {e i,j : e ∈ E ∧ min(e) = e(v i , j)}.
It is easy to see that

V ′ T induces a subtree T ′ in T . Furthermore, C(V ′ T ) = M ′ ⊆ M is defined by deleting in M every color c(l i ) such that v i / ∈ V ′ ,

and it can be seen by definition of

V ′ T that |M ′ | = 1 + 2n + k + m. Conversely, let T ′ = (V ′ T , E ′ T ) be a solution for the Maximum Level Motif problem, where |C(V ′ T )| = 1 + 2n + k + m. Notice that C(V ′ ) = M ′ ⊆ M.
Without loss of generality, suppose that T ′ is maximal for inclusion (i.e., adding any adjacent vertex to T ′ results in a submotif that does not occur in T ). By Lemma 4, we can assume that r ∈ V ′ T , hence M ′ contains color c(r). Furthermore, notice that b i ∈ V ′ T , 1 ≤ i ≤ n, since adding any of these missing vertices would result in a larger connected component T ′′ of T , such that C(T ′′ ) ⊆ M, thereby contradicting the maximality of T ′ . Then it follows that c(b i ) ∈ M ′ , 1 ≤ i ≤ n. Therefore, still by the maximality, V ′ T contains exactly one of x i,C and x i,I , 1 ≤ i ≤ n, and hence M ′ contains color c(x i ), 1 ≤ i ≤ n. Pursuing our maximality argument, if

x i,C ∈ V ′ T then in case x i,I ∈ V ′ T , 1 ≤ i ≤ n, l i ∈ V ′
T , and hence M ′ contains in addition color c(l i ), 1 ≤ i ≤ n. Furthermore, we may assume that c(e) ∈ M ′ for all e ∈ E, i.e., submotif M ′ contains the color associated to each edge of G. Indeed, suppose that there is no vertex associated to color c(e), say e = {v i , v j }, in T ′ , that is c(e) is not part of M ′ . Then, by maximality of T ′ and M ′ , it follows that {x i,I , l i } ⊆ V ′ T and {x j,I , l j } ⊆ V ′ T , and hence that

x i,C , x j,C / ∈ V ′ T . Therefore, V ′′ T = V ′ T -{x i,I , l i } ∪ {x i,C
} ∪ e i,p , with c(e i,p ) = c(e), induces a subtree in T and C(V ′′ T ) = M ′′ = (M ′ -{c(l i )})∪{c(e)}. Applying the above procedure will eventually result in a submotif that contains the color associated to each edge of G.

It follows that {v i : x i,C ∈ V ′ T } is a vertex cover of G, and hence {v i :

x i,I ∈ V ′
T } is an independent set in G. Moreover, since we have characterized precisely which vertices are in V ′ T and since |M ′ | = 1 + 2n + k + m, a simple counting argument allows us to conclude that |{v i :

x i,I ∈ V ′ T }| = k. Finally, since G is a cubic graph, we have k ≥ n
4 and m = 3n 2 . It then follows that the above reduction is indeed an L-reduction [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF] from the Independent Set problem for cubic graphs to the Maximum Level Motif problem for trees, which proves the proposition.

Aiming at applying the self-improvement technique we need to precisely define the product of two instances I 1 and I 2 of the Maximum Level Motif problem. Let I 1 = (T 1 , M 1 ) and I 2 = (T 2 , M 2 ) be two instances of the Maximum Level Motif problem, where T 1 = (V 1 , E 1 ) and T 2 = (V 2 , E 2 ) are vertex-colored trees rooted at r 1 and r 2 , respectively. The product I 1 × I 2 is defined to be the instance (T 1,2 , M 1,2 ) where

T 1,2 = (V 1,2 , E 1,2 ) is a rooted tree defined by V 1,2 = {v i (v j ) : v i ∈ V 1 ∧ v j ∈ V 2 } and E 1,2 = {{v i (v j,1 ), v i (v j,2 )} : {v j,1 , v j,2 } ∈ E 2 ∧ v i ∈ V 1 } ∪ {{v i (r 2 ), v j (r 2 )} : {v i , v j } ∈ E 1 }, and M 1,2 is a motif defined by M 1,2 = {c 1 (c 2 ) : c 1 ∈ M 1 ∧ c 2 ∈ M 2 }. The tree T 1,2 is rooted at vertex r 1 (r 2 ). Informally, T 1,2 is obtained by replacing each vertex v i ∈ V 1 by
a copy of T 2 , connecting these copies through their roots. As for the color of each vertex of

T 1,2 , if v i ∈ V i is colored c i and v j ∈ V j is colored c j then vertex v i (v j ) ∈ T 1,2 is colored c i (c j ). Denote by v i [T 2 ] the subtree of T 1,2 isomorphic to T 2 rooted at v i (r 2 ). Write V 1,2,r = {v i (r 2 ) : v i ∈ V 1 }. Observe that, by construction, the subtree of T 1,2 induced by V 1,2,r is isomorphic to T 1 . Lemma 5. Let I 1 = (T 1 , M 1 ) and I 2 = (T 2 , M 2 ) be two instances of the Max- imum Level Motif problem. Then I 1 × I 2 is an instance of the Maximum Level Motif problem. Proof. Write T 1 = (V 1 , E 1 ) and T 2 = (V 2 , E 2
) and assume that T 1 and T 2 are rooted at r 1 and r 2 , respectively. Let

I 1 × I 2 = (T 1,2 , M 1,2 ) and write T 1,2 = (V 1,2 , E 1,2 ). First, we note that T 1,2 is a tree. Indeed, T 1,2 [V 1,2,r ] is isomorphic to T 1 and each vertex in V 1,2 -V 1,2,
r belongs to a subtree rooted at some v i (r 2 ) ∈ V 1,2,r . Furthermore, T 1,2 is rooted by definition. Now, we show that two vertices of T 1,2 have the same color only if they are at the same level in T 1,2 . Let u 1 (u 2 ) and v 1 (v 2 ) be two vertices of T 1,2 such that c(u

1 (u 2 )) = c(v 1 (v 2 )) = c a (c b ). If u 1 = v 1 ,
we are done. Hence, we may now assume u 1 = v 1 . Therefore, we must have c(u 1 ) = c(v 1 ) = c a . Furthermore, observe that, by construction, all vertices in

u 1 [T 2 ] and v 1 [T 2 ] are colored c a (c x ) for some color c x ∈ M. Consider the subtree T 1,2 [V 1,2,r ] induced by V 1,2,r . Since T 1,2 [V 1,2,r ] is isomorphic to T 1 , each vertex x i (r 2 ) ∈ V 1,2,r has color c(x i )(c(r 2 )). Now, since all vertices of u 1 [T 2 ] and v 1 [T 2 ] are colored c a (c x ), it follows that the root x i (r 2 ) of u 1 [T 2 ] and the root x j (r 2 ) of v 1 [T 2 ] have the same color c a (c(r 2 )).
Then it follows that x i (r 2 ) and x j (r 2 ) must be at the same level l 1 of T 1,2 , since they both belong to V 1,2,r and T 1,2 [V 1,2,r ] is isomorphic to T 1 , where x i and x j must be both at level l 1 . Now, consider the subtrees

u 1 [T 2 ] and v 1 [T 2 ] isomorphic to T 2 . Recall that vertices u 1 (u 2 ) and v 1 (v 2 ) of T 1,2 are both colored c a (c b ). As previously ob- served, all vertices u 1 (u j ) in u 1 [T 2 ] and v 1 [T 2 ] are associated to colors c a (c(u j )) for some u j ∈ V 2 . Since I 2 = (T 2 , M 2 ) is an instance of the Maximum Level Motif problem, vertices u 2 and v 2 must be at the same level l 2 in T 2 since c(u 2 ) = c(v 2 ) = c b . Then, since u 1 [T 2 ] and v 1 [T 2 ] are both isomorphic to T 2 , u 1 (u 2 ) and v 1 (v 2 ) are both at level l 2 in u 1 [T 2 ] and v 1 [T 2 ], respectively. It follows that both u 1 (u 2 ) and v 1 (v 2 ) are at level l 1 + l 2 in T 1,2 .
Finally, consider the motif M 1,2 . By construction, M 1,2 is a set, hence it is colorful.

For any instance I of the Maximum Level Motif problem, write I 1 = I and I k = I × I k-1 for all k ≥ 2. According to Lemma 5, it follows by induction that I k , k ≥ 1, is an instance of the Maximum Level Motif problem. Lemma 6. Let I = (T, M) be an instance of the Maximum Level Motif problem and let T S be a solution for I. Then there exists a solution T S k for instance

I k such that |T S k | ≥ |T S | k , for all k ≥ 1.
Proof. We prove the lemma by induction on k. The result is certainly valid for k = 1. Let k ≥ 2 and assume that the lemma holds for all 1 ≤ k ′ ≤ k -1. Let T S = (V T S , E T S ) be a solution for the Maximum Level Motif problem for instance I, with V T S = {v 1 , v 2 , . . . , v z }. Observe that T S is a subtree of T and that all vertices in V T S have distinct colors since M is colorful. By Lemma 4, we can assume that the root r of T is part of V T S . We now construct a solution T S k for instance I k as follows.

First, consider the subtree of T k which consists of the set V T S ,r ′ of vertices v 1 (r ′ ), v 2 (r ′ ), . . . , v z (r ′ ), where each v i (r ′ ) is the root of a subtree of T k isomorphic to T k-1 . Observe that, by construction, the set of vertices

V T S ,r ′ induces a subtree T k [V T S ,r ′ ] of T k . Since vertices v 1 , v 2 , . . . , v z all have distinct colors in T , then it follows that v 1 (r ′ ), v 2 (r ′ ), . . . , v z (r ′ ) have distinct colors as well. Let v i [T k-1 ] and v j [T k-1 ], 1 ≤ i < j ≤ z, be two subtrees of T isomorphic to T k-1 rooted at v i (r ′
) and v j (r ′ ), respectively. Observe that any two vertices x ∈ v i [T k-1 ] and y ∈ v j [T k-1 ] cannot have the same color, since c(v i ) = c(v j ). Now, consider a subtree rooted at v i (r ′ ), with 1 ≤ i ≤ z. By the induction hypothesis, there is a solution T S k-1 of the Maximum Level Motif problem over instance

I k-1 = (T k-1 , M k-1 ), such that |T S k-1 | ≥ |T S | k-1 .
Notice that, by Lemma 4, we can assume that T S k-1 contains the root of T k-1 . Now we build solution T S k , by adding, for each

v i (r ′ ), 1 ≤ i ≤ z, a subtree of v i [T k-1 ] isomor- phic to T S k-1 . Since T k
S consists of |T S | such subtrees, it follows immediately that the inequality holds.

Finally, notice that the solution we have built is a feasible solution for the Maximum Level Motif problem for instance I k . First, T k S is connected by construction. Furthermore, each vertex of T k S has a distinct color. Indeed, we have shown that this holds for any two vertices that are not in the same subtree v i [T k-1 ]. By the induction hypothesis, since T S k-1 is a feasible solution for the Maximum Level Motif problem over instance I k-1 , it follows that two vertices that belong to the same subtree v i [T k-1 ] must have distinct colors. Lemma 7. Let T S k be a solution for the Maximum Level Motif problem for instance

I k = (T k , M k ). Then, one can compute in polynomial-time a solution T S for instance I such that |T S | k ≥ |T S k |.
Proof. We prove the lemma by induction on k. The result is certainly valid for k = 1. Let k ≥ 2 and assume that the lemma holds for each 1

≤ k ′ ≤ k -1. Let T S k = (V S k , E S k
) be a solution for the Maximum Level Motif problem over instance I k . According to Lemma 4, there is no loss of generality in assuming that the root of T k is part of V S k . It follows that V S k contains vertices x 1 , . . . x p of T k , with p ≤ |T |, such that at least one vertex in subtree

x i [T k-1 ] isomorphic to T k-1 belongs to T S k . For each x i , 1 ≤ i ≤ p, denote by x i [T k-1 S ] the subtree of x i [T k-1 ] which is part of T S k . Let x max [T k-1 S
] be a subtree of maximum size among the subtrees

x i [T k-1 S ], 1 ≤ i ≤ p. Let T k-1 S be a subtree of T k-1 isomorphic to x max [T k-1 S ]. Notice that T k-1
S is a solution of the Maximum Level Motif problem over instance I k-1 . By the induction hypothesis, we can compute in polynomial time a solution T S ′ over the instance I such that

|T S ′ | k-1 ≥ |x max [T k-1 S ]|. Denote now by T p the subtree of T S k induced by {x 1 . . . x p }. Now |T S k | ≤ |T p ||x max [T k-1 S ]| ≤ |T p ||T S ′ | k-1 . If |T S ′ | ≥ |T p | , then T S = T ′
S and the lemma holds, since

|T S ′ ||T S ′ | k-1 ≥ |T p ||T S ′ | k-1 | ≥ |T S k |. Otherwise, if |T S ′ | < |T p |, let T S be the subtree of T isomorphic to T p . It follows that |T p ||T p | k-1 > |T p ||T S ′ | k-1 ≥ |T S k |.
Observe that T S is a feasible solution of the Maximum Level Motif problem over instance I. In the former case, when T S is equal to T S ′ , T S is feasible by the induction hypothesis. Consider the latter case, when T S is equal to T p . Let x 1 , . . . x p be the vertices of T p . Vertex x i of T p , 1 ≤ i ≤ p, is associated to color c i (c(r), c(r), . . . , c(r)), where c(r) is the color associated to the root of T and c i ∈ M. Observe that, since M k is colorful, c i = c j , when i = j, hence the vertices of T S all have distinct colors.

We are now in position to state the main results of this section.

Theorem 1. For any constant δ < 1, the Maximum Level Motif problem cannot be approximated within ratio 2 log δ n in polynomial-time unless NP ⊆ DTIME[2 poly log n ].

Proof. Assume that there exists a constant δ < 1 such that the Maximum Level Motif problem can be approximated within ratio 2 log δ n in O(n c ) time, for some constant c. For any fixed ε > 0, let k = ⌈( log δ n log(1+ε) )

1 (1-δ) ⌉. Given an instance I of the Maximum Level Motif problem of size n, let I k be the instance obtained by applying the product k times. Now, since the problem can be approximated within ratio 2 log δ n in O(n c ) time, it follows that there is an algorithm for the Maximum Level Motif problem for instance I k with performance ratio 2 log δ n k that runs in O(n ck ) = O(2 poly log n ) time. But, according to Lemmas 6 and 7, there is an algorithm for instance I with performance ratio (2 log δ n k ) 1/k ≤ (1 + ε), and hence we have designed a PTAS algorithm for the Maximum Level Motif problem. The result now follows from Proposition 9.

Notice that the Maximum Level Motif problem is a special case of the Maximum Motif problem, and hence Theorem 1 holds for the Maximum Motif problem.

Substituting the complexity hypothesis NP ⊆ DTIME[2 poly log n ] by the classical P = NP yields the following result.

OP T k α 1/k ≥ OP T α 1/k .
But k = ⌈log 1+ε α⌉, and hence (1 + ε) k ≥ α. Therefore, α 1/k ≤ 1 + ε. We have thus described a polynomial-time approximation scheme (PTAS) for the Maximum Level Motif problem since the running time of the algorithm is O(n k ) for some constant k (this follows from Lemma 7 and the fact that computing the product instance is O(n k ) time). The result now follows from Proposition 9.

The same result holds also for the Maximum Motif problem.

case time complexity of the algorithm. Then Z(n) = Z(n-1)+Z(n-2)+O(n).

It follows that Z(n) = O * (1.62 n ).
Consider now the case when the motif M is a set of colors. Consider a candidate vertex v x ∈ V ′ for T S , colored c(v x ). Assume that v x is the only vertex of V ′ -L(T ′ ) colored c(v x ). Then, v x is added to V S . Indeed, since v x is candidate and M is a set, there is no vertex in T S that has color c(x) and a vertex y of T ′ colored c(x) must be a leaf.

The algorithm considers the following cases associated to a candidate vertex v x for T S :

1. v x is added to the solution T S ; then, for each v y ∈ V ′ colored c(v x ), the subtree rooted at vertex v y is removed. 2. v x is not added to the solution T S ; then the subtree of T ′ rooted at v x is removed from T ′ .

Observe that only Case 1. above is modified, as Case 2. above is identical to the case when M is a multiset. In Case 1., v x is added to T S and, since there exists at least one internal vertex of V ′ colored c(v x ), the number of vertices that the algorithm has still to consider is decreased by 3. Then,

Z(n) = Z(n -2) + Z(n -3) + O(n). It follows that Z(n) = O * (1.33 n ).
Let T S = (V S , E S ) be a solution constructed by the algorithm. Then, Lemma 8 is applied in order to add the maximum number of vertices x of V -V S , such that x is adjacent to some vertex of V S .

Parameterized Complexity

In this section, we present two fixed-parameter algorithms for the Maximum Motif problem. The algorithms are based on the color-coding technique. Combining two families of perfect hash functions, we assign label to both the vertices of the graph and the colors that will be part of a solution of the Maximum Motif, and compute a solution by dynamic programming. We first describe the perfect family of hash functions used in both algorithms. Next, we give an FPT algorithm in case the target graph is a tree and finally present a (slower) algorithm for the general case.

Consider an instance I = (G, M) of the Maximum Motif problem, where G = (V, E) is a graph and M is a multiset of colors. For a color c i of M and a subset V ′ ⊆ V , we denote by m M (c i ) the number of occurrences of c i in M and by m V ′ (c i ) the number of vertices in V ′ colored c i . In the sequel, we assume that m

M (c i ) ≤ m V (c i ) since an occurrence of M in G has at most min{m M (c i ), m V (c i )} occurrences of color c i . For a subset of vertices V ′ ⊆ V and a submotif M ′ ⊆ M, we say that V ′ violates M ′ if m M ′ (c i ) < m V ′ (c i ) for some c i ∈ M.
Both algorithms are based on the color-coding technique [START_REF] Alon | Color coding[END_REF]. We recall here the basic definition of perfect hash functions: for a set S, a family F of functions from S to {1, 2, . . . , k} is perfect if for any S ′ ⊆ S of size k, there exists an injective function f ∈ F from S ′ to {1, 2, . . . , k}. In the sequel, k denotes the size of a solution for the Maximum Motif problem. Consider a family H of perfect hash functions from M to the set {1 H , 2 H , . . . , k H } (we use the subscript H to emphasis that this set is related to the family H). Let M ′ be a submotif of size k and let G ′ = (V ′ , E ′ ) be the occurrence of M ′ in G. Since H is perfect, there exists an injective function h ∈ H that assigns to each occurrence of a color in M ′ a distinct label in {1 H , 2 H , . . . , k H }.

Fix some function h ∈ H. For any c i ∈ M, denote by S H (c i ) ⊆ {1 H , 2 H , . . . , k H } the set of labels associated to occurrences of color c i by function h. Furthermore, we associate to each vertex v colored c i the set of labels S H

(v) = S H (c i ). Let V ′ ⊆ V , L H ⊆ {1 H , . . . , k H }, then C(S H , V ′ , L H ) is defined as the family of sets S H (v) ∩ L H , with v ∈ V ′ . Notice that C(S H , V ′ , L H ) may contain more oc- currences of the same set of labels. For example, if v 1 , v 2 ∈ V ′ and c(v 1 ) = c(v 2 ), then (S H (v 1 )∩L H ) = (S H (v 2 )∩L H ). In case L H = {1 H , . . . , k H }, we abbreviate C(S H , V ′ , L H ) by C(S H , V ′ ). Definition 2. Let C(S H , V ′ , L H ) be a family of sets S H (v) with v ∈ V ′ and L H ⊆ {1 H , . . . , k H }, then C(S H , V ′ , L H ) is feasible if and only if there exists an injective function p from the sets of C(S H , V ′ , L H ) to L H , such that, for each S H (v) ∈ C(S H , V ′ , L H ), p(S H (v)) is a label of S H (v) ∩ L H . Consider now a family C(S H , V ′ ) of sets associated to V ′ . Let c i be a color of M, then by construction |S H (c i )| ≤ m M (c i ). Hence, if C(S H , V ′ ) is feasible, then V ′ does not violate M.
We now present an FPT algorithm for the case the target graph is a tree T = (V, E). Let r ∈ V , and we want to compute a solution T ′ = (V ′ , E ′ ) of the Maximum Motif problem, such that |V ′ | = k and r ∈ V ′ (we run the algorithm for each r ∈ V .) Define r as the root of T and, for each internal vertex v of V , define a left-to-right ordering on the children of v. Assume that r is colored c(r). Observe that, since r must belong to T ′ , we can safely remove an occurrence of color c(r) from M. Furthermore, we assume that function h assigns to this occurrence of c(r) label 1 H and that S H (r) = {1 H }. Observe that there is no other vertex u ∈ V -{r}, such that S H (u) contains 1 H . We can now give the definition of the rightmost vertex of a subtree T ′ of T . Definition 3. Let T ′ = (V ′ , E ′ ) be a subtree of T . A vertex v ∈ V ′ is defined to be the rightmost vertex of T ′ if and only if (i) v has no children in V ′ and (ii) for each vertex u ∈ V ′ on the path from r to v, V ′ does not contain the right sibling of u. Now, consider a vertex v ∈ V and a subset L H of labels in {1 H , . . . , k H }. Define P r [v, L H ] as follows:

P [v, L H ] =     
1 if there exists a subtree T ′ = (V ′ , E ′ ) of T with r ∈ V ′ and with rightmost vertex v and such that C(S H , V ′ , L H ) is feasible, 0 otherwise.

The recurrence to compute P [v, L H ] is as follows.

P [v, L H ] = u,L ′ H P [u, L ′ H ], (2)
where u is either a descendant of a left sibling of v or the parent of v, and

L ′ H = L H -{i H }, for some i H ∈ S h (v)∩L H . Notice that P [v, {1 H }] = 0, for each v ∈ V -{r}, P [r, {1 H }] = 1, and that P [r, {i H }] = 0 for each i H ∈ {2 H , . . . , k H }. Lemma 9. Given a labeling h of the motif M, we can compute in O(n 2 2 k ) time if there is a subtree T ′ of T of size k that matches a submotif M ′ of M.
Proof. We have to show that P [v, L H ] = 1 if and only if there exists a subtree

T ′ = (V ′ , E ′ ) of T having root r, which is an occurrence of a submotif M ′ of M of size |L H |. Since T ′ must contain r, we assume that L H contains 1 H .
First, consider a subtree T ′ = (V ′ , E ′ ) with root r. Let v be the rightmost vertex of T ′ . From the definition of the rightmost vertex, it follows that there is no child of v in V ′ and that there is no vertex in T ′ which is a right sibling of a vertex on the path from r to v. Denote by T ′′ = (V ′′ , E ′′ ) the tree obtained from T ′ by removing v. Let u be the rightmost vertex of T ′′ . By definition of the rightmost vertex, u is either the parent of vertex v, denoted by p(v), or a descendant of a child v ′ of p(v) in T ′′ (with v ′ a left sibling of v in T ′ by definition of rightmost vertex).

Let M ′ = C(V ′ ) be the multiset of colors associated to the vertices of T ′ . Consider C(S H , V ′ , L H ), the collection of sets of labels in L H assigned to V ′ . Notice that C(S H , V ′ , L H ) is feasible, as T ′ is a solution of the Maximum Motif problem. It follows that there is an injective function p that assigns to each set S H (u), with u ∈ V ′ , a label i H in S H (u). But then, function p assigns label i H ∈ S H (v) to the set S H (v). It follows that the family of sets S H (u) with u ∈ (V ′ -{v}) must be feasible when p assigns a label in the set {1 H , . . . , k H } -{i H } to each set S H (u), with u ∈ (V (T ′ ) -{v}). Hence P [v, L H ] = 1.

Assume now that P [v, L H ] = 1. We will prove the results by induction. Since P [v, L H ] = 1, by Recurrence (2) it follows that there must exist a vertex u ∈ V ′ and a label i H ∈ S H (v), such that P [u, L H -{i H }] = 1. By the induction hypothesis, it follows that there is a subtree of T ′′ = (V ′′ , E ′′ ) of T having root r, so that T ′′ has size |L H | -1, u is the rightmost vertex of T ′′ and C(S H , V ′′ , L H -{i H }) is feasible. Hence, by construction, also C(S H , V ′ , L H ) is feasible. We will show that v is adjacent to a vertex of T ′′ . By definition of rightmost vertex, u is either the parent of vertex v, denoted by p(v), or a descendant of a child v ′ of p(v) in T ′′ (with v ′ a left sibling of v in T ′ ). In the former case clearly u and v are adjacent. In the latter case, that is u is not p(v), since T ′′ must be rooted at r, p(v) belongs to T ′′ , hence v is adjacent to a vertex of T ′′ .

Observe that, if P [v, {1 H , . . . , k H }] = 1, it follows that there is a subtree Observe that we have to choose O(n) possible roots. Furthermore, since the family of perfect hash functions has size O(log n) 2 O(k) , it follows that the algorithm is O(k2 k n 3 log n) 2 O(k) time.

T ′ = (V ′ , E ′ ) containing the root of T , so that each C(V ′ ) is assigned a distinct label in {1 H , . . . , k H }. By construction, V ′ does not violate M, hence C(V ′ ) is a submotif of M of size k.
Next, we describe a parameterized algorithm when the instance of the Maximum Motif problem consists of a graph G = (V, E) and a motif M. The algorithm for this case consists in combining two perfect families of hash functions, and then applying a strategy similar to that presented in [START_REF] Dondi | Weak pattern matching in colored graphs: Minimizing the number of connected components[END_REF][START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF].

Consider two different perfect families of hash functions: a family H from M to {1 H , . . . , k H }, as we have previously introduced in this section, and a family F from the set V to {1 F , . . . , k F }. By the property of the family of perfect hash functions, we know that there is a function f ∈ F such that the vertices of G that belong to a solution of size k are associated to distinct labels of {1 F , . . . , k F }. Similarly, we know that there is a function h ∈ H such that the occurrences of colors of M that belong to an optimal solution, are associated to different labels of {1 H , . . . , k H }. Observe that each family of perfect hash functions consists of O(log n) 2 O(k) functions. Hence, we can combine all the possible pairs (f, h) of functions, with f ∈ F and h ∈ H, in O(log 2 n) 4 O(k) time.

Recall that, for each color c i ∈ M, S H (c i ) denotes the set of labels associated to occurrences of color c i by function h, and that, given that v is colored c i , S H (v) = S(c i ). Now, for each v ∈ V and for each subset L ⊆ {1 F , . . . , k F }, define M L (v) as the family of all sets of labels H ′ ⊆ {1 H , . . . , k H } such that there exists an occurrence V ′ , with v ∈ V ′ , where the set of labels in {1 F , . . . , k F } that f assigns to V ′ is exactly L and such that C(S H , V ′ , H ′ ) is feasible. Now, we present a method called the Batch procedure for computing M L (v), similar to that introduced in [START_REF] Dondi | Weak pattern matching in colored graphs: Minimizing the number of connected components[END_REF][START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF]. Assume that we have computed the family of sets M L ′ (v), with L ′ ⊆ L \ f (v), we apply the following procedure.

Batch Procedure(L, v):

• Define C H to be the family of all pairs (H ′ , L ′ ) such that H ′ ⊆ {1 H , . . . , k H }-{i H } for some i H ∈ S H (v i ), L ′ ⊆ L \ {f (v)}, and H ′ ∈ M L ′ (u) for some u ∈ N (v).

• Run through all pairs of (H ′ , L ′ ), (H ′′ , L ′′ ) in C H and determine whether H ′ ∩ H ′′ = ∅ and H ′ ∪ H ′′ ⊆ {1 H , . . . , k H } -{i H }, for some i H ∈ S H (v i ), and whether L ′ ∩ L ′′ = ∅. If there is such a pair, add (H ′ ∪ H ′′ , L ′ ∪ L ′′ ) to C H and repeat this step. Otherwise, continue to the next step.

• Set M L (v) to be all the sets of labels H ′ ∪ {i H }, where i H ∈ S H (v i ) -H ′ , (H ′ , L ′ ) ∈ C H and L ′ = L ⊆ -{f (v)}.

Lemma 10. Given a vertex v ∈ V and L ⊆ {1 F , . . . , k F }, the batch procedure computes correctly M L (v), assuming M L ′ (u) is given for each u adjacent to v and for each L ′ ⊆ L \ {f (v)}.

Proof i that has an occurrence in a set V ′ i , such that V ′ i includes a vertex adjacent to v. Notice that each V ′ i is associated to a set of labels L i ⊆ {1 F , . . . , k F }, such that L i ∩ L j = ∅ for each V j with i = j. Hence, all the connected components G[V ′ 1 ], . . . , G[V ′ t ] are pairwise disjoint, and {v} ∪ V 1 • • • ∪ V n is connected. It follows that H ′ ∪ {i h } is then feasible and it is associated to vertices having labels L ′ , so L ′ belongs to M L (v).

Consider now L ′ , a set of labels in M L (v), such that L ′ ∪ f (v) is part of M L (v). Observe that, by definition, there exists a set of vertices V ′ , associated to the set of labels L ′ , such that the function f assigns to V ′ the set of labels in L ′ . Consider now the connected components induced by sets V 1 , . . . , V t where

V 1 ∪ V 2 • • • ∪ V t = V ′ . Since V ′ ∪
{v} must be a connected component, each V i must have a vertex adjacent to v. Each connected component V i is associated to a set of labels L i , such that L i ∩ L j = ∅, for each j = i. Now, the batch procedure will compute the pair (H ′ , L ′ ) in its second step, and H ′ ∪ {i H } will be added to C H . Notice that the function h assigns a distinct label in {1 H , . . . , k H } to each occurrence of a color in a submotif M ′ , with |M ′ | = k. Consider M L (v) = {1 H , 2 H , . . . , k H } with L = {1 F , 2 F , . . . , k F }. The set of vertices in V ′ associated to labels {1 F , 2 F . . . , k F } is then associated to colors having labels in {1 H , 2 H . . . , k H }. Hence, C(V ′ ) does not violate M. Lemma 11. Given labeling functions h : M → {1, . . . , k} and f : V → {1, . . . , k}, the batch procedure determines in O(2 5k kn 2 ) time whether there exists a solution of the Maximum Motif problem of size k.

Proof. First, we will show that a set M L (v) is computed by the batch procedure in O(2 4k kn) time. The first step of the batch procedure searches at most 2 k n families of subsets H ′ of labels in {1 H , . . . , k H }, for each i H ∈ S H (v). Notice that |S H (v)| ≤ k. Each family consists of at most 2 k sets. Hence, the first step requires O(2 2k kn).

For the second step of the batch procedure, observe that there are at most 2 2k sets of label-subset pairs H ′ and L ′ , and hence the second step is repeated 2 2k times. Each iteration of this step can be computed in O(2 k n) time, hence the second step requires O(2 4k kn) time. Accounting also for the third step, the overall time complexity for one invocation of the batch procedure is O(2 4k k + 2 2k kn) = O(2 4k kn).

According to Lemma 10, the batch procedure must be invoked at most 2 k n times in order to obtain M L (v) for every v ∈ V and every label subset L ′ ⊆ {1 F , . . . , k F }, hence the overall time complexity is O(2 5k kn 2 ).

Since each perfect family of hash functions has size O(log n) 2 O(k) , the overall time complexity of the algorithm is O(2 5k kn 2 log 2 n) 4 O(k) .

Conclusion

This paper was concerned with two optimization variants of the Graph Motif problem [24? ]: Min-CC and Maximum Motif. We proved the problem of finding an occurrence of a colored motif that induces a minimum number of connected components (Min -CC) to be APX-hard for colorful motifs and paths, and we proved this problem to be fixed-parameter tractable when parameterized by the size of the motif but to be W [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF]-hard when parameterized by the number of connected components. To complement the above results, we gave an exact exponential-time algorithm for the Min-CC problem in case the target graph is a tree. As for the Maximum Motif problem, i.e., find a maximum cardinality submotif that occurs in the target graph, we proved this problem to be APX-hard in case the motif is colorful and the target graph is a bounded degree tree and to be not approximable within ratio 2 log δ n , for any constant δ < 1, unless NP ⊆ DTIME(2 poly log n ). We complemented these results by presenting two fixed-parameter algorithms and an exact exponentialtime algorithm for the Maximum Motif problem.

We mention here some directions of interest for future works. First, approximation issues of the Min-CC problem are widely unexplored. In particular, is the Min-CC problem for paths approximable within a constant? How approximable is the Maximum Motif problem for colorful motifs in case the target graph is a tree in which each color occurs at most twice? Are Fourier methods [START_REF] Björklund | Fourier meets möbius: fast subset convolution[END_REF] relevant for the parameterized Min-CC and Maximum Motif problems? Kernalization issues of both problems are also completely unexplored.

Figure 1 :

 1 Figure 1: Illustration of the L-reduction from Set-Cover to Min-CC.

Figure 2 :

 2 Figure 2: Schematic representation of the tree T described in Proof of Proposition 8.

Lemma 4 .

 4 Let I = (T, M) be an instance of the Maximum Level Motif problem and T ′ be a solution for instance I. One can compute in polynomialtime a solution T ′′ for I, such that (i) |T ′′ | ≥ |T ′ | and (ii) T ′′ contains the root of T .

Proposition 10 .

 10 No polynomial-time algorithm achieves a constant factor approximation algorithm for the Maximum Level Motif problem unless P = NP. Proof. Let A be an algorithm for the Maximum Level Motif problem that achieves approximation factor α for some constant α > 1. For some constant ε, let k = ⌈log 1+ε α⌉. Let I be an instance of the Maximum Level Motif problem of size n. Then, I k has size n k . Let opt k and opt denote the optimum solution for instances I k and I, respectively. According to Lemma 6, |opt k | ≥ |opt| k . Now, using Algorithm A, one can compute an α-approximate solution S k for instance I k , i.e., |S k | ≥ opt k /α. Now, thanks to Lemma 7, starting from S k we can compute a solution for instance I of size at least OP T k α 1/k . Applying Lemma 6 thus yields

  Now, we consider the time complexity of the algorithm. Observe that there exist O(n2 k ) values of the form P [v, K ′ ], with v ∈ V (T ) and L ′ H ⊆ {1 H , . . . , k H }. Now, in order to compute value P [v, K ′ ], we have to check at most O(nk) other values P [u, K ′′ ]. Hence the time complexity is O(n 2 k2 k ).

  It follows easily from the proof of the above lemma that a 2-isogram has a minimum cardinality prefix cover if and only if it has a minimum cardinality suffix cover, and that it has a minimum cardinality prefix or suffix cover if and only if it has not a minimum cardinality cover which is neither prefix nor suffix. Lemma 2. A 2-isogram has a proper 2-coloring with at most k color changes if and only if it has a cover of size at most k 2 .

  . Consider the family C H computed by the batch procedure. Let (H ′ , L ′ ) ∈ C H , whereH ′ ⊆ {1 H , . . . , k H } -{i H } for some i H ∈ S H (v) and L ′ ⊆ L \ f (v). By construction, H ′ = H ′ 1 ∪ • • • ∪ H ′ t , where each H ′ i ⊆ {1 H , . . . , k H } -{i H }, 1 ≤ i ≤ t, is associated by the function h to a submotif M ′