Michael R Fellows
email: michael.fellows@newcastle.edu.au

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

Danny Hermelin
email: hermelin@mpi-inf.mpg.de

Stéphane Vialette
email: vialette@lri.fr

Upper and Lower Bounds for Finding Connected Motifs in Vertex-Colored Graphs ⋆

We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices whose multiset of colors equals the motif. This problem is a natural graph-theoretic pattern matching variant where we are not interested in the actual structure of the occurrence of the pattern, we only require it to preserve the very basic topological requirement of connectedness. We give two positive results and three negative results that together give an extensive picture of tractable and intractable instances of the problem.

Introduction

Vertex-colored graph problems have numerous applications in bioinformatics. Sandwich problems have applications in DNA physical mapping [START_REF] Bodlaender | Intervalizing k-colored graphs[END_REF][START_REF] Fellows | DNA physical mapping: Three ways difficult[END_REF][START_REF] Golumbic | On the complexity of DNA physical mapping[END_REF] and in perfect phylogeny [START_REF] Bodlaender | Two strikes against perfect phylogeny[END_REF][START_REF] Mcmorris | Triangulating vertex-colored graphs[END_REF], while vertex-recoloring problems arise in protein-protein interaction networks and phylogenetic analysis [START_REF] Bodlaender | Kernelization for convex recoloring[END_REF][START_REF] Chor | Connected coloring completion for general graphs: Algorithms and complexity[END_REF][START_REF] Moran | Convex recolorings of strings and trees: Definitions, hardness results and algorithms[END_REF]. In this paper, we consider another vertex-colored graph problem with an important application in metabolic network analysis [START_REF] Lacroix | Motif search in graphs: Application to metabolic networks[END_REF]:

Graph Motif:

Input: A vertex-colored graph G and a multiset of colors M.

Question: Does G have a connected subset of vertices whose multiset of colors equals M?

The Graph Motif problem can be viewed as a natural variant of a graphtheoretic pattern matching problem. In more classical variants one is interested in subgraphs or induced subgraphs that appear, along with their colors, in the corresponding text graph. However, in Graph Motif we are not interested in the actual structure of the occurrence of the pattern, we only require it to preserve the very basic topological requirement of connectedness. We believe that due to the generic nature of this problem, it will find applications in many domains. Indeed, although the problem was introduced by Lacroix, Fernandes, and Sagot (in a slightly more general formulation) in the context of detecting patterns that occur in e.g. interaction networks between chemical compounds and\or reactions [START_REF] Lacroix | Motif search in graphs: Application to metabolic networks[END_REF], it is conceivable to think that algorithms for this problem can also be used in analyzing other types of networks, such as social or technical networks.

In [START_REF] Lacroix | Motif search in graphs: Application to metabolic networks[END_REF], Graph Motif is proved to be NP-complete even if the given vertexcolored graph is a tree, but fixed-parameter tractable in this case when parameterized by the size of the given motif (i.e., |M|). However, as observed by [START_REF] Lacroix | Motif search in graphs: Application to metabolic networks[END_REF], their fixed-parameter algorithm does not apply when the vertex-colored graph is a general graph. For this case they only provided a heuristic algorithm which works well in practice. This paper focuses on extending these results. In particular, we are interested in investigating Graph Motif under different parameters governing the structure of the input.

Our results

We give an extensive, yet still initial, analysis for Graph Motif which provides both upper and lower bounds for the problem. Our analysis applies tools from both the classical and the parameterized complexity viewpoints, and is aimed at understanding the nature of tractable and intractable instances of the problem and the parameters controlling them. We show that Graph Motif is:

(1) NP-complete already for trees of maximum degree 3 and for motifs which are sets rather than multisets. (2) NP-complete for motifs with 2 colors, even if G is bipartite with maximum degree 4. (3) FPT when parameterized by the size of the motif k via an algorithm running in time 2 O(k) n 2 lg n. (4) XP when parameterized by both the number of colors in the motif and the treewidth of the input graph. In other words, it is polynomial-time solvable when both these parameters are bounded by some constant. ( 5) W [START_REF] Alon | Color coding[END_REF]-hard when parameterized by the number of colors in the motif, even when the input graph is a tree.

Our first upper bound (3) should be compared with our first lower bound [START_REF] Alon | Color coding[END_REF]. These two together give a rather sharp distinction between the complexity of the problem when the motif is unbounded. When the motif has a bounded number of colors, our second lower bound [START_REF] Althaus | Approximating the interval constrained coloring problem[END_REF] suggests that the problem remains hard for quite a few graph classes, yet not for bounded-treewidth graphs according to [START_REF] Arnborg | Efficient algorithms for combinatorial problems on graphs with bounded decomposability[END_REF]. Our last lower bound [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF] complements the algorithm for bounded treewidth graphs by showing that when we take the number of colors in the motif as a parameter, the problem becomes intractable already for trees.

Related and extended work

Since the appearance of the earlier version of this work [START_REF] Fellows | Sharp tractability borderlines for finding connected motifs in vertex-colored graphs[END_REF], other variants of Graph Motif have been introduced and studied. In [START_REF] Dondi | Weak pattern matching in colored graphs: Minimizing the number of connected components[END_REF], a minimization variant of the problem was considered, where the goal is to minimize the number of connected components that induce all the colors in the motif. An asymmetric maximization variant of Graph Motif was considered in [START_REF] Dondi | Maximum motif problem in vertex-colored graphs[END_REF], where the goal is to find the largest subset of the given motif that occurs in the graph. Both problems turn out to be APX-hard, even for restrictive special cases, and are in FPT when parameterized by the size of the solution by extensions of the algorithm presented here. Finally, Betzler et al. [START_REF] Betzler | Parameterized algorithms and hardness results for some graph motif problems[END_REF] considered the variant where the occurrence of the motif is required to be 2-connected, and showed that this variant is W[1]-complete when parameterized by the size of the motif M. This result shows how fragile the tractability results are with respect to the topological requirements of the motifs. They also presented an improvement upon our FPT algorithm for parameter |M|, and this has recently been improved once more in [START_REF] Guillemot | Finding and counting vertex-colored subtrees -Manuscript[END_REF].

