Laurent Bulteau
email: laurent.bulteau@univ-nantes.fr

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

Minghui Jiang
email: mjiang@cc.usu.edu

Irena Rusu
email: irena.rusu@univ-nantes.fr

Tractability and Approximability of Maximal Strip Recovery

An essential task in comparative genomics is usually to decompose two or more genomes into synteny blocks, that is, segments of chromosomes with similar contents. In this paper, we study the Maximal Strip Recovery problem (MSR) [Zheng et al. 07], which aims at finding an optimal decomposition of a set of genomes into synteny blocks, amidst possible noise and ambiguities. We present a panel of new or improved FPT and approximation algorithms for the MSR problem and its variants. Our main results include the first FPT algorithm for the variant δ-gap-MSR-d, an FPT algorithm for CMSR-d and δ-gap-CMSR-d running in time O(2.360 k poly(nd)), where k is the number of markers or genes considered as erroneous, and a (d + 1.5)-approximation algorithm for CMSR-d and δ-gap-CMSR-d.

Introduction

An essential task in comparative genomics is usually to decompose two or more genomes into synteny blocks, that is, segments of chromosomes with similar contents. This task is non-trivial when the genomic maps contain noise and ambiguities, which need to be removed before we can give a precise synteny block decomposition. This is the objective of the Maximal Strip Recovery problem (MSR) [START_REF] Zheng | Removing noise and ambiguities from comparative maps in rearrangement analysis[END_REF]: to delete a set of markers (genes) from the genomic maps until the remaining markers can be partitioned into a set of strips (synteny blocks) of maximum total length.

We review some definitions. A genome consists of one or more chromosomes; each chromosome is a sequence of genes. Correspondingly, a genomic map consists of one or more sequences of gene markers. Each marker is a signed integer representing a gene: the absolute value of the integer represents the family of the gene; the sign of the integer represents the orientation. A marker has duplicates if it is contained more than once in some genomic map, possibly in different orientations. A strip of d ≥ 2 genomic maps is a sequence of at least two markers appearing consecutively in each map, such that the order of the markers and the orientation of each marker are either both preserved or both reversed. The reversed opposite of a sequence s = x 1 , . . . , x h is -s = -x h , . . . , -x 1 . The MSR problem on d input maps is the following maximization problem MSR-d [START_REF] Chen | On recovering syntenic blocks from comparative maps[END_REF][START_REF] Zheng | Removing noise and ambiguities from comparative maps in rearrangement analysis[END_REF]:

Problem MSR-d Input: d genomic maps G 1 , . . . , G d each containing n markers without duplicates. Solution: d subsequences G ′ 1 , . . . , G ′ d of G 1 , . . . , G d respectively, each containing the same ℓ markers, such that all the markers in G ′ 1 , . . . , G ′ d can be partitioned into strips. Parameter: the number ℓ of selected markers.

The maximization problem MSR-d that maximizes the parameter ℓ, the number of selected markers, has a complement minimization problem called CMSR-d [START_REF] Wang | On the tractability of maximal strip recovery[END_REF][START_REF] Jiang | Inapproximability of maximal strip recovery: II[END_REF] that minimizes the parameter k = nℓ, the number of deleted markers. For genomic maps of close species with few errors, k can be much smaller than ℓ, thus approximation and FPT algorithms are sometimes more relevant for CMSR than for MSR. We refer to Figure 1 for an example.

Given d subsequences G ′ 1 , . . . , G ′ d of d genomic maps G 1 , . . . , G d , respectively, the gap between two consecutive markers a and b of G ′ i is the number of markers appearing between a and b in G i , a and b excluded. The gap of a strip s is the maximum gap between any two consecutive markers of s in any map G ′ i . The deleted markers between markers of a strip correspond to noise and ambiguities, which occur infrequently. A synteny block is a segment of chromosomes that remain undisrupted by genome rearrangements during evolution. Consecutive elements of a synteny block can only be separated in a dataset due to noise and ambiguities. Thus a strip having a large gap is unlikely to correspond to a synteny block; see [START_REF] Choi | Algorithms for the extraction of syntheny blocks from comparative maps[END_REF] for an empirical analysis. This leads to the following gap-constrained variant of MSR-d [START_REF] Bulteau | Maximal strip recovery problem with gaps: hardness and approximation algorithms[END_REF]:

Problem δ-gap-MSR-d Input: d genomic maps G 1 , . . . , G d each containing n markers without dupli- cates. Solution: d subsequences G ′ 1 , . . . , G ′ d of G 1 , .
. . , G d respectively, each containing the same ℓ markers, such that all the markers in G ′ 1 , . . . , G ′ d can be partitioned into strips, and such that each strip has gap at most δ. Parameter: the number ℓ of selected markers.

G1 = 1 5 -3 2 6 4 8 7 G ′ 1 = 1 5 -3 6 8 G2 = 1 5 -3 -8 7 -6 2 4 G ′ 2 = 1 5 -3 -8 -6 G3 = -8 2 7 -6 -4 3 -5 -1 G ′ 3 = -8 -6 3 -5 -1
Fig. 1. Three genomic maps G1, G2, G3, and an optimal solution G ′ 1 , G ′ 2 , G ′ 3 for MSR-3. The markers 2, 4, 7 are deleted; the markers 1, 3, 5, 6, 8 are selected in two strips 1, 5, -3 and 6, 8 of

G ′ 1 , G ′ 2 , G ′ 3 .
The gap of the strip 1, 5, -3 is 0; the gap of the strip 6, 8 is 2, since there are 2 markers between -8 and -6 in G3.

No doubt that MSR-d is a more elegant problem from a theoretical perspective, but δ-gap-MSR-d could be more relevant in biological applications. The gap-constrained variant of CMSR-d, denoted δ-gap-CMSR-d, can be similarly defined. Similarly to MSR-d and CMSR-d, the parameter for δ-gap-MSR-d is ℓ, and the parameter for δ-gap-CMSR-d is k. In most cases, δ and d are assumed to be constants, although our FPT algorithm in Theorem 3 does not depend on this assumption and can take δ and d as parameters besides ℓ. There is no known direct reduction from δ-gap-MSR-d to MSR-d or vice versa. Although the gap constraint appears to be an additional burden that the algorithm has to take care of, it also limits the set of candidate strips and their intersection pattern, especially when δ is small, which may make the problem easier to handle.

For the four variants of the maximal strip recovery problem, MSR-d, CMSRd, δ-gap-MSR-d, and δ-gap-CMSR-d, several hardness results have been obtained [START_REF] Chen | On recovering syntenic blocks from comparative maps[END_REF][START_REF] Wang | On the tractability of maximal strip recovery[END_REF][START_REF] Jiang | Inapproximability of maximal strip recovery[END_REF][START_REF] Bulteau | Maximal strip recovery problem with gaps: hardness and approximation algorithms[END_REF][START_REF] Jiang | On the parameterized complexity of some optimization problems related to multiple-interval graphs[END_REF][START_REF] Jiang | Inapproximability of maximal strip recovery: II[END_REF], and a variety of algorithms have been developed, including heuristics [START_REF] Zheng | Removing noise and ambiguities from comparative maps in rearrangement analysis[END_REF], approximation algorithms [START_REF] Chen | On recovering syntenic blocks from comparative maps[END_REF][START_REF] Bulteau | Maximal strip recovery problem with gaps: hardness and approximation algorithms[END_REF][START_REF] Jiang | Exact and approximation algorithms for the complementary maximal strip recovery problem[END_REF], and FPT algorithms [START_REF] Wang | On the tractability of maximal strip recovery[END_REF][START_REF] Jiang | Exact and approximation algorithms for the complementary maximal strip recovery problem[END_REF]. For example, it is known that MSR-d admits a 2d-approximation algorithm for any d ≥ 2 [START_REF] Chen | On recovering syntenic blocks from comparative maps[END_REF][START_REF] Jiang | Inapproximability of maximal strip recovery: II[END_REF], and that δ-gap-MSR-d admits a 2d-approximation algorithm for any d ≥ 2 and δ ≥ 1 and a 1.8-approximation algorithm for d = 2 and δ = 1 [START_REF] Bulteau | Maximal strip recovery problem with gaps: hardness and approximation algorithms[END_REF]. Refer also to [START_REF] Zhu | Efficient exact and approximate algorithms for the complement of maximal strip recovery[END_REF][START_REF] Jiang | Exact and approximation algorithms for the complementary maximal strip recovery problem[END_REF] for some very recent development on the CMSR problem parallel to our work. The following two theorems summarize some basic hardness results regarding these problems: In this paper, we present a panel of new or improved FPT and approximation algorithms. Our positive results, together with some previous results, are summarized in Table 1. Due to space constraints, we present only three main results in this extended abstract. These results are (i) an FPT algorithm for δ-gap-MSR-d running in time 2 O(dδℓ) n, (ii) an FPT algorithm for CMSR-d and δ-gap-CMSR-d, running in time O(2.360 k poly(nd)), and (iii) a (d+1.5)-approximation algorithm for CMSR-d and δ-gap-CMSR-d.

Preliminaries. Given a set of genomic maps (either the set of d original maps given as input or some set of reduced maps during the execution of a recursive algorithm), if a maximal sequence of markers form a strip in these maps, then these markers are either all selected or all deleted in any optimal solution. This is because any solution that includes only a subset of the markers in a strip can be extended to a better solution that includes all markers in that strip. Hence, these markers can be treated as an atomic unit, and called a super-marker, whose size is the number of markers it contains. Note that the size of a super-marker is

δ-gap-MSR-d (δ ≥ 4) 2d [1] 1-gap-MSR-d (d ≥ 3) 0.75d + 0.75 + ǫ [See full version] 1-gap-MSR-2 1.8 [1] 2-gap-MSR-d 1.5d + ǫ [See full version] 3-gap-MSR-d 1.5d + 0.75 + ǫ [See full version] CMSR-d (d ≥ 3) d + 1.5 [Theorem 5, Section 4] CMSR-2 3 [5] δ-gap-CMSR-d d + 1.5 [Theorem 5, Section 4] 1-gap-CMSR-2 2.

[See full version]

Table 1. Positive results for variants of MSR.

always at least 2. A marker that does not belong to any super-marker is a singlemarker. We use the term single-super-marker to refer to either a single-marker or a super-marker. A common step of our algorithms is to partition the markers into single-super-markers. If a set of genomic maps contains only super-markers, then we have a straightforward decomposition into strips, without deleting any marker.

For two markers or two single-super-markers u and v, denote by gap(u, v) the set of markers that appear between u and v in at least one of the maps; clearly gap(u, v) = gap(v, u). We call v a candidate successor (resp. candidate predecessor ) of u, and write v ≻ u (resp. v ≺ u), if the following two conditions are satisfied: (1) u, v (resp. v, u ) is a strip (satisfying the δ-gap constraint, if necessary) in the reduced maps with all markers in gap(u, v) deleted, (2) u, x, v (resp. v, x, u ) cannot be a strip for any x ∈ gap(u, v). The relation ≺ always refers to two markers of the original map, even if we temporarily work with reduced maps. Note that v is a candidate successor of u if and only if u is a candidate predecessor of v. In the example of Figure 1 Algorithm 1 FPT algorithm for δ-gap-MSR-d