The Graph Motif problem was introduced by by Lacroix, Fernandes, and Sagot (in a slightly more general formulation) in the context of detecting patterns that occur in various metabolic networks, e.g. interaction networks between chemical compounds and\or reactions [START_REF] Lacroix | Motif search in graphs: Application to metabolic networks[END_REF]. There has been an enormous amount of study in this area in the biological community. We refer interested readers to [START_REF] Deville | An overview of data models for the analysis of biochemical pathways[END_REF] for a short overview. The model of Lacroix et al. was also used and extended in [START_REF] Bruckner | Torque: topology-free querying of protein interaction networks[END_REF][START_REF] Ideker | Efficient algorithms for detecting signaling pathways in protein interaction networks[END_REF][START_REF] Kelley | Conserved pathways within bacteria and yeast as revealed by global protein network alignment[END_REF].

Finally, we wish to mention the related problem of Interval Constraint Coloring, where the input is a set of intervals on the integer line, and a set of motifs, one for each interval. The goal is to color the integers on the line so that each interval has exactly the colors of his motif. This problem was introduced in the context of automated mass spectrometry [START_REF] Althaus | Approximating the interval constrained coloring problem[END_REF][START_REF] Althaus | Computing H/D-exchange speeds of single residues from data of peptic fragments[END_REF], and has been analyzed according to the parameters governing its input in [START_REF] Komusiewicz | Deconstructing intractability: A case study for interval constrained coloring[END_REF].

Basic notation and terminology

Our graph-theoretic notation is standard and all notions we use can be found in any classical text on the subject, e.g. [START_REF] Diestel | Graph Theory[END_REF]. Throughout the paper, we use G = (V (G), E(G)) to denote our given vertex-colored graph, and n = |V (G)| to denote its order. For a vertex v ∈ V (G), we use χ(v) to denote the color of v, and for a vertex subset V ⊆ V (G), we let χ(V ) denote the multiset of colors v∈V χ(v). For any vertex subset V ⊆ V (G), we let G[V ] denote the subgraph of G induced by V , i.e., the subgraph on V along with all edges of G that connect vertices in V . We assume w.l.o.g. that G is connected.

A motif M is a multiset of colors. If M is in fact a set rather than a multiset, we say that M is colorful. Given a subset of vertices

V ⊆ V (G), |V | = |M|, we say that V is colored by the colors of M, if χ(V ) = M.
For V to be an occurrence of M, we require not only for V to be colored by the colors of M, but also for G[V ] to be connected. If this is in fact the case, we say that M occurs at v for any vertex v ∈ V , or simply that M occurs in G. In these terms, the Graph Motif problem is the problem of determining whether a given motif M occurs in a given vertex-colored graph G. We assume w.l.o.g. that χ(v) ∈ M for any v ∈ V (G).

Our analysis is based both on the classical and parameterized complexity frameworks. Readers unfamiliar with these subjects are referred to [START_REF] Downey | Parameterized Complexity[END_REF][START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF].

Organization

The rest of the paper is organized as follows. In the reminder of this section we discuss notations that will be used throughout the paper. In Section 2, we give two NP-hardness results that will motivate the rest of our discussion. Following this, in Section 3 we present our algorithm for logarithmic size motifs. In Section 4 we discuss the case when G has bounded treewidth. Finally, in Section 5, we show that Graph Motif is W[1]-hard on trees when parameterized by the number of colors in M.

Two Classical Hardness Results

Graph Motif is known to be NP-complete for trees [START_REF] Lacroix | Motif search in graphs: Application to metabolic networks[END_REF]. Our aim in this section is to tighten this result by showing that Graph Motif remains hard for highly restrictive graph classes, even if we restrict ourselves to motifs which are sets rather than multisets, or on the other extreme, to motifs which consist of a small number of colors. We begin with colorful motifs (i.e. set motifs).

Theorem 1 Graph Motif is NP-complete, even if M is colorful and G is a tree of maximum degree three.

PROOF. Graph Motif is clearly in NP. To prove NP-hardness, we present a reduction from the well known NP-complete problem 3-SAT [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Recall that 3-SAT asks to determine whether a given 3-CNF formula is satisfiable, that is, whether there is a truth assignment to the boolean variables of the formula, such that the value of the formula under this assignment is 1. The problem remains hard even if each variable appears in at most three clauses and each literal (i.e., variable with or without negation) appears in at most two clauses [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Hence, we restrict ourselves in our proof to formulas of this type.

Let an instance of 3-SAT be given in the form of a 3-CNF formula Φ =

c 1 ∧ • • • ∧ c m over variables x 1 , . . . , x n such that |{c j | x i ∈ c j }| ≤ 2 and |{c j | xi ∈ c j }| ≤ 2 for all 1 ≤ i ≤ n.
We construct an instance for Graph Motif as follows. The colored graph G initially consists of a path of n vertices, each colored by a distinct color in 1, . . . , n. To a vertex colored i in this path, 1 ≤ i ≤ n, we connect a new vertex colored i ′ . To a vertex colored i ′ , 1 ≤ i ≤ n, we connect a pair of new non-adjacent vertices, both colored x i . Conceptually, each vertex in this pair corresponds to a different truth assignment for x i . If a truth assignment to variable x i satisfies clause c j , we connect a new vertex colored c j to the vertex colored x i which corresponds to this assignment. This is done for every x i ∈ {x 1 , . . . , x n } and every c j ∈ {c 1 , . . . , c m }. We conclude our construction by specifying M to be the set of colors {1, . . . , n, 1 ′ , . . . , n ′ , x 1 , . . . , x n , c 1 , . . . , c m }. A simple example of this construction is given in Fig. 1. Note that G and M are as required by the theorem.

1 2 3 1 ′ 2 ′ 3 ′ x 1 x 1 c 1 c 3 c 2 x 2 x 2 c 1 c 2 c 3 x 3 x 3 c 1 c 2 c 3 Figure 1.
An example of the construction of G out of a 3-CNF formula which consists of three clauses:

c 1 = (x 1 ∨ x 2 ∨ x 3 ), c 2 = (x 1 ∨ x 2 ∨ x3 ), and c 3 = (x 1 ∨ x2 ∨ x3 ).
The construction above is clearly polynomial. Hence, to complete the proof, we are left to show that M occurs in G if and only if Φ is satisfiable. For the first direction, assume that there exists a truth assignment φ which satisfies Φ.

Let N ⊆ V (G) be the subset of vertices in G which are colored by the colors in {1, . . . , n, 1 ′ , . . . , n ′ }, and let X ⊆ V (G) be the subset of vertices which correspond to assignment φ. Hence, X consists of n vertices which are colored by the colors in {x 1 , . . . , x n }, and N ∪ X induces a connected subgraph. Since φ satisfies every clause in Φ, by construction of G there is a vertex colored c j in the neighborhood of X for every 1 ≤ j ≤ m. In other words, there exists C ⊆ N(X) which is colored by the colors in {c 1 , . . . , c m }. It follows that V = N ∪ X ∪ C is connected and is colored by the colors of M, and therefore is an occurrence of M in G.

For the converse direction, assume there exists an occurrence V of M in G.

Let X ⊆ V be the vertices colored by the colors in {x 1 , . . . , x n }, C ⊆ V be the vertices colored by the colors in {c 1 , . . . , c m }, and φ the truth assignment corresponding to X. By construction, a vertex colored c j is connected in G to a vertex colored x i if and only if the truth assignment corresponding to this vertex satisfies clause c j . Since C contains all colors in {c 1 , . . . , c m }, and since vertices in C are connected only to vertices in X, it follows that φ satisfies every clause in Φ, and so it satisfies Φ itself. 2

Theorem 1 (and our proof) shows that a polynomial-time algorithm for Graph Motif restricted to trees of maximum degree three is unlikely, even when the motif is colorful, and when each color occurs at most three times in the input tree. The next lemma shows that this implication is tight in two ways:

Lemma 2 Graph Motif is polynomial-time solvable if either • G has maximum degree two, or
• G is a tree where each color is shared by at most two vertices, and M is colorful.

PROOF. First observe that if G has maximum degree two, then G is actually a collection of paths and cycles. Given a motif M, one can search through all subpaths of length |M| in the cycles and paths of G in polynomial-time.

To prove the second part of the lemma, assume without loss of generality that G is rooted at r ∈ V (G) (as otherwise we can try all possible roots), and let M = {1, . . . , k}. We associate with each vertex v a unique literal

x(v) ∈ {x 1 , x1 , . . . , x k , xk }, with x(v) ∈ {x i , xi } if χ(v) = i.
This can be done since each color in M appears at most twice in G. Next, we construct a 2-CNF formula Φ which consists of all clauses x(u) ⇒ x(v) for every childparent pair (u, v) in G. We also add to Φ a single-literal clause containing x(r).

Interpreting the assignment of the variable x i as the selection of which of the two vertices colored i in G will be taken for the occurrence of M, it is easy to see that M occurs in G (with respect to the root r) iff Φ is satisfiable. Thus, the second part of the lemma follows from the fact that 2-SAT is polynomial-time solvable [START_REF] Aspvall | A linear-time algorithm for testing the truth of certain quantified boolean formulas[END_REF].

2
The motif used in the construction of Theorem 1 above is not only of unbounded size, it also consists of an unbounded number of colors. One might hope that for motifs which consist of only a small number of colors, Graph Motif would become polynomial-time solvable. Indeed, if the motif consists of a single color then Graph Motif reduces to the polynomial problem of computing the largest connected component in G. Unfortunately, the following theorem shows that already for motifs which consist of two colors Graph Motif is NP-complete, even when restricted to bipartite graphs of maximum degree four.

Theorem 3 Graph Motif is NP-complete, even if M consists of two colors, and G is bipartite with maximum degree four.

PROOF. We reduce from the Exact Cover by 3-Sets (X3C) problem, which is known to be NP-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Recall that, given a set X = {x 1 , x 2 , . . . , x 3q } and a collection S = {s 1 , s 2 , . . . , s n } of 3-element subsets of X, the X3C problem asks to determine whether there exists an exact cover of X in S, i.e., a sub-collection C ⊆ S such that every element of X is included in exactly one subset s i ∈ C. The problem is hard even if each element of X appears in at most three sets of S [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], so we restrict ourselves in the proof to instances of this type.

Let X, S be an arbitrary instance of the X3C problem with |{s j ∈ S | x i ∈ s j }| ≤ 3 for all x i ∈ X. We show how to construct a motif M and a colored graph G in such a way that there exists an exact cover of X in S if and only if M occurs in G. First, we define M so as it contains 2n + 3q white elements and q black elements. Then, we define

G by V (G) = X ∪ S ∪ S ′ ∪ S ′′ and E(G) = E 1 ∪ E 2 ∪ E 3 ∪ E 4 , where S ′ = {s ′ 1 , s ′ 2 , . . . ,
E 1 = {{x i , s j } | x i ∈ s j }, E 2 = {{s i , s ′ i } | 1 ≤ i ≤ n}, E 3 = {{s ′ i , s ′′ i } | 1 ≤ i ≤ n}, and E 4 = {{s ′′ i , s ′ i+1 } | 1 ≤ i ≤ n -1}.
The vertices of X ∪ S ′ ∪ S ′′ are colored white and the vertices of S are colored black. It is easily seen that G and M are as required by the theorem, and that our construction can be carried out in polynomial time.

x 1 x 2 x 3 x 4 x 5 x 6 s 1 s 2 s 3 s 4 s ′ 1 s ′ 2 s ′ 3 s ′ 4 s ′′ 1 s ′′ 2 s ′′ 3 s ′′ 4 Figure 2.
The construction of G out of an instance for X3C: X = {x 1 , . . . , x 6 } and S = {s 1 , . . . , s 4 }. The 3-sets are

s 1 = {x 1 , x 2 , x 4 }, s 2 = {x 1 , x 3 , x 4 }, s 3 = {x 2 , x 5 , x 6 }, and s 4 = {x 3 , x 4 , x 6 }.
Let us now argue that there exists an exact cover C ⊆ S of X if and only if M occurs in G. For the first direction, suppose that there exists an exact cover C ⊆ S of X. Consider the subset of vertices V = X ∪ C ∪ S ′ ∪ S ′′ . First note that V consists of q = |C| black vertices and 2n + 3q = |X ∪ S ′ ∪ S ′′ | white vertices. Second, since C is a cover of X, every vertex of X is connected to some vertex in C, and C is connected to S ′ ∪ S ′′ , so V itself is connected. It follows that V is an occurrence of M, and M occurs in G.

Conversely, suppose that there exists an occurrence

V ⊆ V (G) of M in G.
Observe that M contains 2n + 3q white elements, and since exactly 2n + 3q vertices of G are colored white, we must have X ∪ S ′ ∪ S ′′ ⊂ V . The remaining q vertices in V are q black vertices from S. By construction, we do not have an edge between two vertices of X, nor between a vertex of X and a vertex of S ′ ∪ S ′′ . Therefore, since V is connected, each vertex of X has to be adjacent to at least one vertex in V ∩ S. But |X| = 3q and each vertex in S is connected to exactly 3 vertices in X. Then it follows that no two vertices of V ∩ S share a common neighbor in X, and C = V ∩ S is an exact cover of X in S. 2

Parameterizing by the Motif Size

We next prove that Graph Motif is fixed-parameter tractable for parameter |M| on any general graph. This generalizes the result of Lacroix, Fernandes, and Sagot [START_REF] Lacroix | Motif search in graphs: Application to metabolic networks[END_REF] mentioned in Section 1, and should be compared to the hardness results presented in the previous section. In particular, our algorithm implies that Graph Motif is polynomial-time solvable when the given motif M is of logarithmic size (i.e. |M| = O(lg n)).

Set k := |M|. Our algorithm for parameter k uses the color-coding technique introduced by Alon et al. [START_REF] Alon | Color coding[END_REF], whose derandomized version crucially relies on the notion of perfect hash families: A family F of functions from V (G) to {1, . . . , k} with the property that for any subset V ⊆ V (G) of k vertices there is a function f ∈ F which is bijective when restricted to V . Alon et al. [START_REF] Alon | Color coding[END_REF] showed any graph has a perfect hash family of size 2 O(k) • lg n, for any given positive integer k, and furthermore, this family can be constructed in 2 O(k) • n lg n time.

The main idea of the color-coding technique is as follows: Suppose M has an occurrence V in G, and suppose we are provided with a perfect family F of hash functions from V (G) to {1, . . . , k}. Since F is perfect, we are guaranteed that at least one function in F assigns V with k distinct labels. Thus, by iterating through all functions in F , we can concentrate on finding occurrences of V which are distinctly labeled by our hashing. This allows us to compute occurrences of M by applying dynamic programming.

Let us next describe the tables used in this dynamic programming algorithm, for a given a hash function f : V (G) → {1, . . . , k}. We use L to denote the set of labels {1, . . . , k}. For each vertex v ∈ V (G), we will have a table denoted DP v . Each such table will have an entry for every pair of label-subset L ′ ⊆ {1, . . . , k}, and motif-subset M ′ ⊆ M, M ′ = ∅. At the end of the algorithm, the following invariant will be held:

DP v [L ′ , M ′ ] = 1 ⇐⇒ M ′ has an occurrence V with v ∈ V, f (V ) = L ′ . (1)
All entries DP v [∅, M ′ ] are set to 0 at the beginning of the algorithm. Note that unlike M ′ which can be a multi-set, L ′ will always be a set of labels. Clearly, M has an occurrence V which is distinctly labeled by

f iff DP v [L, M] = v for some v ∈ V (G).
Now let v be some vertex of G. Our goal is to compute DP v [L ′ , M ′ ] assuming DP u [L ′′ , M ′′ ] has previously been computed for every vertex u ∈ V (G), any L ′′ ⊆ L ′ \ {f (v)}, and any M ′′ ⊆ M ′ \ {f (v)}. The straightforward approach is to consider small motifs occurring at neighbors of v. However, a motif occurring at v might be the union of motifs occurring at any number of neighbors of v, and so this approach might require exponential running time in n. We therefore present an alternative method for computing DP v [L ′ , M ′ ], which we call the batch procedure, that uses an even more naive approach, but one that requires exponential-time only with respect to k:

Batch Procedure(v, L ′ , M ′ ):
(1) Define S to be the set of all pairs (L ′′ , M ′′ ) such that

L ′′ ⊆ L ′ \ {f (v)}, M ′′ ⊆ M ′ \ {χ(v)}, and DP u [L ′′ , M ′′ ] = 1 for some neighbor u of v. (2)
Run through all pairs of (L 1 , M 1 ), (L 2 , M 2 ) ∈ S and determine whether L 1 ∩ L 2 = ∅, and whether

M 1 ∪ M 2 ⊆ M ′ \ {χ(v)}.
If there is such a pair, add (L 1 ∪ L 2 , M 1 ∪ M 2 ) to S and repeat this step. Otherwise, continue to the next step.

(3) Set DP v [L ′ , M ′ ] to be 1 if (L ′ \ {χ(v)}, M ′ \ {f (v)}) ∈ S.
The reader should note that the correctness of the batch procedure relies on the fact that we are only required to compute motif occurrences which occur at specified vertices. In this way we are ensured that the connectedness requirement holds. This is stated more precisely in the proof of Lemma 4 below. Lemma 5 then shows that using the batch procedure, we can determine wether our given motif M occurs in G in relatively efficient (i.e. FPT-) time.

Lemma 4 For any vertex

v ∈ V (G), label-subset L ′ ⊆ L, and M ′ ⊆ M, the batch procedure correctly computes DP v [L ′ , M ′ ], assuming DP u [L ′′ , M ′′ ] is given for every neighbor u of v, L ′′ ⊆ L ′ \ {f (v)}, and M ′′ ⊆ M ′ \ {χ(v)}.
PROOF. Let S be the family of pairs computed by the batch procedure. Consider any pair (L ′′ , M ′′ ) ∈ S with L ′′ = L ′ \ {f (v)}. By construction, M ′′ = M ′ \ {χ(v)} and can be written as

M ′′ = M ′′ 1 ∪ • • • ∪ M ′′ ℓ , where each M ′′ i , 1 ≤ i ≤ ℓ
, is a motif that has an occurrence V ′′ i which includes a neighbor of v. Furthermore, each V ′′ i is labeled by a unique set of labels L ′′ i such that

L ′′ i ∩ L ′′ j = ∅ for all 1 ≤ j ≤ ℓ, j = i.
It follows that all the V ′′ i s are pairwise disjoint, and that

V ′ = {v} ∪ V ′′ 1 ∪ • • • ∪ V ′′ ℓ is connected. Hence, V ′ is an occurrence of M ′ = M ′′ ∪ {χ(v)} in G which is labeled by L ′ = L ′′ ∪ {f (v)},
and so invariant (1) is held when the batch procedure sets DP v [L ′ , M ′ ] to 1.

On the other hand, suppose M ′ has an occurrence V ′ , v ∈ V ′ , which is labeled by L ′ . Write M ′′ := M ′ \ {χ(v)}, L ′′ := L ′ \ {f (v)}, and

V ′′ := V ′ \ {v}. Let V ′′ 1 , . . . , V ′′ ℓ be the connected components of the induced subgraph G[V ′′ ]. Since V ′ is connected, every V ′′ i , 1 ≤ i ≤ ℓ, includes a neighbor of v. Furthermore, letting L ′′ i denote the set of labels that f assigns V ′′ i for every 1 ≤ i ≤ ℓ, we have L ′ ⊆ L ′ \ {f (v)} and L ′′ i ∩ L ′′ j = ∅ for all 1 ≤ i, j ≤ ℓ.
It is now easy to see that the batch procedure will eventually compute the pair (M ′′ , L ′′ ) in its second step, and hence DP v [L ′ , M ′ ] will be set to 1 in its final step. 2 Lemma 5 Given a labeling function f : V (G) → {1, . . . , k}, one can use the batch procedure iteratively in order to determine in O(2 6k kn 2 ) time whether there is an occurrence of M in G which is distinctly labeled by f . PROOF. To prove the lemma, let us first analyze the complexity of a single invocation of the batch procedure. In its first step, the batch procedure searches through at most 2 k n motif families, each consisting of at most 2 k motifs. Hence, this step requires O(2 2k kn) time. For the second step, notice that number of distinct motif and label-subset pairs is bounded by 2 2k , and so the number of times the second step is repeated is also bounded by this term. Since each iteration of this step can be computed in O(2 2k k) time, it follows that the second step requires O(2 4k k) time. Accounting also for the third step, the total time of one invocation of the batch procedure is therefore O(2 4k k + 2 2k kn) = O(2 4k kn).

It now can easily be seen that due to Lemma 4, one needs to invoke the batch procedure at most 2 2k n times in order to compute every entry in each dynamic programming table DP v . It follows that in O(2 6k kn 2 ) time one can obtain all necessary information to determine whether M has an occurrence which is distinctly labeled by f , and so the lemma follows. 2 Note that in case M is colorful, the vertex-coloring of G distinctly colors any occurrence of M, and therefore, in this case we can determine whether M occurs in G within the time complexity given in Lemma 5. For general motifs our algorithm is as follows: It first constructs in 2 O(k) • n lg n time a perfect family F of 2 O(k) • lg n functions from V (G) to {1, . . . , k}, using [START_REF] Alon | Color coding[END_REF]. Next for each f ∈ F , it uses the batch procedure to determine whether there is any occurrence of M which is distinctly labeled by f in 2 O(k) • n 2 time (Lemma 5). Since F is perfect, any occurrence of M in G is guaranteed to be distinctly labeled by at least one labeling function f ∈ F , and so by exhaustively searching through all functions in F , our algorithm can determine whether M occurs in G in total 2 O(k) • n 2 lg n time.

Theorem 6 Graph Motif can be solved in 2 O(k) • n 2 lg n time for k := |M|.

Bounded Treewidth Graphs

The treewidth parameter of graphs [START_REF] Robertson | Graph minors. II. Algorithmic aspects of tree-width[END_REF] plays a central role in designing exact algorithms for many NP-hard graph problems (see e.g. [START_REF] Arnborg | Efficient algorithms for combinatorial problems on graphs with bounded decomposability[END_REF][START_REF] Arnborg | Linear time algorithms for NP-hard problems restricted to partial k-trees[END_REF][START_REF] Bodlaender | A tourist guide through treewidth[END_REF][START_REF] Corneil | A dynamic programming approach to the dominating set problem on k-trees[END_REF]). In this section we show that Graph Motif is polynomial-time solvable when G has constant treewidth and M consists of a constant number of colors (but with arbitrary numbers of repeated elements in the multiset of colors). This should be compared with Theorem 3 which implies that Graph Motif is intractable even when M consists of only two colors and G is bipartite with constant degree.

Basic ingredients

We begin by describing the necessary terminology and definitions for our algorithm. We first define tree decompositions and nice tree decompositions of arbitrary graphs in a somewhat nonstandard way tailor-fit for our purposes.

Later we introduce the central ingredient of our algorithm which is a data structure essential for its computation.

Definition 7 (Tree Decomposition [START_REF] Robertson | Graph minors. II. Algorithmic aspects of tree-width[END_REF]) A tree decomposition of a graph G is a pair (T , X ), where X is a set of subgraphs of G (we also refer to elements of X as bags), and T is a tree over X , satisfying the following conditions:

(1) X∈X X = G, and ( 2)

X v = {X ∈ X | v ∈ V (X)} is connected in T for all v ∈ V (G). The width of T is max X∈X |V (X)| -1.
The treewidth of G is the minimum width over all tree decompositions of G. Definition 8 (Nice Tree Decomposition [START_REF] Bodlaender | Treewidth: Algorithmic techniques and results[END_REF]) A tree decomposition (T , X ) of a graph G is nice if T is rooted, binary, and each bag in X is of one of the following four types:

• Leaf nodes X ∈ X are leaves in T , and are singleton graphs which consist of a single isolated vertex v ∈ V (G).

• Introduce nodes X ∈ X have one child

X ′ in T , with V (X) = V (X ′ ) ∪ {v} for some vertex v / ∈ V (X ′ ), and E(X) = E(X ′ ). • Connect nodes X ∈ X have one child X ′ in T , with V (X) = V (X ′ ) and E(X) = E(X ′ ) ∪ {u, v} for some pair of vertices u, v ∈ V (X). • Forget nodes X ∈ X have one child X ′ in T , with V (X) = V (X ′ ) \ {v} for some vertex v ∈ X ′ , and E(X) = E(X ′ ) \ {u, v} ∈ E(X ′ ) . • Join bags X ∈ X have two children X ′ and X ′′ in T with X = X ′ = X ′′ .
Although computing an optimal tree-decomposition of a graph is an NP-complete problem [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF], for graph of constant treewidth there exists a linear-time algorithm due to Bodlaender [START_REF] Bodlaender | A linear time algorithm for finding tree-decompositions of small treewidth[END_REF] for computing an optimal tree-decomposition. Furthermore, given a tree decomposition for a given graph, one can obtain a nice tree decomposition with the same width (and with an at most constantfactor increase of nodes) in linear time (see for instance [START_REF] Bodlaender | Treewidth: Algorithmic techniques and results[END_REF]). Therefore, we assume throughout the remainder of this section that we have a nice tree decomposition (T , X ) of our input graph G.

Definition 9 (X T ) For any subgraph X ∈ X , we let X T denote the subgraph of G defined by

X T = X ′ ∈Des(X) X ′ ,
where Des(X) is the collection of all descendants of X (including X itself ) in T .

Many of the treewidth-based algorithms for NP-complete graph problems apply some form of dynamic-programming computation on the nodes of the tree-decomposition at hand. Our algorithm also follows these lines, by maintaining for each X ∈ X the following data-structure:

Definition 10 (Descriptor, Inventory) A descriptor of a subgraph X of G with respect to a motif M consists of:

• A partition Π = {Π 1 , . . . , Π r } of V (X). • A motif family M = {M 1 , . . . , M r }, where M i ⊆ M, M i = ∅, for all 1 ≤ i ≤ r.
We say that a descriptor as above is positive for X if there exist r pairwise disjoint subsets of vertices in X T , say V 1 , . . . , V r , such that:

• V i ∩ V (X) = Π i , for all 1 ≤ i ≤ r. • V i is an occurrence of M i in X T , for all 1 ≤ i ≤ r.
We define the inventory inv(X) of X as the set of all positive descriptors for X.

Lemma 11 If G has constant treewidth and M consists of a constant number of colors, then any subgraph X ∈ X has a polynomial number of distinct positive descriptors.

PROOF. Suppose that any subgraph X ∈ X has at most α vertices, and that M consists of at most α colors, for some α ∈ N + . The number of different vertex-partitions of any X ∈ X is bounded by α α , and the number of different motif families consisting of at most α motifs, each of size at most n, is bounded by n α 2 . Therefore, the total number of positive descriptors for any X ∈ X is bounded by α α • n α 2 . 2

The algorithm

Our algorithm proceeds as follows. It traverses the nice tree-decomposition of G in bottom-up fashion, and for each node X ∈ X it encounters, it computes inv(X) from the inventory (or inventories) of the child graph(s). We determine that M occurs in G iff M ∈ inv(X) for some subgraph X ∈ X . The following lemma proves the correctness of this strategy.

Lemma 12 M occurs in G iff M ∈ M for some descriptor (Π, M) ∈ inv(X), X ∈ X . PROOF. Suppose M has an occurrence V in G. For any v ∈ V , let X v = {X ∈ X | v ∈ X}
denote the collection of subgraphs which include v. By property (2) of Definition 7, every X v induces a connected subtree T v in T . Furthermore, property (1) of this definition implies that for any u, v ∈ V with {u, v} ∈ E(G), there is a subgraph in X v that includes u, and a subgraph in

X u that includes v. It follows that {u, v} ∈ E(G) implies T u ∩ T v = ∅.
Therefore, since V is connected, T V = v∈V T v is a subtree of T . Hence, there is a subgraph that lies on all paths in T between the root of T and

{X v | v ∈ V }. For this particular subgraph X ∈ {X v | v ∈ V }, V is a subset of vertices in X T with V ∩ V (X) = ∅,
and therefore there is some positive descriptor (Π, M) ∈ inv(X) with M ∈ M. Since the converse direction is trivial, the lemma follows. 2

We proceed to describe our algorithm in terms of the computation needed in order to obtain inventories of nodes in T from the inventories of their children. We use (Π, M) to denote the descriptor of an arbitrary node X in T , and (Π ′ , M ′ ) to denote a descriptor (Π, M) previously computed from the child X ′ of X in T (using double-prime notation in case X has two children). The base cases of this computation are the leaf nodes. The inventory of a leaf node X consists of a single descriptor (Π, M) with Π = {v} and M = {χ(v)} , PROOF. First note that since any motif that occurs in X ′ T occurs also in X T , and since V (X ′ ) = V (X), we have inv(X ′ ) ⊆ inv(X). Furthermore, any motif which occurs in X T and not in X ′ T can be decomposed into two motifs that occur at u and v. The lemma then follows. 2

We are left to describe the more interesting case of join nodes. Let us first define the join operator ⊗ on two partitions of the same vertex set. Let Π ′ and Π ′′ be two partitions of the same vertex set. The partition Π = Π ′ ⊗ Π ′′ corresponds to the equivalence relation formed by taking the transitive closure of Π ′ ∪ Π ′′ (when Π ′ and Π ′′ are both viewed as equivalence relations). In other words, Π is the transitive closure of {(u, v) | uΠ ′ v or uΠ ′′ v}, where uΠ ′ v and uΠ ′′ v respectively denote that u and v are in the same class in Π ′ and in Π ′′ . Now, for a pair of motif families M ′ = (M ′ 1 , . . . , M ′ p ) and M ′′ = (M ′′ 1 , . . . , M ′′ q ) associated as in Definition 10 with the partitions Π ′ and Π ′′ , we define the motif family M = M ′ ⊗ M ′′ = (M 1 , . . . , M r ), such that M i is defined by adding and subtracting colors in the natural manner. That is, if Π ′ i 1 , . . . , Π ′ ix ∈ Π ′ and Π ′′ i 1 , . . . , Π ′′ iy ∈ Π ′′ are the classes of vertices forming Π i ∈ Π, then the motif M i is defined by

M i = j∈{1,...,x} M ′ i j \ χ(Π ′ i j ) j∈{1,...,y} M ′′ i j \ χ(Π ′′ i j ) χ(Π i ). (2)
Lemma 16 Let X be a join node with children X ′ and X ′′ in T . Then inv(X) is the set of all descriptors in inv(X ′ ) and inv(X ′′ ), along with all descriptors (Π ′ ⊗ Π ′′ , M ′ ⊗ M ′′ ) with (Π ′ , M ′ ) ∈ inv(X ′ ) and (Π ′′ , M ′′ ) ∈ inv(X ′′ ).

PROOF. First observe that inv(X ′ ) ⊆ inv(X) and inv(X ′′ ) ⊆ inv(X) follow immediately from the definition. To show that any descriptor (Π ′ ⊗ Π ′′ , M ′ ⊗ M ′′ ) with (Π ′ , M ′ ) ∈ inv(X ′ ) and (Π ′′ , M ′′ ) ∈ inv(X ′′ ) is also in inv(X) consider an arbitrary class Π i ∈ Π along with its corresponding motif M i ∈ M, and let Π ′ i 1 , . . . , Π ′ ix ∈ Π ′ and Π ′′ i 1 , . . . , Π ′′ iy ∈ Π ′′ be the classes of vertices from which Π i originated, and M ′ i 1 , . . . , M ′ ix and M ′′ i 1 , . . . , M ′′ iy be the motifs corresponding to these vertex classes in inv(X ′ ) and inv(X ′′ ) respectively. We will argue that the motif M i ∈ M has an occurrence

V i with V i ∩ V (X) = Π i .
To see this, take V ′ i 1 , . . . , V ′ ix and V ′′ i 1 , . . . , V ′′ iy to be the occurrences of M ′ i 1 , . . . , M ′ ix and M ′′ i 1 , . . . , M ′′ iy in X ′ T and X ′′ T , respectively, and define V i ⊆ V (X T ) by

V i = V ′ i 1 ∪ • • • ∪ V ′ ix ∪ V ′′ i 1 ∪ • • • ∪ V ′′ iy .
Then V i is colored by the colors of M i according to [START_REF] Althaus | Approximating the interval constrained coloring problem[END_REF], and by the requirements of V ′ i 1 , . . . , V ′ ix and V ′′ i 1 , . . . , V ′′ iy according to Definition 10. Furthermore, V i ∩ V (X) = Π i . Now, for any pair of vertices u, v ∈ V (X), if u and v are in the same class in Π ′ or Π ′′ , then u and v are connected in X T [V i ], since they are even connected in a subset of V i . Thus, as Π is the transitive closure of Π ′ ∪ Π ′′ , it follows that all vertex-pairs in Π i are connected in X T [V i ]. As all vertex subsets V ′ i 1 , . . . , V ′ ix , V ′′ i 1 , . . . , V ′′ iy are connected in X T [V i ] and have non-empty intersection with Π i , there is a path from any vertex in V i to Π i . Combining the two facts above together we get that V i is connected in X T .

To prove the converse direction of the lemma, we show that for any positive descriptor (Π, M) of X ′ which is not in the inventories of X ′ and X ′′ , there are two descriptors (Π ′ , M ′ ) ∈ inv(X ′ ) and (Π ′′ , M ′′ ) ∈ inv(X ′′ ) with Π = Π ′ ⊗ Π ′′ and M = M ′ ⊗ M ′′ . first observe any motif M i ∈ M that does not occur in X ′ T nor in X ′′ T , has an occurrence V i which can be decomposed into its connected components

V ′ i 1 , . . . , V ′ ix in X ′ T [V i ],
and into the connected components

V ′′ i 1 , . . . , V ′′ iy in X ′′ T [V i ].
These vertex-subsets are all occurrences of sub-motifs of M i , and moreover, the families {V ′ i 1 ∩V (X), . . . , V ′ ix ∩V (X)} and

{V ′′ i 1 ∩ V (X), . . . , V ′′ iy ∩ V (X)} both partition V i ∩ V (X).
Taking the transitive closure of the union of both these partitions, we must get V i ∩ V (X), as otherwise V i cannot be connected in X T . Continuing in this way for all motifs in M, we get that Π = Π ′ ⊗ Π ′′ and M = M ′ ⊗ M ′′ . 2

Theorem 17 If G has constant treewidth and M has a constant number of colors, then Graph Motif is polynomial-time solvable.

PROOF. The algorithm is as described below. Given an instance (G, M) of Graph Motif, it first computes in linear time a nice tree-decomposition (T , X ) of G, and then it traverses T in bottom-up fashion, computing the inventories of each subgraph X ∈ X it encounters from the inventories of its child subgraph(s) in T . The algorithm then determines that M occurs in G iff M is in a motif family of a positive descriptor of some X ∈ X . Correctness of this approach follows from Lemma 12, and from the correctness of lemmas 13 through 16. Furthermore, lemmas 13 through 16 together imply that computing the inventory of any subgraph requires at most quadratic time in the total size of the inventory of its children. Hence, as each inventory consists of a polynomial number of descriptors (according to Lemma 11), this can be performed in polynomial-time. Therefore, as |X | = O(n) nodes, the entire algorithm requires polynomial-time. 2

Parameterizing by the Number of Colors

Although Theorem 17 gives a nice complementary result to the sharp hardness result of Theorem 3, it still leaves a certain gap. In the following section we aim to close this gap, by proving that Graph Motif, parameterized by the number of colors c in M, is W[1]-hard for trees. We refer readers to [START_REF] Downey | Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF] for more information on the W[1] class, and the implications of an FPT-time algorithm for a W[1]-hard problem.

Theorem 18

The Graph Motif problem, parameterized by the number of colors c in the motif, is W[1]-hard for trees.

PROOF. We present a parameterized reduction from Clique which is known to be W[1]-hard [START_REF] Downey | Parameterized Complexity[END_REF]. Recall that in Clique we are given a simple graph H and an integer κ, the parameter, and we are asked to determine whether H has a subset of κ vertices which are pairwise adjacent. Given an instance H, κ of Clique, we describe a rooted tree G = T colored with 1 + κ + 2κ(κ -1) + κ The color of each node in S(i) is b(i). • From each node s(i, u) hang κ -1 groups of paths. The groups are P (i, u, j) for every j ∈ {1 . . . , κ} \ {i}. There is one path p(i, u, j, v) ∈ P (i, u, j) for each edge {u, v} ∈ E(H) that is incident to u in H.

The path p(i, u, j, v) begins with a vertex colored c(i, j) and ends with a vertex colored d(i, j), and otherwise consists of some number m(i, u, j, v) of internal vertices colored by e(i, j) = e(j, i). There is an important detail to note here. If i < j, then c(i, j) and c(j, i) are different colors, and likewise d(i, j) and d(j, i), whereas e(i, j) and e(j, i) are the same color. We call the e(i, j)'s the edge colors.

The number m(i, u, j, v) is calculated as follows. Number the edges in E(H) from 1 to m, letting l(uv) denote the number assigned to the edge {u, v} ∈ E(H). We define:

m(i, u, j, v) =    l(uv) if i < j 3m -l(uv) if i > j.
The motif M consists of one-of-each for every color other than the edge colors, and 3m elements colored by each edge color. Thus, M consists of c = 1 + κ + 2κ(κ -1) + κ 2 different colors, and |M| = 1 + κ + 2κ(κ -1) + 3m κ 2 . This completes the construction of our instance (G, M), c for Graph Motif. Illustrations of the construction are given in Figures 3 and4.

We claim that H has a subset of κ pairwise adjacent vertices if and only if T has a subtree T ′ which is an occurrence of M. Suppose that the vertices v 1 , ..., v κ are pairwise adjacent in H. The subtree T ′ consists of:

p(i, u, j, v 1 ) path p(i, u, j, v 2 ) path p(i, u, j, v d(u) ) s(i, v) P (i, v, 1) P (i, v, 2) P (i, v , κ) c(i, j) c(i, j) c(i, j) e(i, j) e(i
• The root which is colored a.

• The κ children of the root s(i, v i ) for all 1 ≤ i ≤ κ, where s(i, v i ) is colored b(i).

• The κ(κ -1) paths p(i, v i , j, v j ). The path p(i, v i , j, v j ) begins with a node colored c(i, j) and ends with a node colored d(i, j) for all 1 ≤ i, j ≤ κ, i = j. Note that the path p(i, v i , j, v j ) is pendant from s(i, v i ) since v i and v j are adjacent in H. Together, the two complementary paths p(i, v i , j, v j ) and p(j, v j , i, v i ) contain 3m nodes colored e(i, j).

In the other direction, suppose that the subtree T ′ of T is an occurrence of M. Then T ′ must include the root of T , since it is the only node colored a. Furthermore, T ′ must contain exactly one node in each of the groups S(i), 1 ≤ i ≤ κ, since nodes in each S(i) are all colored b(i). Suppose these nodes are s(1, v 1 ), . . . , s(κ, v κ ). We argue that the vertices v 1 , ..., v κ are pairwise adjacent in H.

In order for T ′ to be an occurrence of M in T , T ′ must contain exactly one pendant path in each of the groups of paths P (i, v i , j) for any 1 ≤ i, j ≤ κ, i = j, and nothing further. To see this, note that T ′ must contain at least one path in each of the groups of paths P (i, v i , j) in order for T ′ to contain a node colored d(i, j). But containing one such path prevents T ′ from including any node of other paths in P (i, v i , j), else T ′ would contain too many nodes of color c(i, j).

It follows that for any pair of indices i, j with 1 ≤ i < j ≤ κ, T ′ includes exactly two paths p(i, v i , j, x) and p(j, v j , i, y) that contain nodes of color e(i, j) = e(j, i). Since M contains exactly 3m elements colored by e(i, j), it follows that x = v j and y = v i , since p(i, v i , j, v j ) and p(j, v j , i, v i ) are the only two paths in T with nodes colored e(i, j) that together have exactly 3m nodes of this color. But then, by the construction of T , v i and v j must be adjacent in H. 2

Summary

In this paper we studied the Graph Motif problem, a natural patternmatching problem in graphs which was introduced by Lacroix, Fernandes, and Sagot to model applications in metabolic network analysis [START_REF] Lacroix | Motif search in graphs: Application to metabolic networks[END_REF]. We presented an extensive complexity analysis of the problem which entailed two positive results, and three negative results. Our analysis focused on finding natural parameters that determine the complexity of the problem. To this extent, we identified two such natural parameters: The size of the motif, and the number of different colors in the motif. We believe however that there are more parameters to be explored, and identifying these is left for further research.

Another direction for possible future research is classes of dense graphs. The reader should also note that all of our hardness results use graphs that are quite sparse, which makes the task of assuring connectivity of potential motif occurrences difficult. On the other hand, Graph Motif is trivial on the complete graph. We conjecture that there are many other natural and interesting dense graph classes for which Graph Motif becomes tractable.

Finally, we conclude with a list of three concrete questions that were left open by this paper:

• Is Graph Motif in FPT when parameterized by the treewidth of the graph, and the number of different colors in the motif is taken as a constant? • In light of Theorem 1, Theorem 18, and Lemma 2, is Graph Motif restricted to trees fixed-parameter tractable when parameterized by both the number of colors of the motif, and the maximum number of occurrences of a color in the tree? • Does Graph Motif have a polynomial-size kernel?

2 colors.

 2 We let m denote the number of edges of H, i.e., m = |E(H)|. • The root of T is colored a. • The root has κ • |V (H)| children organized into κ groups S(1) . . . S(κ). The group of |V (H)| children S(i) consists of the nodes s(i, u), where u ∈ V (H).

Figure 3 .

 3 Figure 3. A schematic description of the the first two levels of the tree.

  path

  , u, j, v d(u) ) vertices P (i, v, j), j ∈ {1, 2, . . . , κ} \ {i}

Figure 4 .

 4 Figure 4. A schematic description of the group of paths which hang from the node s(i, v) ∈ S(i). Is is assumed here that N (u) = {v 1 , v 2 , . . . , v d(u) }.

  s ′ n } and S ′′ = {s ′′ 1 , s ′′ 2 , . . . , s ′′ n } are copies of S, and E 1 , E 2 , E 3 , E 4 are defined by:

Supported by the Australian Research Council, by a Fellowship to the Durham University Institute for Advanced Studies, and by a William Best Fellowship at Grey College while the paper was in preparation. 2 Most of the work on this is paper was done during the graduate studies of the University of Haifa. At the time, the author was supported by the Adams Fellowship of the Israel Academy of Sciences and Humanities.

where v is the single vertex of X. The computation done on any single child node in T is almost equally easy, and is given for the sake of completeness in the following three lemmas.

Lemma 13 Let X be an introduce node with child

where

PROOF. Clearly, (Π, M) in the lemma is a positive descriptor of X, assuming (Π ′ , M ′ ) is positive for X ′ . Furthermore, there are no other positive descriptors of X, since X ′ T and X T differ only by vertex v, and v is isolated in X T . 2 Lemma 14 Let X be a forget node with child

) and Π ′ i = {v}, and all descriptors (Π, M) with

where

PROOF. The lemma follows from the easy observation that any motif

Lemma 15 Let X be a connect node with child X ′ in T such that E(X) = E(X ′ ) ∪ {u, v} for some {u, v} / ∈ E(X ′ ). Then inv(X) is the set of all descriptors in inv(X ′ ), along with all descriptors (Π, M) with

where M ′ = (M ′ 1 , . . . , M ′ r ) and Π ′ = (Π ′ 1 , . . . , Π ′ r ) form a positive descriptor of X ′ , {u, v} Π ′ i , Π ′ j and {u, v} ⊆ Π ′ i ∪ Π ′ j .