1: Gather all pairs of markers (u, v) such that u ≺ v. Such pairs are called candidate pairs. 2: For each marker u, create a boolean variable xu. 3: For each candidate pair (u, v), create a conjunctive boolean formula fu,v = xu ∧ xv ∧ ¬xg 1 ∧ . . . ∧ ¬xg s , where g1, . . . , gs are the markers in gap(u, v). 4: Delete the variables that do not appear in any formula or appear only in negative form in the formulas. 5: Enumerate all possible assignments to the remaining variables to find an optimal assignment that maximizes the number of variables appearing in positive form in at least one satisfied formula. Delete all markers whose variables are not assigned true values. 6: Return the resulting genomic maps.

Our algorithm is based on a simple idea: create a boolean variable for each marker (where true means the marker is selected in a solution, false that it is unselected), then test all possible assignments to find an optimal solution. To reduce the time complexity of this brute-force approach, we add a pruning step (line 4) to delete certain variables whose markers cannot appear in any optimal solution. The remaining variables form a "kernel" on which we can find an optimal solution in FPT time.

Given an optimal solution, which selects ℓ markers, we call a marker active if it appears within distance at most δ from a selected marker in some map. Then each map contains at most ℓδ + ℓ 2 δ unselected active markers: at most δ after each selected marker, and at most δ before the first marker of each strip (note that the number of strips of this optimal solution is at most ℓ/2). The total number of active markers is at most ℓ + d(ℓδ

+ ℓ 2 δ) = ℓ(1 + 3 2 dδ
). The pruning step in line 4 depends on the crucial observation that a nonactive marker can never appear in positive form. Suppose for contradiction that a non-active marker u appears in a candidate pair with some marker v. Then u is at distance at most δ + 1 from v in each map. Since u, as a non-active marker, must be at distance at least δ + 1 from the selected markers in all maps, no selected markers can appear between u and v in any map, thus we can extend the optimal solution by selecting both u and v, a contradtiction.

Note that in line 4 the variables appearing at least once in positive form are never deleted, hence no formula becomes empty after deleting the variables that appear only in negative form. After line 4, the number of remaining variables is at most the number of active markers, which is at most t = ℓ(1 + 3 2 dδ). Correspondingly, the number of formulas is at most t(δ +1), because any candidate pair consists of an active marker and one of the δ + 1 markers immediately following it in the first map. Each formula contains at most dδ + 2 variables.

The time complexity of line 1 is O(ndδ). In lines 2 and 3, the variables can be created in time O(n), and the formulas can be created in time O(t(δ +1)(dδ + 2)) = O(tdδ 2 ). Similarly, line 4 can be executed in time O(n + tdδ 2 ). Finally, line 5 can be executed in time O(2 t t(δ + 1)(dδ + 2)) = O(2 t tdδ 2 ), so the overall time complexity is O(2 t tdδ 2 + ndδ).

An FPT Algorithm for CMSR-d and δ-gap-CMSR-d

In this section, we design an FPT algorithm for CMSR-d and δ-gap-CMSR-d, where the parameter is k, the number of deleted markers in the optimal solution.

Since super-markers are already strips in the input genomic maps, one may naturally be tempted to come up with the following algorithm. First, find all super-markers, and add them to the solution. Then, delete a subset of singlemarkers until all markers in the resulting maps can be partitioned into strips. The correctness of this algorithm on finding an exact solution, however, depends on the assumption that in some optimal solution no super-marker needs to be deleted, which is false as can be seen in the following counter-example:

G 1 = 4 1 2 3 5 6 7 G 2 = 6 -3 -2 -1 7 4 5
Here 1, 2, 3 forms a super-marker, but the optimal solution deletes 1, 2, 3 and selects 4, 5 and 6, 7 instead. An easy generalization of this counter-example shows that any super-marker of size strictly less than 2d is not guaranteed to be always selected in some optimal solution.

We observe that an FPT algorithm for CMSR-d and δ-gap-CMSR-d can be easily obtained using the bounded search tree method. In any feasible solution for the two problems, a single-marker x must be either deleted or selected. If x is selected, then at least one of its neighbors must be deleted. Since x has at most 2d neighbors (at most two in each map), this leads to a very simple algorithm running in time O((2d + 1) k poly(nd)). Parallel to our work, Jiang et al. [START_REF] Jiang | Exact and approximation algorithms for the complementary maximal strip recovery problem[END_REF] presented an FPT algorithm running in time O(3 k poly(nd)). We next describe a carefully tuned FPT algorithm running in time O(2.360 k poly(nd)).

For convenience, we consider the decision problem associated with CMSR-d and δ-gap-CMSR-d, for which the parameter k is part of the input. x ← the left-most single-marker in G1 6: else 7:

return true 8: s ← the first single-super-marker following x in G1 9: // 1: Assume x is deleted in the optimal solution 10: Create G ′ 1 , . The efficiency of Algorithm 2 is made possible by several optimizations justified by the following lemmas. These lemmas are all based on very simple observations. Note that although we consider the decision problem for simplicity, Algorithm 2 can be adapted to directly return the actual solution, instead of "true", when the input instance indeed has a solution of size k. Recall that the relation ≺ in lines 14-15 is defined for markers in the original maps -it remains unchanged through recursive calls, and can be precomputed. Lemma 2. Let x be a single-marker and w a super-marker. If x is selected in an optimal solution, and w is a candidate successor or predecessor of x with exactly one marker in gap(x, w), then there is an optimal solution where the marker in gap(x, w) is deleted. Lemma 3. Let x be a single-marker and s a single-super-marker. If s appears in gap(x, w) for each w that is a candidate successor or predecessor of x, then s itself cannot be a candidate successor or predecessor of x, and any solution selecting x deletes s. Lemma 4. (In this lemma we assume there is no gap constraint.) Let x be a single-marker and y a candidate successor of x such that all markers in gap(x, y) are single-markers and candidate successors of x. If x is part of some strip in an optimal solution, but not at the end of this strip, then there is an optimal solution where x, y is part of some strip. Lemma 5. Let x be the first single-marker in G ′ 1 . Let z be a candidate predecessor of x such that all markers in gap(x, z) are size-2 super-markers and candidate predecessors of x. If x appears at the end of a strip in an optimal solution, then there is an optimal solution where z, x is at the end of some strip.

In addition to these four optimizations, we also use a "delayed commitment" optimization which is the equivalent of Lemma 4 when we need to observe a gap constraint. We consider the case where x is part, but not at the end, of some strip in the optimal solution, and where y is a single-marker and a candidate successor of x such that all markers in gap(x, y) are single-markers and candidate successors of x. In this case we delete all markers in gap(x, y) to make x, y a strip, but keep the possibility of replacing y by any marker y 1 ∈ gap(x, y), should necessity arise. We denote this unspecified marker by [y | gap(x, y)].

To prove the correctness of Algorithm 2, we need the following easy lemma from [START_REF] Zheng | Removing noise and ambiguities from comparative maps in rearrangement analysis[END_REF]: Lemma 6. [10, Proposition 2] We can decompose the strips of any optimal solution in such a way that (1) each strip contains at most 3 single-super-markers and (2) each strip containing 3 single-super-markers starts and ends with a singlemarker.

Let OPT be any optimal solution, and let us decompose the strips of OPT as in the above lemma. We show by induction that the solution found by Algorithm 2 has the same size as OPT. Let x be the left-most single-marker in G 1 , then exactly one of the following three cases is true:

1: x is deleted in OPT, 2.a: There exists a single-super-marker y such that x, y is part of a strip in OPT, 2.b: There exists a super-marker z such that z, x is a strip in OPT.

Note that in case 2.b, z cannot be a single-marker since it is to the left of x in G 1 . By our choice of x, case 2.a can be split into the following two subcases: 2.a.i: There exists a single-super-marker y such that x, y is a strip in OPT, 2.a.ii: There exists a single-super-marker y and a single-marker y ′ such that

x, y, y ′ is a strip in OPT.

Refer to Algorithm 2. In case 1, a solution is found in lines 9-12 of the function recurse. In case 2, i.e. in the case where x is part of an optimal solution, if either Lemma 2 or Lemma 3 can be applied, then again a solution is found. Otherwise, we are in case 2.a or 2.b.

Suppose we are in case 2.a. If y ∈ Y 0 , then the function recurse 2a tests a branch in which x, y becomes part of some strip. Otherwise, there exists some Algorithm 3 (d + 1.5)-approximation for δ-gap-CMSR-d and CMSR-d 1: X ← { triples of markers (z, x, y) | z ≺ y and gap(z, y) = {x} } 2: Partition the markers into single-super-markers. 3: for all (z, x, y) ∈ X do 4:

if x, y and z are not deleted and y or z is a single-marker then 5: Delete x.

6:

Re-create all super-markers. 7: Delete all remaining single-markers. 8: Return the resulting genomic maps. y 0 ∈ Y satisfying the conditions of Lemma 4. If there is no gap constraint, y is replaced by y 0 , which does not change the size of the solution. If there is a gap constraint, y is replaced by the unspecified marker u = [y 0 | Y ], and we look further in case 2.a.i or 2.a.ii.

In case 2.a.i, we can replace y by y 0 since gap(x, y 0 ) has no more markers than gap(x, y). In case 2.a.ii, we can replace y by any y 1 such that x ≺ y 1 ≺ y ′ , since gap(x, y) ∪ {y} ∪ gap(y, y ′ ) is the same set as gap(x, y 1 ) ∪ {y 1 } ∪ gap(y 1 , y ′ ). This is what happens in case 2.b of a subsequent recursive call in which y ′ becomes the left-most single-marker in G 1 .

Suppose we are in case 2.b. If z ∈ Z 0 , then the function recurse 2b tests a branch in which z, x becomes a strip. Otherwise, Lemma 5 can be applied, which leaves the size of the optimal solution unchanged. In line 9 of recurse 2b, if s becomes the left-most single-marker in G 1 in the next recursive call of recurse, it cannot be at the end of a strip because x is already at the end of a strip.

This completes the correctness proof. An anonymous reviewer of an earlier version of this paper commented that perhaps some further properties of the optimal solution, besides those already described in our lemmas, might be used to improve the time complexity further. This may be true, but we believe that such improvement would require significantly different ideas. Let k be the number of deleted markers in an optimal solution. Then the number of single-markers in the input maps is at most (2d + 1)k because each single-marker is either deleted or adjacent to a deleted marker. This immediately yields a (2d + 1)-approximation algorithm: simply delete all single-markers. We refer to Figure 2 for a tight example for the (2d + 1)-approximation algorithm. Observe that after one single-marker is deleted, many other singlemarkers may be merged into strips. Algorithm 3 first identifies (line 1) all triples of markers (z, x, y) such that z and y can be merged into a strip z, y after x is deleted, then successively deletes (lines 2-6) "cost-efficient" single-markers x that can reduce at least one other single-marker y or z, and finally removes (line 7) the remaining single-markers. Lemma 7. For each triple (z, x, y) in the set X in Algorithm 3, at least one of the three markers x, y, z must be deleted in any feasible solution.

G1 = z d y d • • • z3y3 z2y2 z1 x y1 G2 = z1y1 z2 x y2 z3y3 • • • z d y d G3 = z1y1 z2y2 z3 x y3 • • • z d y d • • • • • • • • • • • • • • • • • • G d = z1y1 z2y2 z3y3 • • • z d x y d
Proof. We prove the lemma by contradiction. Suppose that all three markers x, y, z are selected in a solution. Assume wlog that the sequence z, x, y appears in some map. Then x must be in the same strip as z or y. Assume wlog that z, x is part of some strip. Then z ≺ x. Recall that z ≺ y. Thus x and y are both candidate successors of z. By Lemma 1a, we have y ∈ gap(z, x), thus y must be deleted: a contradiction.

⊓ ⊔

We next prove the approximation ratio of Algorithm 3. Let O be the set of deleted markers in an optimal solution; |O| = k. For each marker x / ∈ O, we define two sets Γ succ (x) and Γ pred (x) as follows. If x is followed by a marker y in a strip of O, Γ succ (x) = gap(x, y); otherwise x is the last marker of its strip, Γ succ (x) = ∅. If x is preceded by a marker z in a strip of O, Γ pred (x) = gap(z, x); otherwise x is the first marker of its strip, Γ pred (x) = ∅. Then, for each marker x / ∈ O, define γ(x) = |Γ succ (x)| + |Γ pred (x)|, and for each marker x ∈ O, define γ(x) = 0.

Refer to Algorithm 3. Let D be the set of markers deleted in line 5, let S be the set of single-markers that are merged into super-markers in line 6, and let R be the set of markers deleted in line 7

. Let R 1 = {r ∈ R | γ(r) = 1} and R 2 = {r ∈ R | γ(r) ≥ 2}. Note that if
x is a single-marker at the beginning of the algorithm, then γ(x) = 0 if and only if x ∈ O. Thus we have a partition R = (R ∩ O) ∪ R 1 ∪ R 2 . Also note that each marker x ∈ O is counted by γ at most twice in each map: at most once in some Γ pred (y), and at most once in some Γ succ (z). Thus we have the following inequality:

x single-marker γ(x) ≤ 2dk.

(1)

Each marker x ∈ D has a corresponding triple (z, x, y) ∈ X, where z or y is a single-marker. After x is deleted in line 5, z and y are merged into the same super-marker in line 6. Thus we have the following inequality:

|D| ≤ |S|. (2)
For each marker x ∈ D -O, let φ(x) be an arbitrary marker in the nonempty set {z, x, y} ∩ O (see Lemma 7). Obviously φ(x) = x, thus φ(x) ∈ O -D. We show that at most two markers in D -O can have the same image by φ. Suppose that φ(x 1 ) = φ(x 2 ) = φ for two different markers x 1 , x 2 ∈ D -O, where x 1 is deleted before x 2 in Algorithm 3. Then the marker φ is merged into a super-marker after x 1 is deleted, and again merged into a larger super-marker after x 2 is deleted. Since a marker has at most two neighbors in a super-marker, φ is necessarily a single-marker before x 1 is deleted, so it belongs to S, indeed S ∩ O. Moreover, after x 2 is deleted and φ is merged into a larger super-marker, φ cannot be adjacent to any other single-marker, say x 3 . Therefore |D -O| ≤ |O -D| + |S ∩ O|.

(

) 3
Let u be a marker such that γ(u) = 1. Then u belongs to some strip in the optimal solution, and it has a neighbor v = ψ(u) in the same strip such that gap(u, v) contains only one marker, say x. Note that u, v / ∈ O and x ∈ O. We claim that if u is a single-marker at the beginning of the algorithm, then either u ∈ D ∪S or v ∈ D. This claim is clearly true if u or v is deleted by the algorithm in line 5. Otherwise, with (v, x, u) ∈ X or (u, x, v) ∈ X, either x is not deleted because u is merged into a super-marker, or x is deleted: in both cases u ∈ S. This proves the claim. So for each u ∈ R 1 , we have v ∈ D, indeed v ∈ D -O. Note that there can be at most two markers u 1 and u 2 with the same image v by ψ: the two neighbors of v in some strip in the optimal solution. Thus we have |R 1 | ≤ 2|D -O|. Moreover, if there are two markers u 1 and u 2 with the same image v, then γ(v) ≥ 2. Therefore

|R 1 | ≤ v∈D-O γ(v). (4)
Combining inequalities (1), ( 2), (3), and (4), the calculation in the following shows that the number of deleted markers, |D| + |R|, is at most (d + 1.5)k. Thus Algorithm 3 indeed finds a (d + 1.5)-approximation for δ-gap-CMSR-d and CMSR-d.

Theorem 1 .

 1 [6, 1, 8] MSR-d, CMSR-d, δ-gap-MSR-d, and δ-gap-CMSR-d are APX-hard for any d ≥ 2 and δ ≥ 2, even if all markers appear in positive orientation in all genomic maps; 1-gap-MSR-d and 1-gap-CMSR-d are NP-hard for any d ≥ 2. Theorem 2. [7] MSR-d is W[1]-hard for any d ≥ 4, even if all markers appear in positive orientation in all genomic maps.

Theorem 3 .

 3 , we have 6 ≺ 8, and gap(6, 8) = {2, 4, 7}. The following lemma gives some basic properties of the function gap: Lemma 1. (a) Let u, v, w be three markers or single-super-markers. If u and v are two candidate successors of w with u = v, then u ∈ gap(w, v) and v ∈ gap(w, u). (b) Let u and v be two single-super-markers. If u ≺ v or u ≻ v, then gap(u, v) = ∅. 2 An FPT Algorithm for δ-gap-MSR-d In this section, we present the first FPT algorithm for δ-gap-MSR-d with the parameter ℓ. Recall that without the gap constraint, MSR-d with the parameter ℓ is W[1]-hard for any d ≥ 4. In sharp contrast to the W[1]-hardness of MSR-d, we obtain a somewhat surprising result that δ-gap-MSR-d is in FPT, where ℓ is the parameter, and δ and d are constants. In fact, our FPT algorithm for δ-gap-MSR-d works even if d and δ are not constants: δ-gap-MSR-d is in FPT even with three combined parameters d, δ and ℓ. Algorithm 1 finds an optimal solution for δ-gap-MSR-d for any d ≥ 2 and δ ≥ 1, in time O(2 t tdδ 2 + ndδ), where t = ℓ(1 + 3 2 dδ).

Theorem 4 .Algorithm 2

 42 Algorithm 2 finds an exact solution for the decision problems associated with CMSR-d and δ-gap-CMSR-d, for any δ ≥ 1 and d ≥ 2, in time O(c k poly(nd)), where c < 2.360 is the unique real root of the equation 2c -1 + 2c -3 = 1. It is interesting to note that although the two problems MSR-d and δ-gap-MSR-d have very different complexities when parameterized by ℓ, their complements CMSR-d and δ-gap-CMSR-d are both tractable when parameterized by k. FPT algorithm for δ-gap-CMSR-d and CMSR-d Input: d genomic maps G1, . . . , G d each containing n markers without duplicates, and two parameters k ∈ N, δ ∈ N ∪ {∞} 1: return recurse(G1, . . . , G d , k, δ, false) Function recurse(G1, . . . , G d , k, δ, skip step 2b): boolean 1: if k < 0 then 2: return false 3: Partition the markers into single-super-markers. 4: if there exists at least one single-marker in G1 then 5:

4Theorem 5 .

 5 An Approximation Algorithm for CMSR-d and δ-gap-CMSR-d In this section, we present a (d + 1.5)-approximation algorithm for the two minimization problems CMSR-d and δ-gap-CMSR-d. Recall that 2d-approximation algorithms [2, 8, 1] were known for the two maximization problems MSR-d and δ-gap-MSR-d. Algorithm 3 finds a (d + 1.5)-approximation for CMSR-d and δgap-CMSR-d for any d ≥ 2 and δ ≥ 1.

Fig. 2 .

 2 Fig.2. A tight example for the (2d+1)-approximation algorithm. The optimal solution deletes one single-marker x instead of all 2d + 1 single-markers.

  ) + |S -O| + |R 1 | + 2|R 2 | ≥ |S -O| + 2|R 1 | + 2|R 2 | by (4).

2 k. After our initial submission of this paper for publication, we learned from an anonymous reviewer that Jiang et al. [START_REF] Jiang | Exact and approximation algorithms for the complementary maximal strip recovery problem[END_REF] have very recently designed a 3approximation algorithm for CMSR-2 based on a similar greedy approach. Their algorithm does not work for the gap-constrained variant, although it seems that the algorithm might be extended to a (d + 1)-approximation for CMSR-d for all d ≥ 2. Our solution gives uniform results on both variants.

Fig. 3. Upper: an almost-tight example for the (d+1.5)-approximation algorithm showing that its approximation ratio cannot be better than d+1; the optimal solution deletes the two single-markers u and v instead of all 2d + 2 single-markers. Lower: an example showing that no algorithm deleting only single-markers can achieve an approximation ratio better than d; the optimal solution deletes one super-marker u, v instead of 2d single-markers zi and yi,

We refer to Figure 3 for two examples: the first example gives a lower bound of d + 1 on the approximation ratio of Algorithm 3; the second example gives a lower bound of d on the approximation ratio of any algorithm for δ-gap-CMSR-d and CMSR-d that deletes only single-markers. Note that both our Algorithm 3 and the algorithm in [START_REF] Jiang | Exact and approximation algorithms for the complementary maximal strip recovery problem[END_REF] delete only single-markers.

Compared to the approximation upper bound of 2d [START_REF] Chen | On recovering syntenic blocks from comparative maps[END_REF][START_REF] Bulteau | Maximal strip recovery problem with gaps: hardness and approximation algorithms[END_REF][START_REF] Jiang | Inapproximability of maximal strip recovery: II[END_REF] for the two maximization problems MSR-d and δ-gap-MSR-d, which almost matches (at least asymptotically) the current best lower bound of Ω(d/ log d) [START_REF] Jiang | Inapproximability of maximal strip recovery: II[END_REF], our upper bound of d + 1.5 for the two minimization problems CMSR-d and δ-gap-CMSR-d is still far away from the constant lower bound in [START_REF] Jiang | Inapproximability of maximal strip recovery: II[END_REF]. It is an intriguing question whether CMSR-d and δ-gap-CMSR-d admit approximation algorithms with constant ratios independent of d.


Riccardo Dondi
email: riccardo.dondi@unimib.it

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

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

Finding Approximate and Constrained Motifs in Graphs

come

Introduction

The problem of analyzing biological networks such as protein-protein interaction networks and metabolic networks has become increasingly relevant in Computational Biology (see for example [START_REF] Bruckner | Topology-Free Querying of Protein Interaction Networks[END_REF][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]). While the classical approach is based on graph-theoretical topology of the motif, a recent approach introduced in [START_REF] Lacroix | Motif Search in Graphs: Application to Metabolic Networks[END_REF] aims at discovering functional motifs that do not rely on the conservation of the topology, but that are simply connected components of the network. This approach has been formalized as a graph problem (named Graph Motif), in which given a vertex-colored graph G = (V, E) and a multiset M of colors, the goal is to find a subset V ′ ⊆ V which is connected and whose vertex set is colored exactly as M.

The Graph Motif problem has been widely studied, and some variants have been introduced. The original problem is known to be NP-complete [START_REF] Lacroix | Motif Search in Graphs: Application to Metabolic Networks[END_REF], even if the input graph is a tree with maximum degree 3 and the motif is a set [START_REF] Fellows | Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs[END_REF], and if the input graph is a bipartite graph with maximum degree 4 and the motif is built over two colors only [START_REF] Fellows | Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs[END_REF]. It is easy to see that Graph Motif admits a polynomial time algorithm when the input graph is a tree and each color occurs at most twice in the input tree. The Graph Motif problem is known to be in FPT, when parameterized by the size of the motif [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] Guillemot | Finding and Counting Vertex-Colored Subtrees[END_REF], while it is W [START_REF] Ambalath | On the Kernelization Complexity of Colorful Motifs[END_REF]-hard when parameterized by the number of distinct colors in the motif, even in the case the input graph is a tree [START_REF] Fellows | Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs[END_REF]. Recently, the kernelization complexity of the problem has also been considered [START_REF] Ambalath | On the Kernelization Complexity of Colorful Motifs[END_REF].

Different variants of the Graph Motif problem have been introduced. Such variants either modify the requirement of connectedness [START_REF] Dondi | Weak Pattern Matching in Colored Graphs: Minimizing the Number of Connected Components[END_REF], or look for approximate occurrences of the motif, where some colors are allowed to be inserted or deleted in an occurrence of the motif [START_REF] Bruckner | Topology-Free Querying of Protein Interaction Networks[END_REF][START_REF] Dondi | Maximum Motif in Vertex-Colored Graphs[END_REF][START_REF] Guillemot | Finding and Counting Vertex-Colored Subtrees[END_REF]. Following this direction, we consider three variants of the Graph Motif problem. In the first two variants, we relax the constraint that each color of M must appear in an occurrence of the motif, and we allow for the adding (Min-Add) or the substitution (Min-Substitute) of some colors. These two problems are motivated by the fact that, due to experimental errors, there may not exist an exact occurrence of the motif M in the graph G. In the third variant, Constrained Graph Motif (or CGM, for short), we strengthen the requirement of connectedness, constraining some vertices of the input graph to be part of an occurrence of a motif M. This is motivated by the fact that, due to a previous knowledge on the structure of the network, we may require some of the vertices to be contained in any occurrence of M.

The rest of the paper is organized as follows. In Section 2, we give some preliminary definitions and we formally define the problems. In Section 3, we show that Min-Substitute and Min-Add are NP-hard, even when M is a set, the input graph is a tree T of degree bounded by 4 and each color has at most two occurrences in T . Notice that under the same hypotheses, the Graph Motif problem admits a polynomial time algorithm. In Section 4, we give an FPT algorithm for Min-Substitute. In Section 5, we discuss the parameterized complexity of the CGM problem, when the parameter is the number of colors not belonging to mandatory vertices ; in Section 5.1, we show that CGM is fixed-parameter tractable for graphs of bounded treewidth, while in Section 5.2 we show that CGM is W [2]-hard, even if the diameter of the input graph is bounded by 2. Some of the proofs are omitted due to space constraints.

Preliminaries

In this section, we recall basic notations used in the rest of the paper. Given a graph G = (V, E) and

V ′ ⊆ V , we denote by G[V ′ ] the subgraph of G induced by V ′ , that is G[V ′ ] = (V ′ , E ′ ) and {u, v} ∈ E ′ iff u, v ∈ V ′ and {u, v} ∈ E.
Given a vertex v ∈ V , we denote by N (v) the set of vertices in G adjacent to v. We recall that a graph is cubic when each vertex has degree 3.

Let G be a connected graph, where every vertex u ∈ V (G) is assigned a color c(u) from a set C of colors. For any subset V ′ of V , let C(V ′ ) be the multiset of colors assigned to the vertices in V ′ . Let M be a multiset of colors, whose colors are taken from the set C. Given a colored graph G and a subset of vertices

V ′ ⊆ V (G), C(V ′ ) is said to match a multiset of colors M if C(V ′ ) is equal to M.
In this case, by abuse of notation, we say that V ′ matches M. Given a subset of vertices

V ′ ⊆ V (G) such that V ′ matches M and G[V ′ ] is connected, then V ′ is called an occurrence of M in G. A motif M is said colorful when M is a set of colors (rather than a multiset).
In this paper, we consider three variants of the Graph Motif problem. For two of them, Min-Add and Min-Substitute, we look for a vertex set

V ′ of G = (V, E), such that G[V ′ ] is connected and C(V ′
) is not necessarily equal to M. Furthermore, we consider a constrained variant of the Graph Motif problem, CGM, where the input consists of a vertex colored graph and a set of mandatory vertices that must belong to any occurrence of motif M.

Let us introduce the first two variants of Graph Motif problem.

Min-Add (decision version)

Input : A multiset of colors M, a vertex-colored graph G = (V, E), an integer p. Question : Is there a subset

V ′ ⊆ V , such that G[V ′ ] is connected, C(V ′ ) ⊇ M and |C(V ′ ) \ M| ≤ p ?

Min-Substitute (decision version)

Input : A multiset of colors M, a vertex-colored graph G = (V, E), an integer p.

Question : Is there a subset V ′ ⊆ V , such that G[V ′ ] is connected and C(V ′ ) can be obtained with at most p substitutions from M?

Notice that, in case p = 0, both Min-Add and Min-Substitute are equivalent to the Graph Motif problem. As a consequence, Min-Add and Min-Substitute are both NP-hard when the motif is colorful, the input graph consists of a tree T and each color has at most 3 occurrences in T [START_REF] Fellows | Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs[END_REF]. Furthermore, Min-Add (resp. Min-Substitute) cannot be approximated within any approximation factor, and does not admit any fixed-parameter tractable algorithm, when the parameter is the number of added colors (resp. the number of substitutions). Notice that Min-Add is in FPT, when parameterized by |M|. Indeed, in [START_REF] Guillemot | Finding and Counting Vertex-Colored Subtrees[END_REF], a variant of Graph Motif, called Multiset Graph Motif With Gaps (MGMG), is considered: given an input graph G and a motif M, we look for an occurrence of M that is allowed to contain gaps. Note that this is precisely Min-Add, where the gaps represent colors to be added to M. As in [START_REF] Guillemot | Finding and Counting Vertex-Colored Subtrees[END_REF] it is shown that MGMG is in FPT when parameterized by |M|, we can conclude that the Min-Add problem is in FPT. Furthermore, in case the motif is colorful, a fixed-parameter algorithm for Min-Add has been given in [START_REF] Bruckner | Topology-Free Querying of Protein Interaction Networks[END_REF].

Let us now consider a different variant of the Graph Motif problem, called Constrained Graph Motif (CGM).

Constrained Graph Motif (CGM)

Input : A multiset of colors M, a vertex-colored graph G = (V, E), a set of mandatory vertices V M ⊆ V . Question : Is there a subset V ′ ⊆ V , such that G[V ′ ] is connected, C(V ′ ) = M and V M ⊆ V ′ ?
Given an instance of CGM, define the optional occurrences

C o as C o = M \ C(V M ).
The CGM problem is NP-complete, since the Graph Motif problem is NP-complete [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]. It is easy to see that CGM is fixed-parameter tractable, when the parameter is the size of the motif. Indeed, recall that Graph Motif is fixed-parameter tractable. By recoloring the graph, assigning a unique color to each vertex in V M , and by modifying accordingly M, we can conclude that each occurrence of M in G must include all the vertices in V M .

In Section 5, we investigate the parameterized complexity of the CGM problem, when the parameter is the number of optional occurrences. Notice that the Minimum (Unweighted) Steiner Tree problem is a restriction of the CGM problem, where the non mandatory vertices in the Steiner Tree problem correspond to optional occurrences in CGM. As the Minimum (Unweighted) Steiner Tree problem is W [START_REF] Alimonti | Some APX-Completeness Results for Cubic Graphs[END_REF]-hard when parameterized by the number of non mandatory vertices [START_REF] Cesati | Compendium of parameterized problems[END_REF], it follows that the CGM problem is W [START_REF] Alimonti | Some APX-Completeness Results for Cubic Graphs[END_REF]-hard when parameterized by the number of optional occurrences.

In Section 5.1, we will consider the case where the input graph has bounded treewidth and we will use a tree decomposition of the graph. Let us recall the definition of tree decomposition of a graph [START_REF] Downey | Parameterized Complexity[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]. Given a graph G = (V, E), a tree decomposition of G is a pair {X i : i ∈ I}, T , such that each X i is called a bag, and T is a tree having as vertices the elements of I and such that:

1. ∪ i∈I X i = V ; 2. for each edge {u, v} ∈ E, there is a bag X i with u, v ∈ X i ; 3. for each i, j, k in V , if j is on the path from i to k in G, then X i ∩ X k ⊆ X j .
The width of {X i : i ∈ I}, T is equal to max{|X i | : i ∈ I} -1 and the treewidth of a graph G is equal to the minimum δ such that G has a tree decomposition of width δ. A tree decomposition {X i , i ∈ {1, . . . , p}}, T of a graph G is nice (see [START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]) when, given a vertex i of the tree decomposition, i has at most two children and the following conditions hold:

1. if i has two children j and k, then X i = X j = X k ; 2. if i has exactly one child j, then one of the following conditions holds:

(a

) |X i | = |X j | + 1, and then X j ⊂ X i ; or (b) |X i | = |X j | -1, and then X j ⊃ X i .
In the rest of the paper, in order to extend some results from the case when M is colorful to the general case, we use the recoloring technique introduced in [START_REF] Betzler | Parameterized Algorithms and Hardness Results for Some Graph Motif Problems[END_REF], based on the color-coding technique [START_REF] Alon | Color Coding[END_REF]. The recoloring technique starts from a general motif M and computes a colorful motif C, recoloring accordingly the vertices of the input graph G. Let V ′ be an occurrence of M in the graph G, then V ′ achieves a colorful recoloring if C(V ′ ) is colorful after the recoloring of M and G. In [START_REF] Betzler | Parameterized Algorithms and Hardness Results for Some Graph Motif Problems[END_REF], the following result was shown:

Lemma 1 (Betzler et al. [START_REF] Betzler | Parameterized Algorithms and Hardness Results for Some Graph Motif Problems[END_REF]). Given a motif M, the number of trials to achieve a colorful recoloring of M with an error probability of

ε is | ln(ε)| • O(e |M| ).

NP-hardness of Min-Substitute and Min-Add

In this section, we show that Min-Substitute and Min-Add are NP-hard, even if the input graph is a tree, the motif is colorful and each color has at most two occurrences in the input tree. Recall that, under the same hypotheses, the Graph Motif problem admits a polynomial time algorithm.

Theorem 1. The Min-Substitute problem is NP-hard, even when the input graph is a tree of maximum degree 4, each color occurs at most twice in the input graph and the motif is colorful.

Proof. We give a reduction from the Minimum Vertex-Cover on Cubic Graphs problem (Min-VCC). Let G = (V, E) be a cubic graph with V = {v 1 , v 2 , . . . , v n }, the Min-VCC problem asks for a subset V ′ ⊆ V of size at most p, such that for each {v i , v j } ∈ E at least one of v i , v j is in V ′ . Min-VCC is known to be NP-hard [START_REF] Alimonti | Some APX-Completeness Results for Cubic Graphs[END_REF]. Starting from G, we construct an instance of the Min-Substitute problem which consists of a tree T and a set of colors M. For any vertex v i ∈ V , let e i,j , 1 ≤ j ≤ 3, be its 3 incident edges, ordered arbitrarily. The tree T = (V T , E T ) is defined as follows (see Figure 1):

-V T = {l i , a i,1 , a i,2 : 1 ≤ i ≤ n} ∪ {s i : 1 ≤ i ≤ p} ∪ {t i : 1 ≤ i ≤ n + 1} ∪ {e i,j : 1 ≤ i ≤ n ∧ 1 ≤ j ≤ 3}; -E T = {{l i , l i+1 } : 1 ≤ i < n} ∪ {{s i , s i+1 } : 1 ≤ i < p} ∪ {{t i , t i+1 } : 1 ≤ i < n + 1} ∪ {{l n , t 1 }} ∪ {{t n+1 , s 1 }} ∪ {{l i , a i,1 }, {a i,1 , a i,2 } : 1 ≤ i ≤ n} ∪ {{a i,2 , e i,j } : 1 ≤ i ≤ n ∧ 1 ≤ j ≤ 3}.
Clearly, this construction gives us a tree of maximum degree 4. Let us describe the colors assigned to each vertex of V (G). Each vertex l i , 1 ≤ i ≤ n, is assigned a unique color c(l i ), each vertex s i , 1 ≤ i ≤ p, is assigned a unique color c(s i ), and each each vertex t i , 1 ≤ i ≤ n + 1, is assigned a unique color c(t i ). The two vertices a i,1 , a i,2 , 1 ≤ i ≤ n, are assigned the same color c(v i ). Finally, each vertex e i,x in V T , 1 ≤ i ≤ n and 1 ≤ x ≤ 3, associated to an edge e i,j = {v i , v j } in E, is assigned color c(e i,j ). Each color occurs at most twice in T , as each color c(e i,j ) is associated to two vertices of T , while each color c(v i ) is associated to vertices a i,1 , a i,2 . M is a set of colors defined as follows:

M = {c(l i ) : 1 ≤ i ≤ n} ∪ {c(s i ) : 1 ≤ i ≤ p} ∪ {c(v i ) : 1 ≤ i ≤ n} ∪ {c(e i,j
) : e i,j ∈ E}. Notice that no occurrence of a color c(t i ), 1

≤ i ≤ n + 1, belongs to M.
Starting from a vertex cover V ′ ⊆ V of G of size at most p, a solution V T ′ of Min-Substitute, that substitutes p colors from M, is obtained as follows. Given an edge e i,j = {v i , v j }, define e min i,j = min{i, j}. The vertex set V T ′ defined as follows:

V T ′ = {l i , a i,1 : 1 ≤ i ≤ n} ∪ {t i : 1 ≤ i ≤ p -|V ′ |} ∪ {a i,2 : v i ∈ V ′ } ∪ {e i,x : c(e i,x ) = c(e i,j ) ∧ i = e min
i,j }. By construction and since V ′ is a vertex cover, V T ′ induces a subtree of T . It is easy to see that, given C(V T ′ ) = M ′ , M ′ can be obtained from M by p substitutions.

Let us consider now a solution V T ′ of Min-Substitute, where C(V T ′ ) = M ′ , |M ′ | = |M|, and M ′ can be obtained from M with at most p substitutions. First, we show that V T ′ does not contain a vertex of the set {s i : 1 ≤ i ≤ p}. Indeed, assume that a vertex s i is part of V T ′ ; by construction the set of vertices {t j : 1 ≤ j ≤ n + 1} must belong to V T ′ , and since M does not contain occurrences of any color c(t j ), 1 ≤ j ≤ n + 1, it follows that M ′ requires at least n + 1 substitutions. Notice that n + 1 > p, as each vertex cover V ′ of G has size at most n. Hence, we can assume that V T ′ does not contain any vertex in the set {s i : 1 ≤ i ≤ p}. It follows that all the colors c(s i ), 1 ≤ i ≤ p, in M must be substituted, and, since by hypothesis M ′ can be obtained from M with at most p substitutions, it follows that only the colors c(s i ), 1 ≤ i ≤ p, are substituted. Hence {l i , a i,1 : 1 ≤ i ≤ n} ⊆ V T ′ and M ′ ⊇ {c(e i,j ) : e i,j ∈ E}. Since T [V T ′ ] must be connected, it follows that each vertex colored c(e i,j ) must be connected to some vertex

a i,2 ∈ V T ′ colored by c(v i ). Define V ′ = {v i : a i,2 ∈ V T ′ } ; then V ′ is
a cover of G of size at most p, which completes the proof.

⊓ ⊔ Theorem 2. The Min-Add problem is NP-hard, even when the input graph is a tree of maximum degree 4, each color occurs at most twice in the input graph and the motif is colorful.

Proof. (Sketch) The result follows from a reduction from Min-VCC similar to that of Theorem 1. Given an instance of Min-VCC, an instance (T, M) of Min-Add is constructed as follows. T = (V T , E T ) is defined as follows (see Fig. 2): Each vertex l i , 1 ≤ i ≤ n, is assigned a unique color c(l i ), 1 ≤ i ≤ n. The two vertices a i,1 , a i,2 , 1 ≤ i ≤ n, are assigned the same color c(v i ). Finally, each vertex e i,x in V T , 1 ≤ i ≤ n and 1 ≤ x ≤ 3, associated to an edge e i,j = {v i , v j } in E, is assigned color c(e i,j ). M is a set of colors defined as follows: M = {c(l i ) : 1 ≤ i ≤ n} ∪ {c(v i ) : 1 ≤ i ≤ n} ∪ {c(e i,j ) : e i,j ∈ E}.

-V T = {l i , a i,1 , a i,2 : 1 ≤ i ≤ n} ∪ {e i,j : 1 ≤ i ≤ n ∧ 1 ≤ j ≤ 3}; -E T = {{l i , l i+1 } : 1 ≤ i < n} ∪ {{l i , a i,1 }, {a i,1 , a i,2 } : 1 ≤ i ≤ n} ∪ {{a i,2 , e i,j } : 1 ≤ i ≤ n ∧ 1 ≤ j ≤ 3}.
It can be proved that starting from a vertex cover

V ′ ⊆ V of G, we can compute in polynomial time a solution V T ′ of Min-Add such that C(V T ′ ) ⊇ M and |C(V T ′ )| ≤ |M| + |V ′ |. Conversely, starting from a solution V T ′ of Min-Add such that C(V T ′ ) ⊇ M and |C(V T ′ )| ≤ |M| + p, we can compute a vertex cover V ′ of G such that |V ′ | ≤ p. ⊓ ⊔

Parameterized Complexity of Min-Substitute

In this section, we discuss the parameterized complexity of Min-Substitute, when parameterized by |M|. We recall that Min-Substitute is not in FPT, as discussed in Section 2, when parameterized by the the size of the solution (i.e., the number of substituted colors). Let us first consider the case where the motif M is colorful (i.e., M is a set). The algorithm is based on dynamic programming. Let (G = (V, E), M) be an instance of Min-Substitute. Instead of computing directly a solution for Min-Substitute, we compute a solution for a slightly different problem, where we visit the vertices of a connected component of G, allowing to visit some vertices more than once. Let v be a vertex of the input graph G, let C ⊆ M be a subset of colors, let k be the number of vertices of the solution of Min-Substitute we are looking for, and define S[v, C, k] as the minimum value z required by a visit of a connected set V T of vertices of G such that:

1. v ∈ V T ; 2. exactly k visits of vertices in V T are done; 3. C(V T ) matches q colors of C, where z = kq.

Notice that a vertex of V T may be visited more than once, while the overall number of visits must be k. Now, let us define the dynamic programming recurrence to compute

S[v, C, k]. S[v, C, k] = min C ′ ⊆C,u∈N (v),k1+k2=k S[v, C ′ , k 1 ] + S[u, C \ C ′ , k 2 ] . (1)
For the base cases: S[u, C ′ , 1] = 0, when c(u) ∈ C ′ , for each C ′ ⊆ C and u ∈ V , and S[u, C ′ , 1] = 1 when c(u) / ∈ C ′ . Now, let us prove the correctness of Recurrence (1). Lemma 2. Let (G, M) be an instance of Min-Substitute, let v be a vertex of G, and let C be a subset of M. There is a visit of a connected vertex set V T of G, such that v ∈ V T , the vertices of V T are visited k times, and C(V T ) matches q colors of C, iff there exists an entry S[v, C, k] = z, where z = kq.

An optimal solution for the Min-Substitute problem can be found as follows. We look for the minimal value z in the entries S[v, M, |M|], with v ∈ V . Notice that this value may be associated to a visit of a connected vertex set V T , where some of the vertices may be visited repeatedly. Each repeated visit of a vertex represents a color to be substituted, since M is colorful. It follows that we can compute a feasible solution for Min-Substitute by replacing these repeated visits by some connected components adjacent to V T without increasing the number of substitutions.

The time complexity of the algorithm is O * (3 |M| ), as we have to consider all possible subsets C ⊆ M and for each subset C we have to consider all possibile bipartitions of C. Indeed, there are O(3 |M| ) possible bipartitions of all possible subsets C of M. In order to extend the results to a multiset, we apply the recoloring technique described in [START_REF] Betzler | Parameterized Algorithms and Hardness Results for Some Graph Motif Problems[END_REF]. Combining Lemma 2 with Lemma 1, and we get that Min-Substitute, parameterized by |M|, can be solved in time O * ((3e) O(|M| )).

Parameterized Complexity of CGM

In this section, we consider the parameterized complexity of CGM, where the parameter is the number

k of optional occurrences C o , that is k = |C o |, where C o = M \ C(V M ).
First, in Section 5.1, we show that CGM is fixed-parameter tractable, when the input graph is of bounded treewidth ; then, in Section 5.2, we prove that CGM is W [START_REF] Alimonti | Some APX-Completeness Results for Cubic Graphs[END_REF]-hard, even when the input graph is of diameter 2.

An FPT Algorithm for Graphs of Bounded Treewidth

Here, we describe a fixed-parameter algorithm for CGM for graphs of bounded treewidth. Let (G = (V, E), M, V M ) be an instance of CGM, and let us first consider the case where the motif M is colorful.

Denote by k the number of optional occurrences and by δ the treewidth of graph G. The algorithm is based on a nice tree decomposition of G (see Section 2 for the definition of nice tree decomposition of a graph). We also consider a slightly more general problem, where instead of requiring that an occurrence of a motif consists of a single connected component, we may have an occurrence consisting of at most δ + 1 connected components, where the different connected components are induced by a partition of a bag X i of the nice tree decomposition. Given a vertex i of the tree decomposition of G, denote by T [i] the subtree of the nice tree decomposition rooted at i and let

V (T [i]) = {u ∈ X j : j ∈ T [i]}.
Now, consider a set X i , 1 ≤ i ≤ p, of the nice tree decomposition {X i , i ∈ {1, . . . , p}}, T . From the definition of treewidth, it follows that |X i | ≤ δ + 1. Now, let us define a mapping function f i associated to the vertices of X i , as follows.

Definition 1. Let X i be a bag of the nice tree decomposition of G. A mapping function f i from X i to {0, 1, . . . , δ + 1} is feasible when

1. f i (v) = 0 for each mandatory vertex v in X i ; 2. for each pair of vertices u, v ∈ X i such that c(u) = c(v), then f i (u) = 0 or f i (v) = 0; 3. define X l i = {v ∈ X i : f (v i ) = l}, l ∈ {1, . . . , δ + 1}, and
X ′ i = ∪ l X l i , then X l i is a maximal connected component of G[X ′ i ].
A feasible mapping f i represents a partition of a subset X ′ i ⊆ X i in at most δ + 1 connected components, where f i (v) = p = 0 implies that v belongs to the p-th connected component, while f i (v) = 0 implies that v does not belong to X ′ i . Definition 2. Let W be a set of vertices of V (T [i]), consisting of the connected components W 1 , W 2 , . . . , W z . Let f i be a feasible mapping of X i in {0, 1, . . . δ+1}, then W is mapped (or partitioned) according to f i if:

1. for each p, 1 ≤ p ≤ z, W p ∩ X i = ∅, and there exists exactly one l,

1 ≤ l ≤ δ + 1, such that W p ∩ X i = X l i 2. for each l, 1 ≤ l ≤ δ + 1, such that X l i = ∅, there exists exactly one p, 1 ≤ p ≤ z, such that X l i = W p ∩ X i .
Notice that by Definition 2, if a vertex u of W is not in X i , then there exists a vertex v in W ∩ X i such that v and u are in the same connected component W x of W , v is assigned some label l = 0, and all the vertices of W x ∩ X i are assigned the same label l.

Given two sets X i and X j of a nice tree decomposition, and two feasible mappings f i : X i → {0, . . . , δ + 1} and f j : X j → {0, . . . , δ + 1}, then f i and

f j are consistent if, for each v ∈ X i ∩ X j , f i (v) = f j (v).
Let i be a vertex of the nice tree decomposition, with exactly one child j, such that |X i | = |X j | + 1 and X j ⊂ X i , with v ∈ X i \ X j . Then, a feasible mapping f i is an extension of a feasible mapping f j , when either:

1. f i (v) = 0; or 2. f i (v) = l, l ∈ {1, . . . , δ + 1}, f i (u) = l for each u ∈ X i ∩ X j , and f i , f j are consistent; or 3. there exists a value l ∈ {1, . . . , δ + 1} such that (a)

f i (v) = l; (b) if f j (z) = 0, then f i (z) = 0, for z ∈ X i ∩ X j ; (c) if f i (z) = f j (z), for z ∈ X i and f j (z) = 0, then f i (z) = l.
Given a feasible mapping

f i of X i in {0, 1, . . . δ + 1}, define c(X i , f i ) = {c ∈ C o : ∃v ∈ X i , c(v) = c ∧ f i (v) = 0}.
Let us define the value S[i, f i , C ′ ], where i is a vertex of the nice tree decomposition of G, f i is a feasible mapping function of the set X i in {0, 1, . . . δ + 1} and C ′ ⊆ C o be a subset of the set of optional occurrences. S[i, f i , C ′ ] = 1 when there exists a set W of vertices in the nice tree decomposition rooted at i, such that the vertices of W can be partitioned according to f i , each mandatory vertex of T [i] is in W , and the set of optional occurrences of c(W ) is C ′ ; else S[i, f i , C ′ ] = 0. Next, we describe how to compute S[i, f i , C ′ ] by dynamic programming, depending on the three different cases of a nice tree decomposition.

Case 1) Assume that vertex i has two children j and k (recall that X i = X j = X k ), then

S[i, f i , C ′ ] = fj ,f k ,Cj ,C k S[j, f j , C j ] ∧ S[k, f k , C k ],
where f i , f j , f k are all feasible and consistent,

C ′ = (C j ∪ C k ) and c(X i , f i ) = C j ∩ C k .
Case 2) Assume that i has exactly one child j, such that X i = X j ∪ {v}, then

S[i, f i , C ′ ] = fj ,Cj S[j, f j , C j ],
where f i and f j are feasible, f i is an extension of f j , C ′ = C j ∪ {c(v)} and c(v) / ∈ C j , when f i (v) = 0 and v / ∈ V M , and

C ′ = C j when f i (v) = 0 or v ∈ V M .
Case 3) Assume that X i has exactly one child X j , such that

X i = X j \ {v}, then S[i, f i , C ′ ] = fj S[j, f j , C ′ ],
where f i and f j are feasible and consistent, and there is a vertex z ∈ X i ∩X j , such that f j (z) = f j (v), with v ∈ X j \ X i , when f j (v) = 0.

For the base cases (when X i is a leaf of the nice tree decomposition), define S[i, f i , C ′ ] = 1 when there is a partition of the vertices of X i according to the feasible function f i , and c(X i , f

i ) = C ′ ; else S[i, f i , C ′ ] = 0.
First, we prove the correctness of the above recurrences, then we discuss the time complexity of the algorithm. Lemma 3. Let f i be a feasible mapping function of X i , and let W be a set of vertices in V (T [i]), such that W contains all the mandatory vertices in V (T [i]), W can be mapped according to f i and C ′ is the set of optional occurrences in c(W ). Then S[i, f i , C ′ ] = 1. Lemma 4. Let S[i, f i , C ′ ] = 1 for a feasible mapping function f i of X i in {0, 1, . . . , δ + 1}, then there exists a set W of vertices in V (T [i]) such that the set of optional occurrences in c(W ) is C ′ , W contains all the mandatory vertices in V (T [i]) and the vertices of W can be mapped according to f i .

Theorem 3 shows how the values S[i, f i , C ′ ] are used to compute the existence of a feasible solution for CGM. Theorem 3. Let (G = (V, E), M, V M ) be an instance of the CGM problem. Then there is a solution W of CGM over instance of (G, M, V M ) iff there is a vertex i of the nice tree decomposition and a feasible function

f i that maps X i in {0, x}, with x ∈ {1, . . . , δ + 1}, such that S[i, f i , C o ] = 1 and such V M ⊆ V (T [i]).
Proof. Assume that there is a vertex i of the nice tree decomposition and a feasible function f i that maps X i in {0, x}, with x ∈ {1, . . . , δ + 1}, such that S[i, f i , C o ] = 1 and all the mandatory vertices of G are in T [i]. By Lemma 4, it follows that there is a set of vertices W in V (T [i]) that contains all the mandatory vertices of G, such that the set of optional occurrences in c(W ) is C o and such that the vertices of W can be mapped according to f i . Furthermore, notice that W consists of a single connected component. Hence W is a solution of CGM.

Consider the case where there is a solution W of CGM over instance (G = (V, E), M, V M ). Consider a vertex i of the tree decomposition of G such that all the vertices of W are contained in V (T [i]). By Lemma 3, it follows that S[i, f i , C o ] = 1 for some feasible function f i that maps X i in {0, x}, with x ∈ {1, . . . , δ + 1}.

⊓ ⊔ Now, we discuss the time complexity of the above algorithm. Denote by n the size of V . Given a vertex i and the associated set X i of the nice tree decomposition, the number of possible mapping functions of X i into {0, . . . , δ+1} is O(δ δ ). The number of possible subsets C ′ is O(2 k ). Since the number of vertices of a nice tree decomposition is O(n), it follows that we have O(δ δ n2 k ) entries S[i, f i , C]. Given a mapping function f i of X i into {0, . . . , δ + 1}, computing an entry S[i, f i , C], given the entries of the children (or the child) of i, requires time at most O(δ 2δ 2 2k ) (notice that the worst case occurs when i has two children). Hence the total time complexity is O(δ 3δ n2 3k ).

When a motif is a multiset of colors, we apply the recoloring technique presented in Lemma 1. As a consequence, CGM can be solved with error probability ε in time O(| ln(ε)|δ 3δ n2 4.4427k ), for graphs of treewidth δ.

Hardness of Parameterization

The CGM problem parameterized by the number of optional occurrences is W [2]-hard, as stated in Section 2. Here we strengthen the result, showing that the problem is W [2]-hard even when the input graph is of diameter 2. an instance of Min-SC, we define a corresponding instance (G = (V, E), M, V M ) of the CGM problem (see Fig. 3). The graph G of diameter 2 is defined as follows:

-V = {r} ∪ {r ′ } ∪ {v S,i : 1 ≤ i ≤ m} ∪ {v u,j : 1 ≤ j ≤ n};

-E = {{r, r ′ }} ∪ {{r, v S,i } : 1 ≤ i ≤ m} ∪ {{r ′ , v S,i } : 1 ≤ i ≤ m} ∪ {{v S,i , v u,j } : 1 ≤ i ≤ m ∧ u j ∈ S i } ∪ {{r ′ , v u,j } : 1 ≤ j ≤ n}.

Vertex r and vertex r ′ are both colored by c(r), vertex v S,i is colored by c(S), 1 ≤ i ≤ m, and vertex v u,j is colored by c(u j ), 1 ≤ j ≤ n. The motif M is a multiset containing one occurrence of color c(r), one occurrence of each color c(u j ), 1 ≤ j ≤ n, and k occurrences of color c(S). Finally, V M = V \ ({v S,i : 1 ≤ i ≤ m} ∪ {r ′ }).

Then, it is possible to show that, given a solution of Min-SC of size at most k, we can compute in polynomial time a solution of CGM over instance (G = (V, E), M, V M ). Similarly, it is possible to show that given an occurrence V T of motif M in G, we can compute in polynomial time a solution of Min-SC of size at most k. By construction, a solution of CGM over instance (G = (V, E), M, V M ) contains exactly k optional occurrences. Hence the reduction is parameter preserving, thus implying that CGM is W [2]-hard.

⊓ ⊔

Fig. 1 .

 1 Fig. 1. Illustration of the reduction from Min-VCC to Min-Substitute.

3 Fig. 2 .

 32 Fig. 2. Illustration of the reduction from Min-VCC to Min-Add.

Theorem 4 .Fig. 3 .

 43 Fig. 3. Illustration of the reduction from Min-SC to CGM ; notice that element uj ∈ Si.


Karen Ferret

Elena Soare
email: elena.soare@univ-paris8.fr

Florence Villoing
email: florence.villoing@univ-paris8.fr

Rivalry between French -age and -ée: the role of grammatical aspect in nominalization *

Keywords: nominalizations, event and argument structure, grammatical aspect

This paper will provide an account for the existence of pairs of deverbal nominals with -age and -ée giving rise to event readings. We first study the argument structure of the bases and of the derived nominals, and establish the general tendencies. We further examine the Aktionsart of the nominalizations and of the verbal bases. We conclude that these levels of investigation are not sufficient to determine the proper contribution of the two nominalization patterns and further demonstrate that the relevant contribution they make is at the level of grammatical aspect. We therefore propose that -age introduces the imperfective viewpoint, whereas -ée introduces the perfective viewpoint.

Introduction

In this paper, we will study French deverbal nouns with -age and -ée which are derived from the same verbal base-a case of nominalization rivalry ignored in the literature. Based on a corpus of event nominal pairs derived from 29 verbal bases (which we selected from the TLFi dictionary and completed with web occurrences), we will provide an account of the existence of such pairs in the language. Two questions immediately arise in light of such cases:

-Is there any linguistic reason for the existence of these pairs? -Do these nominalizations have a distinctive contribution? Looking at the interplay between event structure, Aktionsart and grammatical aspect, we will try to sketch an answer to these general questions, and propose that the nominalizations under consideration contribute different grammatical aspect values.

2 Argument structure of the verbal bases

All verbal bases selected

We begin by examining two existing hypotheses: (a) the suffix -age selects transitive verbal bases [START_REF] Dubois | La dérivation suffixale en français[END_REF]), and (b) only unaccusative verbs allow -ée nominalization [START_REF] Ruwet | Les verbes météorologiques et l'hypothèse inaccusative[END_REF]). Examination of the argument structure type of the bases leads us to conclude that there is no clear specialization of the two nominalizations: both can combine with transitive, unaccusative and unergative bases (cf. Legendre (1989) for unaccusativity tests in French). However, some trends and regularities are visible. The transitive base is the primary type selected by both processes that construct N-age and N-ée pairs: [START_REF] Alexiadou | Nominal/Verbal Parallelisms and Number/Aspect Interactions in the Syntax of Nominalizations[END_REF] couler du bronze'to cast bronze', couler une cloche, 'to cast a bell' le coulage / la coulée du bronze/ d'une cloche 'the casting of bronze/a bell' However, nominalizations with both -age and -ée also select unergative bases (2) and unaccusatives (3).

(2)

CHEVAUCHER 'aller à cheval' 'to ride' la chevauchée hebdomadaire 'the weekly ride' / le chevauchage sous un soleil éclatant 'the riding under a blazing sun' [START_REF] Dubois | La dérivation suffixale en français[END_REF] ARRIVER 'to arrive' l'arrivage / l'arrivée de la marchandise, des ouvriers '"the arriving"/ the arrival of the merchandise, of the workers'

General preferences

When selected by only one of the two nominalizations, there is a general preference for certain bases: -age shows a tendency to select transitive bases (4) while unaccusatives are selected by -ée [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF]. [START_REF] Kelling | French Psych Verbs and Derived Nouns[END_REF] tourner le film 'to shoot the film' le tournage du film / *la tournée du film 'the shooting of the film' [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] le fascisme monte en Europe 'fascism grows in Europe' la montée du fascisme/*le montage du fascisme 'the growth of fascism'

On the one hand, the data confirm the arguments of [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] (that nominalization with -age is not limited to transitive bases) and of Legendre (1989) (that -ée nouns are not a valid test for unaccusativity). On the other hand, this result determines the argument structure of the verbal bases selected by the two affixes.

Proposal: highlighting of causation

Transitive bases

Nominalization with -age highlights the proto-agent property (cf. Dowty (1991)) of the external argument of the verb (cf. Kelling (2001) and [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] for an earlier analysis). Our analysis is supported by the different meanings associated with N-age and N-ée derived from the same transitive verb base (6a) and by neologisms (6b). Nominalization with -age underlines the causative sense while with -ée it highlights the resultative sense. [START_REF] Haas | Du verbe au nom: calques et décalcages aspectuels[END_REF] a. Le montage des briques / la montée des briques 'the lifting of bricks' (cause/result) b. @...avec Sarko, on est entré dans l'ère de l'effrayage ! with Sarko, we entered the age of scaring (built on EFFRAYER 'scare' transitive-causative : x CAUSE y is scared)

Unaccusative bases

(i) Nominalization with -age seems to introduce a semantic participant into the event structure of the base verb which has the proto-agent property external causation. For deverbal nouns built from some unaccusative bases, such as ARRIVAGE 'arrival', POUSSAGE 'growth', nominalization with -age seems to introduce causation which allows a verbal paraphrase with faire 'make'. [START_REF] Grimshaw | Argument Structure[END_REF] a. l'arrivage des légumes 'the "arriving" = arrival of the vegetables' = 'faire arriver les légumes' 'make the vegetables arrive' b. le poussage des poils sur le torse 'the growth of hair on the chest' = 'faire pousser les poils à l'aide d'une lotion' 'make the hair grow using a lotion' c. le levage de la pâte = 'faire lever la pâte' 'the rising of the dough' = 'make the dough rise' This is also true for other deverbal nouns with-age that have no morphological counterpart with -ée, like ATTERRISSAGE, which is derived from an unaccusative verb that has no transitive counterpart in French (unlike in English and German). [START_REF] Heyd | Quelques remarques à propos des noms d'activité[END_REF] a. l'avion a atterri 'the plane landed' b. *le pilote a atterri l'avion 'the pilot landed the plane' c. l'atterrissage de l'avion 'the landing of the plane'

(ii) Exceptions

But this pattern is not systematic. An -age nominal is ungrammatical when the unaccusative V selects an internal argument that cannot be affected by (agentive or instrumental) causation. [START_REF] Ruwet | Les verbes météorologiques et l'hypothèse inaccusative[END_REF] a. la coulée / *le coulage de neige/ de lave 'the flow of snow / of lava' b. la couchée / le couchage des réfugiés -la couchée / *le couchage du soleil 'the going-to-bed of refugees / the setting of the sun'

The contrasts in (9a-b) are explained by the fact that it is not possible to cause the sunset, or to take into account an external cause (other than natural) for the flowing of lava or of snow. Conversely, the examples in [START_REF] Smith | The Parameter of Aspect[END_REF] are acceptable because it is possible to have an external initiator of the situation expressed by the verb COULER 'flow', and therefore the property 'causally affected' of the proto-patient is present: [START_REF] Smith | The Parameter of Aspect[END_REF] le coulage / la coulée d'eau 'the flowing of water'

We can therefore conclude that in the case of unaccusative verbs that select an internal argument which cannot be affected by causation, the internal argument cannot figure as a participant (y) in the complex event structure in [START_REF] Van Geenhoven | For-adverbials, Frequentative Aspect, and Pluractionality[END_REF].

(

) [ x CAUSE [BECOME y <STATE>]] 11
In addition, it also allows us to refine the 'agentivity' property of -age, proposed in Kelling (2001) and Martin (2008). [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] proposed to extend the 'agentivity' property characterizing -age deverbals on transitive bases to account for two unaccusative verbs, ARRIVER 'arrive' and POUSSER 'grow', giving rise to -age nouns. However, she neither mentions the conditions in which this property is neutralized, nor whether these unaccusative verbs are the only ones that may involve "agentivity" when nominalized by -age.

Refinement of our proposal

Our study reveals several points.

(i) This 'agentivity' property cannot be extended to all the unaccusatives (even those without a transitive counterpart), as in [START_REF] Laca | Indefinites, Quantifiers and Pluractionals: What Scope Effects Tell us about Event Pluralities. Non-definiteness and Plurality[END_REF]. (ii) An unaccusative verb can be nominalized by -age and yet not involve agentivity [START_REF] Zucchi | The Language of Propositions and Events[END_REF]. [START_REF] Zucchi | The Language of Propositions and Events[END_REF] PASSER 'pass' le passage de l'ouragan 'the passing of the hurricane'

(iii) Unergatives (as in 14a) and some transitive verbs in the corpus (15b) are not causative, even if they allow nominalization by -age. Causation is therefore highlighted by -age nominalization in a very particular way. We propose that causation is not directly introduced by -age (since certain -age nominalizations of unaccusative bases are not causative) but only highlighted when the verb inherently possesses this property. In other words the internal argument must have a proto-P property "be causally affected", which must be specified in the lexical entry of the verb. The proto-P property on the internal argument implies a proto-A property: "x causally affects y". It is conceivable, according to our study, that this lexical property of the verb is only activated through morphological derivation.

Aspectual properties

Since the rivalry between nominalizations with -age and -ée does not seem to be constrained by the argument structure of the verbal base, we continue our investigations by examining the lexical-aspectual properties of the verbs.

Aspectual properties of the verbal bases

Our corpus analysis shows that -age and -ée nominalizations are not sensitive to the lexical-aspectual class of their verbal bases, since they can select bases from all the aspectual classes except for pure states: activities (15), accomplishments (16), and achievements (17).

(15) POUSSER 'push' ACT deux heures de poussage / de poussée (naissance) two hours of pushing / of push (delivery) (16) PESER (tr) 'weigh' ACC pesage / pesée de l'enfant 'the weighing of the baby' (17) ARRIVER 'arrive' ACH l'arrivage du navire / l'arrivée du navire 'the "arriving" / the arrival of the ship'

Aspectual inheritance vs. aspectual shift

The application of the set of tests for French nominalizations elaborated by [START_REF] Haas | Du verbe au nom: calques et décalcages aspectuels[END_REF] to the -age and -ée pairs allows us to conclude that the two constructions have different lexical-aspectual values, which they generally inherit from the verbal bases, but which can also be the result of an aspectual shift induced by nominalization.

Aspectual inheritance

Activity verbs can give rise to activity nominals with -age and -ée, as shown by the fact that these nominals reject the structure un N de x-temps 'a N of x-time' in (19a), excluded for ACT nominals [START_REF] Haas | Du verbe au nom: calques et décalcages aspectuels[END_REF]). Accomplishments give rise to Durative Culminative Occurrences (DCO, following terminology and tests from Haas et al 2008). This is indicated in (19b) by the fact that the corresponding nominals appear in 'x time of N'. There are also achievements that give rise to Punctual Occurences (PO, 19c). Contrary to ACT nominals, DCO and PO nominals appear in the subject of a eu lieu 'happened'. DCO nominals, but not PO nominals, can be the subject of a duré 'lasted' and appear in en cours de 'in the process of' N.

Aspectual shift

Haas et al. (2008) added a new category of deverbal nouns: Durative non-Culminative Occurrences (DnCO). The DnCO MANIFESTATION 'demonstration' is derived from an activity verb MANIFESTER 'demonstrate' but successfully passes the test 'subject of a eu lieu 'happened' (which excludes activity nominals). DnCOs differ from other Occurrences (DCO, PO) in not being culminative; that is, if the process denoted by the noun is interrupted, we can nonetheless assert that the denoted event took place (e.g., the manifestation has been interrupted they manifested, vs. the delivery has been interrupted # she gave birth)

Consequently, there are cases in which the aspectual value of the base is shifted in the nominalization process. Such cases include (i) activity bases which derive DnCOs (19a-b), as shown by their ability to appear with pendant 'during'; (ii) achievement bases giving rise to DCO (instead of PO), which can take en cours de 'in the process of' in (19c). a. V ACT N DnCO (for -age and -ée ): traîner la quille 'to drag the keel' pendant le traînage/ pendant la traînée 'during the dragging / during the "drag"' b. V ACT N DnCO ( for -ée ): chevaucher pendant deux heures (activity) 'to ride for two hours' le jour de la chevauchée (DnCO) 'the day of the ride' c. V ACH N ODC (for -age) ARRIVER 'arrive' (ACH) 5173 tonnes (de céréales) étaient en cours d'arrivage par camions '5173 tones (of cereals) were in the process of arriving by trucks'

These results show that the two nominalizations -age and -ée are not tied to specific lexical-aspectual values. However, in the case of -age, we can remark that the shift goes in the direction of durativity (as in 20c), whereas in the case of -ée, the shift is associated with terminativity. Nonetheless, the Aktionsart of these nominals seems to be insufficient in distinguishing their properties. In the following section, we will show that the distinguishing factor is in fact their contribution on the level of grammatical aspect (viewpoint -Smith (1991)).

Grammatical aspect in nominalizations

Given the existence of these pairs of nouns, it is reasonable to hypothesize that the two nominalizations correspond to different ways of conceptualizing events: focusing on the event as a whole (closed) in the case of -ée, or, in the case of -age, focusing on the ongoing process or on an internal phase of the event denoted by the verbal base. Thus, -age introduces the imperfective aspect, while -ée introduces the perfective aspect. The difference should therefore be situated on the level of grammatical aspect (viewpoint), which usually shows up in the verbal domain in French. In this light, we propose the following account of the pairs:

(20) Proposal: With the same verbal base (tr., unacc. and unerg.) -age and -ée contribute grammatical aspect introducing an imperfective vs. perfective value

Series of arguments supporting this semantic difference

The first argument is provided by the semantic difference between the two nominalizations, which is highlighted by the following distributional tests.

(i) Event nominals with -ée, but not with -age, can appear with the preposition APRÈS 'after', which requires a perfective event as its complement, exactly as in the case of (finite and non-finite) complement clauses.

(21) a. ??après l'arrivage de la marchandise / après l'arrivée de la marchandise' 'after the arriving of the merchandise / after the arrival of the merchandise' b. après être arrivée, la marchandise a été vendue 'after being arrived, the merchandise has been sold' (22) a. ??après le pesage du bébé / après la pesée du bébé 'after the weighing of the baby' b. après avoir pesé le bébé 'after having weighed the baby'

(ii) Event nominals with -age, but not with -ée, can appear as object of INTERROMPRE 'interrupt' (23), or as subject of PROGRESSER 'progress' (24).

(23) L'arrivage / ??l'arrivée des ouvriers a été interrompu(e) par un convoi de police 'the arriving / the arrival of the workers has been interrupted by a police crew' (24)

Le perçage / ??la percée du tunnel a progressé. 'the drilling / the "drilling" of the tunnel progressed'

(iii)

The two nominalizations have different meanings (namely 'process in development' with -age and 'whole process' with -ée), when they appear as objects of FILMER 'to film' (25) or SURVEILLER 'supervize' (26).

(27) a. J'ai filmé le pesage du bébé (le déroulement / une portion du procès)

I filmed the weighing of the baby (the development / a phase of the process) b. J'ai filmé la pesée du bébé (la globalité de l'event : début, milieu, fin) I filmed the weighing of the baby (the whole event: start, development, end) (28) a. J'ai surveillé l'arrivage des marchandises (le déroulement du procès) 'I supervised the arriving of goods' ('supervise the process') b. #J'ai surveillé l'arrivée des marchandises (épier, guetter, attendre) 'I supervised the arrival of goods' ('look for, wait for the arrival')

(iv) pluractionality of -age as manifestation of its imperfectivity value Another argument for imperfectivity in the case of -age nominals is their pluractional meaning. Recall that in the literature on pluractionality, pluractional markers are defined as imperfective (iterative or habitual) aspectual operators (cf., Van Geenhoven ( 2004)). Nominalizations with -age involve a pluractional meaning which conflicts, in the case of achievement verbal bases, with the cardinality of the internal argument, thus explaining the contrasts in ( 29) and ( 30).

(29) *l'arrivage d'un légume / OK des légumes, de la marchandise 'the arriving of a vegetable / of vegetables, of the merchandise' (30) *le tuage d'une mouche / OK de mouches 'the killing of a fly / of flies'

Similar tests have been used crosslinguistically in the domain of verbal aspect for West Greenlandic in Van Geenhoven (2004) and aspectual periphrases with andar in Spanish by [START_REF] Laca | Indefinites, Quantifiers and Pluractionals: What Scope Effects Tell us about Event Pluralities. Non-definiteness and Plurality[END_REF]. Pluractionality has been also documented for Romanian Supine nominalizations by Iordăchioaia & Soare (2008), [START_REF] Alexiadou | Nominal/Verbal Parallelisms and Number/Aspect Interactions in the Syntax of Nominalizations[END_REF]. In (31), the supine derived from 'kill' is ruled out when combined with a singular argument: (31) ucisul *unui jurnalist / jurnaliştilor de către mafia politică 'the killing *of a journalist / of journalists by the political mafia'

[Romanian]

Extension to nominalizations with -age/ -ment

Our proposal, according to which -age/-ée introduce an opposition at the level of grammatical aspect, allows us to reconsider the treatment of nominalization withage/ -ment put forward in [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF]. [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] explains the contrast in (32b) through the fact that a pedestrian is not an incremental Theme.

(32) a. Pierre a écrasé une banane/ un piéton 'Peter crushed a banana / ran over a pedestrian' b. l'écrasage d'une banane / # l'écrasage d'un piéton 'the crushing of a banana' / "the running over of a pedestrian" c. l'écrasement d'un piéton "the running over of a pedestrian" If our proposal for -age/ -ée pairs can be extended to -age/-ment, more precisely, if nominalization with -ment can be considered as highlighting the global event, then the contrast in (32b) -(32c) is predicted 1 . In pairs, -age nominals denote an ongoing event, so in (32b), écrasage cannot take a pedestrian as an argument, because run over a pedestrian denotes a punctual event (an achievement), and cannot be conceptualized in its development, but only as a global (closed) situation.

unaccusative verbs, then also accounting for le gonflement du ballon par Pierre 'the inflation of the balloon by Pierre' exactly as for transitive base verbs of our corpus selected by both nominalizations. For transitive-unaccusative verbs, -ée can also select the complex event structure, but -age can only select the complex one, because of their respective grammatical aspect values.

Nominalization of unaccusative verbs without transitive counterparts

Our proposal makes the following prediction: because these unaccusative verbs have a simple event structure [without an external initiator (x)] they will only be selected by -ée (39). The prediction is borne out: (40c) vs. (40b) :

(39) PERCER 2 émerger 'to emerge': [BECOME y <émergé>] (40) a. @les fleurs ont percé / l'entreprise a rapidement percé (PERCER 2 émerger) 'the flowers "broke through"' 'the enterprise broke through' b. # le perçage des fleurs/ # le perçage de l'entreprise 'the "breaking-through" of the flowers' 'the breaking through of the enterprise' c. @la percée des fleurs / la percée de l'entreprise 'the "break-through" of the flowers' 'the breaking through of the enterprise'

Our proposal then covers the distribution of patterns that [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] treats in terms of length of the eventive chain, but it goes further: (i) by proposing a principled reason for this distribution : because N -age denotes an ongoing process (so a portion of it) -imperfective view point -it highlights the initiator of the situation denoted by the verb, involved in the ongoing process; (ii) by accounting for the fact that the complex event structure is not only combinable with -age, but also with -ée (and also with -ment examples of [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF]). The same proposal (i.e. ( 21)) allows us to account for the selectional restrictions in the case of transitive-unaccusative verbs (age selects the transitive one, -ée selects the unaccusative one) but also to predict the nominalization of 'pure' unaccusative verbs.

Conclusion

By comparing the properties of -age and -ée in pairs, we have shown that these nominalizations encode different values of grammatical aspect, e.g. imperfective vs. perfective, in other words that there is a complementary distribution.

The originality of the proposal consists in the existence, in the nominal domain, of this level of grammatical aspect, normally reserved to the verbal domain in French. We support our proposal by specific tests devoted to nominalizations.

-Consequently, the various properties associated with -age nominals in the literature (e.g., agentivity, incrementality, length of the eventive chain) follow from our general proposal that -age and -ée convey different grammatical aspectual values. -The other properties we studied also fall under this proposal, namely the fact that nominalizations with -age and -ée can select all types of bases, but -age exhibit preference for transitive bases, whereas -ée for unaccusative ones.

Correlatively, -age nominals built on unaccusative bases reveal a part of the argument structure of the verb, which is invisible to syntax. Moreover, in spite of the general inheritance of the lexical aspectual value of the base verb in the deverbal nouns, there is also aspectual shift, reflecting durativity in the case of -age and terminativity in the case of -ée. --The next step of our research will be to test the hypothesis of the existence of grammatical aspect to the whole -age / -ée corpus. We hypothesize that generally the grammatical aspect oppositions are encoded in pairs (-age/-ée,age/-ment, etc) but they can be lexicalized by a single nominalization rule, when pairs are not available.

( 12 )

 12 COULER [unacc] 'flow' coulée / * coulage de la lave 'flow / *flowing of the lava'

  'jump' sautage 'jumping' (trampoline) b. remonter l'escalier 'to climb back upstairs' le remontage d'escalier 'the climbing back upstairs'

  (18) a. V ACT N ACT CRIER (unerg.) 'shout' : Il a crié pendant une heure/ #en une heure He shouted for an hour / #in an hour une heure de criage / # un criage d'une heure an hour of shouting / #a shouting of an hour b. V ACC N DCO plumer un volatile pendant le plumage des oies/ entre deux plumées d'oies 'to pluck a bird' 'during the plucking of geese / between two pluckings of geese' c. V ACH N PO ARRIVER 'arrive' (unacc.) : le train est arrivé à 20h00 l'arrivée du train à 20h00 the train arrived at 8p.m the arrival of the train at 8p.m.

These examples would also involve, for -age/ -ment pairs, an interplay between the Aktionsart of the verb and the grammatical aspect of the nominalization, which may a priori not hold for -age/-ée.

In this event structure, the slashes note the portion of the event highlighted by the each nominalization.

Confirmation and extension of the proposal: transitive-unaccusative verbs; transitive verbs and unaccusative verbs

Selectional restrictions on the nominalization of transitive-unaccusative verbs

Our proposal is further confirmed by selectional restrictions on these nominalizations in the case of transitive-unaccusative verbs (see also [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] for -age/-ment). As shown in (33), -age selects the transitive base whereas the unaccusative base is selected by -ée.

(33) a. Marie a percé son abcès > le perçage de l'abcès. 'Mary burst her abscess / the bursting of the abscess' b. Son abcès a percé > la percée de l'abcès /vs. #le perçage de l'abcès 'Her abscess burst / the bursting of the abscess' (i) Proposal: Given that -age conceptualizes the situation type denoted as ongoing, then it is expected that -age selects the event structure involving the initiator (or the volitional causer) of the ongoing process: the complex one (transitive pattern) where figures the initiator, x, whereas -ée will select the simple one (unaccusative pattern):

(ii) Account of these selectional restrictions for -age vs. -ment deverbals of transitive-unaccusative verbs by [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF]. According to [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] [Property 1], for GONFLER 'inflate, blow' (transitive-unaccusative verb), -age deverbals are built on the long eventive chain of the verb (the transitive pattern) : gonflage du ballon par Pierre, while -ment deverbals are built on the short one (the unaccusative pattern) : gonflement du ballon 'the inflation of the balloon'. This distribution is correct, but, as noted by [START_REF] Martin | The Semantics of Eventive Suffixes in French[END_REF] herself, -ment deverbals can also be built on the long eventive chain of the alternating verbs (gonflement du ballon par Pierre 'the inflation of the balloon by Pierre'). This casts doubts on the exploitation of the notion of length eventive chain for explaining the selectional restrictions.

Transitive-unaccusative and transitive bases selected by both -age/-ée

If -age and -ée respectively introduce imperfective and perfective grammatical aspect, the selectional restrictions in the case of transitive-unaccusative verbs follows naturally : -age is predicted to select only the complex event structure because it contains the initiator of the denoted situation type (35a) -transitive pattern ; whereas -ée will select the simple event structure ((35b) -unaccusative pattern) Because -ée presents the situation as closed, we predict that -ée can also select a complex event structure including the initiator (35a) in case of transitive -