Emilie Morvant
email: emilie.morvant@lif.univ-mrs.fr

Amaury Habrard
email: amaury.habrard@lif.univ-mrs.fr

Stéphane Ayache
email: stephane.ayache@lif.univ-mrs.fr

On the Usefulness of Similarity based Projection Spaces for Transfer Learning

Keywords: Good Similarity Functions, Transfer Learning, Domain Adaptation, Image Classification

Similarity functions are widely used in many machine learning or pattern recognition tasks. We consider here a recent framework for binary classification, proposed by Balcan et al., allowing to learn in a potentially non geometrical space based on good similarity functions. This framework is a generalization of the notion of kernels used in support vector machines in the sense that allows one to use similarity functions that do not need to be positive semi-definite nor symmetric. The similarities are then used to define an explicit projection space where a linear classifier with good generalization properties can be learned. In this paper, we propose to study experimentally the usefulness of similarity based projection spaces for transfer learning issues. More precisely, we consider the problem of domain adaptation where the distributions generating learning data and test data are somewhat different. We stand in the case where no information on the test labels is available. We show that a simple renormalization of a good similarity function taking into account the test data allows us to learn classifiers more performing on the target distribution for difficult adaptation problems. Moreover, this normalization always helps to improve the model when we try to regularize the similarity based projection space in order to move closer the two distributions. We provide experiments on a toy problem and on a real image annotation task.

Introduction

Many machine learning or pattern recognition algorithms are based on similarity functions. Among all of the existing methods, we can cite the famous k-nearest neighbors, k-means or support vector machines (SVM). An important point is to choose or adapt the similarity to the problem considered. For example, approaches dealing with numerical vectors are often based on the Mahalanobis distance [START_REF] Davis | Information-theoretic metric learning[END_REF][START_REF] Goldberger | Neighbourhood components analysis[END_REF][START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] and many methods designed for structured data (strings, trees or graphs) exploit the notion of edit distance [START_REF] Bernard | Learning probabilistic models of tree edit distance[END_REF][START_REF] Gao | A survey of graph edit distance[END_REF][START_REF] Ristad | Learning string-edit distance[END_REF]. For binary classification with SVM classifiers, the similarity function must often be a valid kernel 1 in order to define a potentially implicit projection space which is an Hilbert space and where data can be more easily separated. In this case, the similarity function must be symmetric and positive semi-definite (PSD), allowing one to define a valid dot product in the implicit projection space. However, these constraints may rule out some natural similarity functions. Recently, a framework proposed by Balcan et al. [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF][START_REF] Balcan | A theory of learning with similarity functions[END_REF] considers a notion of good similarity function that overcomes these limitations. Intuitively, this notion only requires that a sufficient amount of examples are on average more similar to a set of reasonable points of the same class than to reasonable points of the opposite class. Then, the similarity can be used to build an explicit (potentially non geometrical) projection space, corresponding to the vector of similarities to the reasonable examples. In this similarity based projection space, a classifier with good generalization capabilities can be learned.

This kind of result holds in a classical machine learning setting, where test data are supposed to have been generated according to the same distribution than the one used for generating labeled learning data. This assumption is in fact very useful to obtain good generalization results, but is not always valid in every application. For example, in an image classification task, if labeled data consist of images extracted from the web and test data images extracted from different videos, the various methods of data acquisition may imply that labeled data are no longer representative of test data and thus of the underlying classification task. This kind of issue is a special case of transfer learning [START_REF] Pan | A survey on transfer learning[END_REF] called domain adaptation (DA) [START_REF] Jiang | A literature survey on domain adaptation of statistical classifiers[END_REF][START_REF] Quionero-Candela | Dataset Shift in Machine Learning[END_REF]. DA arises when learning and test data are generated according to two different probability distributions: the first one generating learning data is often referred to as the source domain, while the second one for test data corresponds to the target domain. According to the existing theoretical frameworks of DA [START_REF] Ben-David | A theory of learning from different domains[END_REF][START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF] a classifier can perform well on the target domain if its error relatively to the source distribution and the divergence between the source and target distributions are together low. One possible solution to learn a performing classifier on the target domain is to find a projection space in which the source and target distributions are close while keeping a low error on the source domain. Many approaches have been proposed in the literature to tackle this problem [START_REF] Blitzer | Domain adaptation with structural correspondence learning[END_REF][START_REF] Bruzzone | Domain adaptation problems: A DASVM classification technique and a circular validation strategy[END_REF][START_REF] Daumé | Frustratingly easy domain adaptation[END_REF][START_REF] Jiang | Instance weighting for domain adaptation in NLP[END_REF].

In this paper, we consider the case where a learning algorithm is provided with labeled data from the source domain and unlabeled data from the target one. Our aim is to investigate the interest of the framework of Balcan et al. for domain adaptation problems. More precisely, we propose to study how we can use the lack of geometrical space of this framework to facilitate the adaptation. We consider two aspects. First, the influence of a renormalization of the similarity function according to the unlabeled source and target data. Second, the addition of a regularization term to the optimization problem considered for 1 Nevertheless there exists some approaches allowing to use indefinite kernels [START_REF] Haasdonk | Feature space interpretation of svms with indefinite kernels[END_REF].

learning the classifier in order to select reasonable points that are relevant for the adaptation. This approach can be seen as a feature selection for transfer learning aiming at moving closer the two distributions. We show experimentally that these two aspects can help to learn a better classifier for the target domain. Our experiments are based on a synthetic toy problem and on a real image annotation task.

The paper is organized as follows. We introduce some notations in Section 2. Then we present the framework of good similarity functions of Balcan et al. in Section 3. We next give a brief overview of domain adaptation in Section 4. We present in Section 5 the approach considered and we describe our experimental study in Section 6. We conclude in Section 7.

Notations

We denote by X ⊆ R d the input space. We consider binary classification problems with Y = {-1, 1}, the label set. A learning task is modeled as a probability distribution P over X × Y , D being the marginal distribution over X. For any labeled sample S drawn from P , we denote by S |X the sample constituted of all the instances of S without the labels. In a classical machine learning setting, the objective is then to learn a classifier h : X → Y belonging to a class of hypothesis H such that h has a low generalization error err P (h) over the distribution P . The generalization error err P (h) corresponds to the probability that h can commit an error according to the distribution P , which is defined as follows:

∀h ∈ H, err P (h) = E (x,y)∼P L(h(x), y)

where L corresponds to the loss function modeling the fact that h(x) = y. We will see later that in a DA scenario, we consider two probability distributions P S and P T corresponding respectively to a source domain and a target one.

We now give a definition about the notion of similarity functions.

Definition 1. A similarity function over X is any pairwise function

K : X × X → [-1, 1]. K is symmetric if for any x, x ∈ X: K(x, x ) = K(x , x).
A similarity function is a valid kernel function if it is positive semi-definite, meaning that there exists a function φ from X to an implicit Hilbert space such that K defines a valid dot product in this space, i.e. K(x, x ) = φ(x), φ(x ) . Using a valid kernel offers the possibility to learn a good classifier into a high dimensional space where the data are supposed to be linearly separable. However, the choice or the definition of a good kernel can be a tricky task in general. We present in the next section a framework that proposes a rather intuitive notion of good similarity function that gets rid of the constraints of a kernel.

E (x ,y )∼P yy K(x, x )|R(x ) ≥ γ, (1)
(ii) P r x [R(x )] ≥ τ .
From this definition, a large proportion of examples must be on average more similar, with respect to the margin γ, to random reasonable examples of the same class than to random reasonable examples of the opposite class. Moreover, at least a proportion τ of examples should be reasonable. Definition 2 includes all valid kernels as well as some non-PSD non symmetric similarity functions [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF][START_REF] Balcan | A theory of learning with similarity functions[END_REF]. The authors have shown that this definition of good similarities allows also to solve problems that can not be handled by classical kernels, which makes the definition a strict generalization of kernels. According to the following theorem, it provides sufficient conditions to learn a good linear classifier in an explicit projection space defined by the reasonable points in the set R.

Theorem 1 (Balcan et al. [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF]). Let K be an ( , γ, τ )-good similarity function for a learning problem

P . Let S = {x 1 , . . . , x d } be a sample of d = 2 τ log( 2 δ ) + 8 log(2/δ) γ 2
landmarks (potentially unlabeled) drawn from P . Consider the mapping φ R : X → R d defined as follows: φ R i (x) = K(x, x i ), i ∈ {1, . . . , d}. Then, with probability at least 1 -δ over the random sample R, the induced distribution φ R (P ) in R d has a separator of error at most + δ relative to L 1 margin at least γ/2. Thus, with an ( ,γ,τ )-good similarity function for a given learning problem P and enough (unlabeled) landmark examples, there exists with high probability a low-error linear separator in the explicit φ R -space, corresponding to the space of the similarities to the d landmarks. The criterion given by Definition 2 requires to minimize the number of margin violations which is a NP-hard problem generally difficult to approximate. The authors have then proposed to consider an adaptation of Definition 2 with the hinge loss formalized as follows.

Definition 3 (Balcan et al. [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF]). A similarity function K is an ( , γ, τ )-good similarity function in hinge loss for a learning problem P if there exists a (random) indicator function R(x) defining a (probabilistic) set of "reasonable points" such that the following conditions hold:

(i) we have

E (x,y)∼P [1 -yg(x)/γ] + ≤ , (2)
where

g(x) = E (x ,y )∼P [y K(x, x )|R(x )] and [1 -c] + = max(0, 1 -c) is the hinge loss, (ii) P r x [R(x )] ≥ τ .
Using the same φ R -space than Theorem 1, the authors have proved a similar theorem for this definition with the hinge loss. This leads to a natural two step algorithm for learning this classifier: select a set of potential landmark points and then learn a linear classifier in the projection space induced by these points. Then, using d u unlabeled examples for the landmark points and d l labeled examples, this linear separator α ∈ R du can be found by solving a linear problem. We give here the formulation based on the hinge loss presented in [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF].

min α d l i=1   1 - du j=1 α j y i K(x i , x j )   + such that du j=1 |α j | ≤ 1/γ. (3)
In fact, we consider a similar formulation based on a 1-norm regularization, weighted by a parameter λ related to the desired margin.

min α d l i=1   1 - du j=1 α j y i K(x i , x j )   + + λ α 1 . (4)
In the following, a classifier learned in this framework is called a SF classifier.

Domain Adaptation

Domain adaptation (DA) [START_REF] Ben-David | A theory of learning from different domains[END_REF][START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF] arises when the learning data generation is somewhat different from the test data generation. The learning data, generally called the source domain, is represented by a distribution P S over X × Y and the test data, referred to the target domain, is modeled by a distribution P T . We denote by D S and D T the respective marginal distributions over X.

A learning algorithm is generally provided with a Labeled Source sample LS = {(x i , y i )} m i=1 drawn i.i.d. from P S , and a Target Sample which contains a large set of unlabeled target instances T S = {x j } m j=1 drawn i.i.d. from D T and sometimes a few labeled target data drawn from P T . The objective of a learning task is then to find a good hypothesis with a low error according to target distribution P T . In this section, we provide a brief and non-exhaustive overview of some existing DA approaches, note that some surveys can be found in [START_REF] Jiang | A literature survey on domain adaptation of statistical classifiers[END_REF][START_REF] Quionero-Candela | Dataset Shift in Machine Learning[END_REF] The first theoretical analysis of the DA problem was proposed by Ben-David et al. [START_REF] Ben-David | A theory of learning from different domains[END_REF][START_REF] Ben-David | Analysis of representations for domain adaptation[END_REF]. The authors have provided an upper bound on the target domain error err P T that takes into account the source domain error err P S (h) and the divergence d H between the source and target marginal distributions:

∀h ∈ H, err P T (h) ≤ err P S (h) + 1 2 d H (D S , D T ) + ν. (5)
The last term corresponds to the optimal joint hypothesis over the two domains ν = argmin h∈H err P S (h) + err P T (h). It can be seen as a quality measure of H for the DA problem considered. If this best hypothesis performs poorly, it appears then difficult to obtain a good hypothesis for the target domain. This term is then supposed to be small to ensure a successful adaptation.

The other crucial point is the divergence2 d H which is called the H-distance. This result suggests that if the two distributions are close, then a low error classifier over the source domain can be a good classifier for the target one. The intuition behind this idea is given in Figure 1. The distance d H is actually related to H by measuring a maximum variation divergence over the set of points on which an hypothesis in H can commit errors:

d H (D S , D T ) = 2 sup h∈H P r D S [I(h)] -P r D T [I(h)]
where

x ∈ I(h) ⇔ h(x) = 1.
An interesting point of this theory is that the H-distance can be estimated from finite samples when the VC-dimension of H is finite. Using a VC-dimension analysis, the authors show that the empirical divergence converges to the true d H with the size of the samples. Let U S be a sample i.i.d. from D S and U T a sample i.i.d. from D T . Consider a labeled sample U S U T where each instance of U S is labeled as positive and each one of U T as negative. The empirical divergence can then be directly estimated by looking for the best classifier able to separate the two samples3 [START_REF] Ben-David | A theory of learning from different domains[END_REF]:

dH (U S , U T ) = 2 1 -min h∈H ê rr U S ,U T (h) , (6)
with ê rr

U S ,U T (h) = 1 m     x∈U S ∪U T , h(x)=-1 1 x∈U S + x∈U S ∪U T , h(x)=1 1 x∈U T     , where 1 x∈U S = 1 if x ∈ U S 0 otherwise.
Note that finding the optimal hyperplane is NP-hard in general. However, a good estimation of dH allows us to have an insight of the distance between the two distributions and thus of the difficulty of the DA problem for the class H. We will use this principle to estimate the difficulty of the task considered in our experimental part. Later, Mansour et al. [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF] have proposed another discrepancy measure allowing one to generalize the d H distance to other real valued loss functions. Note that the bound presented in their work is a bit different from the one of Ben-David et al.. Moreover, they have also provided an average analysis with interesting Rademacher generalization bounds. These theoretical frameworks show that for a good domain adaptation, the distance between distributions and the source error must be low. According to [START_REF] Ben-David | Impossibility theorems for domain adaptation[END_REF], minimizing these two terms appears even necessary in general.

+ +++ + + + + + + + + -- - -- - - - --- + + + + + + + + + + + + -- - -- - - - - -- (a)
One key point for DA approaches is thus to be able to move closer the distributions while avoiding a dramatic increase of the error on the source domain. In the literature, some methods have proposed to reweight the source instances in order to get closer to the target distribution. They are often based on some assumptions on the two distributions [START_REF] Bickel | Discriminative learning for differing training and test distributions[END_REF][START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF][START_REF] Jiang | Instance weighting for domain adaptation in NLP[END_REF][START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF][START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF]. For example some of these approaches rely on hypothesis like the covariate shift where the marginal distributions over X may be different for the two domains, but the conditional distribution of Y given X are the same, i.e. P S (y|x) = P T (y|x) for every x ∈ X and y ∈ Y but P S (x) = P T (x) for some x ∈ X [START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF]. Other works are based on iterative self labeling approaches in order to move progressively from one domain to the other one [START_REF] Bruzzone | Domain adaptation problems: A DASVM classification technique and a circular validation strategy[END_REF]. Another standpoint for moving closer the two distributions is to find a relevant projection space where the two distributions are close. In [START_REF] Blitzer | Domain adaptation with structural correspondence learning[END_REF], the authors propose a structural correspondence learning approach to identify relevant features by looking for their correspondence in the two domains. Another idea is to use an augmented feature space for both source and target data and use the new input space obtained with classical machine learning algorithms [START_REF] Daumé | Frustratingly easy domain adaptation[END_REF]. Some authors have also proposed to use spectral approaches to build a new feature space [START_REF] Pan | Domain adaptation via transfer component analysis[END_REF].

The main underlying ideas among the different approaches presented in this section is that a potential good adaptation needs to have the source and target distributions close. One way to achieve this goal is to build a relevant feature space by defining a new projection operator or by choosing relevant features. In the next section, we study the usefulness of the framework of Balcan et al.. to deal with domain adaptation problems. More precisely, we propose to investigate how the definition of the similarity function and the construction of the feature space -i.e. the φ-space of similarities to a set of reasonable points -can help to improve the performance of the classifier in a domain adaptation setting.

Modifying the Projection Space for Domain Adaptation

In this section, we present our two approaches for modifying the similarity based projection space in order to facilitate the adaptation to the target distribution. First, we present a simple way for renormalizing a similarity function according to a sample of unlabeled instances. Second, we propose a regularization term that tends to define a projection space where the source and target marginal distributions tend to be closer.

A Normalization of a Similarity Function

For a particular DA task, we build a new similarity function K N by normalizing a given similarity function K relatively to a sample N . Recall that, from Definition 2, a similarity must be good relatively to a set of reasonable points. We propose actually to renormalize the set of similarities to these points. Since the real set of reasonable points is unknown a priori, we consider a set of candidate landmark points R and we apply a specific normalization for each instance of x j ∈ R . The idea is to apply a scaling to mean zero and standard deviation one for the similarities of the instances of N to x . Our procedure is defined as follows.

Definition 4. Let K be a similarity function which verifies the Definition 2. Given a data set N = {x k } p k=1 and a set of (potential) reasonable points R = {x j } du j=1 , a normalized similarity function, K N , is defined by:

∀x j ∈ R , K N (., x j ) =                K(., x j ) -µ x j σ x j if -1 ≤ K(.,x j )-μ x j σx j ≤ 1, -1 if -1 ≥ K(.,x j )-μ x j σx j , 1 if K(.,x j )-μ x j σx j ≥ 1, (7)
where μx j is the empirical mean of similarities to x j over N :

∀x j ∈ R , μx j = 1 |N | x k ∈N K(x k , x j ),
and σx j is the empirical unbiased estimate of the standard deviation:

∀x j ∈ R , σx j = 1 |N | -1 x k ∈N K(x k , x j ) -μx j 2 .
By construction, the similarity K N is then non symmetric and non PSD. In the following, we will consider that a learning algorithm is provided with two data sets: LS = {(x i , y i )} m i=1 constituted of labeled source domain data, and T S = {x i } m i=1 of unlabeled target domain data. According to the theoretical result of domain adaptation of Ben-David et al.. recalled in Equation ( 5), the learned classifier should also perform well on the source domain. We then propose to define our normalized function, denoted by K ST , with N = LS |X ∪T S in order to link the two domains by considering the information of both of them at the same time, for avoiding an increasing of the source error. Our choice is clearly heuristic and our aim is just to evaluate the interest of renormalizing a similarity for domain adaptation problems. In order to study the potential of adaptation, we will only consider candidate landmark points R from the source domain.

An Additional Regularization Term For Moving Closer the Two Distributions

As a second contribution, we propose to add a regularization term to the optimization Problem 4 proposed by Balcan et al.. The objective is to control the selection of reasonable points leading to a projection space where the two distributions are close. According to the empirical divergence d H given in Equation 6, the source and the target domains are close if it is difficult to separate source from target examples. Let two subsets U S ⊆ LS and U T ⊆ T S of equal size, our idea is then to build a set C ST of pairs belonging to U S × U T . And then, for each pair (x s , x t ) ∈ C ST , we propose to regularize the learned classifier such that the outputs of the classifier are close for the two instances x s and x t . For any classifier h(•) = |R| i=1 α i K(•, x i ), this can be expressed as follows:

|h(x s ) -h(x t )| = |R| j=1 α j K(x s , x j ) - |R| j=1 α j K(x t , x j ) ≤ |R| j=1 α j K(x s , x j ) -K(x t , x j ) by using triangle inequality = ( t φ R (x s ) -t φ R (x t )) diag(α) 1 . (8)
This leads us to propose a new regularization term which tends to select landmarks with similarities close to both some source and target points, which allows us to define a projection space where source and target examples are closer. Let R be a set of d u candidate landmark points, our global optimization problem is then defined as follows:

min α d l i=1   1- du j=1 α j y i K(x i , x j )   + +λ α 1 +C (xs,xt)∈C ST ( t φ R (x s )-t φ R (x t )) diag(α) 1 (9)
The construction of C ST is difficult since we have no information on the target labels. In practice, we build the matching C ST from U S and U T by looking for a bipartite matching minimizing the Euclidean distance in the φ-space defined by the set of candidate landmarks. This can be done by solving the following problem. Note that in the particular case of bipartite matching, this can be done in polynomial time by linear programming for example.

               min βst 1≤s≤|U S | 1≤t≤|U T | (xs,xt)∈U S ×U T β st φ R (x s ) -φ R (x t ) 2 2 s.t.: ∀(x s , x t ) ∈ U S × U T , β st ∈ {0, 1}, ∀x s ∈ U S , xt∈U T β (st) = 1, ∀x t ∈ U T , xs∈U S β (st) ≤ 1.
Then C ST corresponds to the pairs of U S × U T such that β st = 1. The choice of the points of U S and U T is hard and in an ideal case, we would like to select pairs of points of the same label. But since we suppose that no target label is available, we select the sets U S and U T randomly from the source and target samples, from different draws, and we choose the best sets thanks to a reverse validation procedure described in Appendix A.

Experiments

We now propose to evaluate the approaches presented in the previous section on a synthetic toy problem and on a real image annotation task. For every problem, we consider to have: a labeled source sample LS drawn from the source domain, a set of potential landmark points R drawn from the marginal source distribution over X and an unlabeled target sample T S drawn from the marginal target distribution over X.

As a baseline, we choose a similarity based on a classical Gaussian kernel, which is a good similarity function according to the framework of Balcan et al.:

K(x, x ) = exp - x -x 2 2 D 2 .
We then consider the normalized similarity K ST which corresponds to the normalization of K according to the instances of the source and target samples LS |X ∪ T S. For each of the two similarities K and K ST , we compare the models learned by solving Problem (4), corresponding to learning a classical SF-based classifier, to those learned using our regularized formulation in Problem [START_REF] Blitzer | Domain adaptation with structural correspondence learning[END_REF]. We tune the hyperparameters with a "reverse" validation procedure described in Appendix A. Moreover, in order to evaluate if K ST is a better similarity for the target domain, we propose to study the ( ,γ,τ )-guarantees on the target sample according to Definition 3. For this purpose, we estimate empirically as a function of γ from the target sample (we use here the real labels but only for this evaluation), i.e. for a given γ, ˆ is the proportion of examples x ∈ T S verifying:

x j ∈R y i y j K(x i , x j ) < γ.

We also assess the distance dH between the two domains by learning a SF-based classifier with K for separating source from target samples in the original space.

From Equation ( 6), a small value, near 0, indicates close domains while a larger value, near 2, indicates a hard DA task.

Synthetic Toy Problem

As the source domain, we consider a classical binary problem with two intertwinning moons, each class corresponding to one moon (see Figure 3). We then define 8 different target domains by rotating anticlockwise the source domain according to 8 angles. higher the angle is, the harder the task becomes. For each domain, we generate 300 instances (150 of each class). Moreover, for studying the influence of the pair set C ST , we evaluate the obtained results when C ST corresponds to a set of "perfect pairs (x s , x t )" where x t is the obtained instance after rotating x s . These results correspond to an upper bound for our methods. Finally, in order to assess the generalization ability of our approach, we evaluate each method on an independent test set of 1500 examples drawn from the target domain (not provided to the algorithm). Each adaptation problem is repeated 10 times and the average accuracy obtained for each method is reported in Table 1. We can make the following remarks.

-Our new regularization term for minimizing distance between marginal distributions improves significantly the performances on the target domain. -As long as the problem can be considered as an easy DA task, the normalized similarity does not produce better models. However, when the difficulty increases, using a normalized similarity improves the results. -Regarding the bipartite matching influence, having perfect pairs leads to the best results and is thus important for the adaption process, which is expected. However, our reverse validation procedure helps us to keep correct results when a set of perfect pairs can not be built.

Figure 2 shows the goodness guarantees of the similarities over each adaptation task. A better similarity has a lower area under the curve, meaning a lower error in average. The ˆ rate is relatively high because we consider only landmarks from the source sample in order to study our adaptation capability. We observe for hardest problems (≥ 50 • ) an improvement of the goodness with the normalized similarity K ST . For easier tasks, this improvement is not significant, justifying the fact that the similarity K can lead to better classifiers. Our normalized similarity seems thus relevant only for hard domain adaptation problems.

Image Classification

In this section, we experiment our approach on PascalVOC 2007 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] and TrecVid 2007 [START_REF] Smeaton | High-Level Feature Detection from Video in TRECVid: a 5-Year Retrospective of Achievements[END_REF] corpora. The PascalVOC benchmark is constituted of a set of 5000 training images and a set of 5000 test images. The TrecVid corpus is constituted of images extracted from videos and can be seen also as an image corpus. The goal is to identify visual objects and scenes in images and videos. We choose the concepts that are shared between the two corpora: Boat, Bus, Car, TV/Monitor, Person and Plane. We used visual features extracted as described in [START_REF] Ayache | Image and video indexing using networks of operators[END_REF]. We consider as the source domain, labeled images from the PascalVOC 2007 training set. For each concept, we generated a source sample constituted of all the training positive images and negatives images independently drawn such that the ratio +/-is 1 3 / 2 3 . As the target domain, we use some images of the TrecVid corpus, we built also a sample containing all the positive examples and drew some negative samples in order to keep the same ration +/-of 1 3 / 2 3 . In these samples, the number of positive examples may be low and we propose to use the F-measure4 to evaluate the learned models. The results are reported in Table 2. The different nature and ways of acquisition of the images make the problem of adaptation difficult. As an illustration, the empirical dH between the two domains is high for every concept. In this context, for all the tasks, the normalized similarity with distance regularization provides the best results. This is confirmed on Figure 4 where the evaluation of the goodness of the two similarities for two concepts is provided: the normalized similarity is better for difficult tasks.

Conclusion

In this paper, we have proposed a preliminary study on the usefulness of the framework of Balcan et al. [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF][START_REF] Balcan | A theory of learning with similarity functions[END_REF] for domain adaptation. We have proposed a normalization of a similarity function according to a test sample based on the fact that a similarity does not need to be PSD or symmetric. We have also proposed a new regularization term that tends to define a projection space of reasonable points where the source and target distributions of the examples are closer. We have provided experiments on a toy problem and on a real image annotation task. Our regularization term generally helps to improve the learned classifier and the normalization proposed seems only relevant for difficult adaptation tasks.

As a future work, we will continue on the idea of normalizing a similarity in order to adapt it to the target domain. Around this idea, many questions remain open like the choice the landmark points, the influence of the test set or avoiding overfitting. The use of some labeled target data may also help to produce a better projection space. From a theoretical standpoint, a perspective would be to consider an extension of the framework of robustness of Xu and Mannor [START_REF] Xu | Robustness and generalization[END_REF] to domain adaptation.

Fig. 1 .

 1 Fig. 1. Intuition behind a successful domain adaptation. Source points are in (dark) green (pos. +, neg. -), target points are in (light) orange. (a) The distance between domains is high: the two samples are easily separable and the classifier learned from source points performs badly on the target sample. (b) The distance between domains is low: The classifier learned from source points performs well on the two domains.

( a )

 a For a 20 • task. (b) For a 30 • task. (c) For a 40 • task. (d) For a 50 • task. (e) For a 60 • task. (f ) For a 70 • task. (g) For a 80 • task. (h) For a 90 • task.

Fig. 2 .

 2 Fig. 2. Goodness of the similarities over the target sample: ˆ as a function of γ.

Fig. 3 .

 3 Fig. 3. Left: A source sample. Right: A target sample with a 50 • rotation.

  (a) For concept Boat (b) For concept Plane.

Fig. 4 .

 4 Fig. 4. ˆ on the target domain as a function of γ for 2 concepts.

Table 1 .

 1 88 ± 13 70 ± 20 59 ± 23 47 ± 17 34 ± 08 23 ± 01 21 ± 01 19 ± 01 with KST 79 ± 10 56 ± 15 56 ± 10 43 ± 09 41 ± 08 37 ± 10 36 ± 10 40 ± 09 SF with distance regularization with K 98 ± 03 92 ± 07 83 ± 05 70 ± 09 54 ± 18 43 ± 24 38 ± 23 35 ± 19 with KST 93 ± 05 86 ± 08 72 ± 12 72 ± 013 69 ± 10 67 ± 12 63 ± 13 58 ± 09 SF with distance regularization and perfect matching with K 99 ± 01 96 ± 01 86 ± 02 73 ± 11 65 ± 23 56 ± 29 47 ± 23 39 ± 19 with KST 97 ± 04 92 ± 06 83 ± 10 75 ± 12 73 ± 16 73 ± 02 69 ± 7 60 ± 11 Average results in percentage of accuracy with standard deviation on the toy problem target test sample for each method.

	Rotation	20 •	30 •	40 •	50 •	60 •	70 •	80 •	90 •
	dH	0.58	1.16	1.31	1.34	1.34	1.32	1.33	1.31
	SF without distance regularization
	with K

Table 2 .

 2 SF without distance regularization with K 0.0279 0.1806 0.5214 0.2477 0.4971 0.5522 0.3378 with KST 0.4731 0.4632 0.5316 0.3664 0.3776 0.5635 0.4626 SF with distance regularization with K 0.2006 0.1739 0.5125 0.2744 0.5037 0.5192 0.3640 with KST 0.4857 0.4891 0.5452 0.3989 0.5353 0.6375 0.5153 Results obtained on TrecVid target domain according to the F-measure.

	Concept boat	bus	car monitor person plane Average
	dH	1.93	1.95	1.85	1.86	1.78	1.86	1.86

The authors consider actually the divergence over H∆H, the space of symmetric difference hypothesis, see[START_REF] Ben-David | A theory of learning from different domains[END_REF] for more details.

By considering the 0-1 loss, L01, defined as follows: L01(h, (x, y)) = 1 if h(x) = y and 0 otherwise.

The F-measure or the balanced F-score is the harmonic mean of precision and recall.

This work was supported in part by the french project VideoSense ANR-09-CORD-026 of the ANR in part by the IST Programme of the European Community, under the PASCAL2 Network of Excellence, IST-2007-216886. This publication only reflects the authors' views.

A Appendix

Given a classifier h, we define the reverse classifier h r as the classifier learned from the target sample self labeled by h : {(x, sign(h(x)))} x∈T S . According to the idea of Zhong et al. [START_REF] Bruzzone | Domain adaptation problems: A DASVM classification technique and a circular validation strategy[END_REF][START_REF] Zhong | Cross validation framework to choose amongst models and datasets for transfer learning[END_REF], we evaluate h r on the source domain (see Fig. 5). Given k-folds on the source labeled sample, we use k-1 folds as labeled examples for solving Pb. ( 9) and we evaluate h r on the last k th fold. The final error corresponds to the mean of the error over the k-folds: ê rr S (h r ) = 1 k k i=1 ê rr LSi (h r ). Among many classifiers h, the one with the lowest ê rr S (h r ) is chosen.


Guillaume Blin
email: gblin@univ-mlv.fr

Paola Bonizzoni
email: bonizzoni@disco.unimib.it

Riccardo Dondi
email: riccardo.dondi@unibg.it

Romeo Rizzi
email: romeo.rizzi@dimi.uniud.it

Florian Sikora
email: sikora@univ-mlv.fr

Complexity Insights of the Minimum Duplication Problem

, where the goal is to find all pre-duplications, that is duplications that precede, in the evolution, the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite problems. First of all, we prove that the Minimum Duplication problem is APX-hard, even when the input consists of five uniquely leaf-labelled gene trees (progressing on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently by a randomized algorithm when the input gene trees have bounded depth.

Introduction

The evolutionary history of the genomes of eukaryotes is the result of a series of evolutionary events, called speciations, that produce new species starting from a common ancestor. This evolutionary history has been deeply studied in Computational Biology, and is usually represented using a special type of phylogenetic tree called species tree [START_REF] Felsenstein | Phylogenies from molecular sequences: Inference and reliability[END_REF]. A species tree is a rooted binary tree whose leaves are uniquely labelled by a set Λ representing the extant species, where the common ancestor of the contemporary species is associated with the root of the tree. The internal nodes represent hypothetical ancestral species (and the associated speciations). Speciations are not the only events that influence the evolution. Indeed, there are other events, such as gene duplication, gene loss and lateral gene transfer that, although not leading to new species, are fundamental in evolution. In this paper, we focus on gene duplications which are known to be essential for the evolution of many eukaryotes groups, such as vertebrates, insects and Fig. 1. (a) a gene tree T . (b) a species tree S where M is the lca mapping from T to S; each gene in {g 2 , g 4 , g 5 } is mapped by function f in the species that gene belongs to. (c) a reconciled tree for T and S based on the a priori duplication of gene g 1 into genes h and g 3 .

plants [START_REF] Eichler | Structural dynamics of eukaryotic chromosome evolution[END_REF]. Gene duplication can be described as the genomic event that causes a gene inside a genome to be copied, resulting in two copies of the same gene that can evolve independently. Genes of extant species are called homologous if they evolved from a common ancestor, through speciations and duplications events [START_REF] Fitch | Homology-a personal view on some of the problems[END_REF]. Evolution of homologous genes, with regards to the extant species, is usually represented using another special type of phylogenetic tree called gene tree. A gene tree is a rooted binary tree whose leaves are (not necessarily uniquely) labelled using elements of the set Λ. Indeed, despite the fact that, biologically speaking, leaves in the gene tree represent genes, for ease, the gene tree is labelled according to the species from which the corresponding gene was sampled. Therefore, leaves similarly labelled represent duplicated genes that evolved independently and appear in a common extant species. As in the species tree, the root and the internal nodes respectively represent the common ancestor and ancestral genes explaining their evolution.

With regards to the set of labels Λ, gene and species trees are said to be comparable. Nevertheless, due to complex evolutionary processes such as gene duplication and loss, comparable gene and species trees very often present incompatibilities. A challenging problem is then to reconcile the gene and species trees with hypothetical gene duplications. For example, in Fig. 1, given two comparable gene and species trees inducing incompatibilities, one can infer a reconciled tree based on the a priori duplication of gene g 1 into genes h and g 3 (h is a hypothetical ancestor of genes g 2 , g 4 ), which afterwards both speciate according to the topology of the species tree. Based on the principle of parsimony, one is interested in finding the minimum number of gene duplications that can explain all the incompatibilities. This last can be inferred by the so-called lowest common ancestor mapping (lca mapping), denoted by M and defined as follows. M maps any gene of the gene tree to the latest species from which the gene could be sampled. In other words, M maps each ancestral gene g of the gene tree to the most recent common ancestor of the extant species from which all the descendant of g were sampled.

For example, in Fig. 1, according to M, g 3 is mapped to S 1 since S 1 is the most recent common ancestor of S 4 and S 5 from which were sampled (represented as a function f ) respectively the descendant g 4 and g 5 of g 3 . Observe that, considering M, any leaf of the gene tree is mapped to the unique leaf of S similarly labelled (according to Λ). Given M, a gene in the gene tree is a gene duplication if it has a descendant with the same M mapping. Then, the reconciliation cost is defined as the number of gene duplications in the gene tree induced by the species tree. Computation of this distance has been widely investigated in the context of the Minimum Duplication problem [START_REF] Stege | Gene Trees and Species Trees: The Gene-Duplication Problem in Fixed-Parameter Tractable[END_REF][START_REF] Ma | From Gene Trees to Species Trees[END_REF][START_REF] Hallett | New algorithms for the duplication-loss model[END_REF][START_REF] Bansal | A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem[END_REF], where given a set of gene trees, the objective is to compute a species tree that induces a minimum number of gene duplications.

The Minimum Duplication problem is known to be NP-hard [START_REF] Ma | From Gene Trees to Species Trees[END_REF]. More recently, the Minimum Duplication problem has been related to the Minimum Triplets Consistency [START_REF] Bansal | A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem[END_REF]. The complexity of Minimum Triplets Consistency has been deeply studied, and the problem is known to be W[2]-hard [START_REF] Byrka | New results on optimizing rooted triplets consistency[END_REF] and inapproximable within factor O(log n) [START_REF] Byrka | New results on optimizing rooted triplets consistency[END_REF]. These results coupled with the reduction provided in [START_REF] Bansal | A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem[END_REF] implies that the Minimum Duplication is NP-hard, W [START_REF] Bansal | Heuristics for the Gene-Duplication Problem: A Θ(n) -Speed-Up for the Local Search[END_REF]-hard (despite of [START_REF] Stege | Gene Trees and Species Trees: The Gene-Duplication Problem in Fixed-Parameter Tractable[END_REF]) and inapproximable within factor O(log n) even in the specific case of a forest composed of an unbounded number of uniquely leaf-labelled gene trees with three leaves [START_REF] Bansal | A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem[END_REF]. Therefore, different heuristics and Integer Linear Programs have been developed [START_REF] Bansal | Heuristics for the Gene-Duplication Problem: A Θ(n) -Speed-Up for the Local Search[END_REF][START_REF] Bansal | The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI-Based Local Searches[END_REF][START_REF] Chauve | New Perspectives on Gene Family Evolution: Losses in Reconciliation and a Link with Supertrees[END_REF][START_REF] Chang | An ILP solution for the gene duplication problem[END_REF]. Recently, the Minimum Duplication Bipartite problem has been introduced to tackle the Minimum Duplication problem [START_REF] Ouangraoua | An Approximation Algorithm for Computing a Parsimonious First Speciation in the Gene Duplication Model[END_REF]. The Minimum Duplication Bipartite problem corresponds to finding all pre-duplications; that is duplications that precede, in the evolution, the first speciation with respect to a species tree. Roughly, this means that only the first level of the species tree is of importance. Indeed, one is interested in knowing if a given species belongs to the subtree of S rooted at the left child of the root or at the right one. Therefore, one can view the species tree as a bipartition (Λ 1 , Λ 2 ) of the set of species Λ. Solving the Minimum Duplication Bipartite problem recursively produces a natural greedy heuristic for the Minimum Duplication problem. The Minimum Duplication Bipartite problem was shown to be 2-approximable [START_REF] Ouangraoua | An Approximation Algorithm for Computing a Parsimonious First Speciation in the Gene Duplication Model[END_REF], but its complexity remains open.

In this contribution, we provide results relying both on the Minimum Duplication problem and the Minimum Duplication Bipartite problem. First of all, we prove that the Minimum Duplication problem is APX-hard, even when the input consists of five uniquely leaf-labeled gene trees (that is for a bounded number of gene trees). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently by a randomized algorithm when the input gene trees have bounded depth. greedy heuristic for the Minimum Duplication problem. Due to space consideration, we do not provide full details and proofs which are deferred to the full version of the paper.

We present a reduction from Minimum Vertex Cover on cubic graphs (MVCC) to the specific case of the Minimum Duplication problem -denoted Min-5-Dup -where given a set of five uniquely leaf labelled gene trees F = {T 1 , T 2 , T 3 , T 4 , T 5 }, the objective is to compute a species tree S that induces a minimum number of gene duplications (afterwards denoted as d(F, S)). Let G = (V G , E G ) be a cubic graph (i.e. every vertex has degree three), MVCC problem asks for a subset V G ⊆ V G , such that for each edge (v i , v j ) ∈ E G , at least one of {v i , v j } belongs to V G . In a first step, starting from any cubic graph G = (V G , E G ), we will construct an associated input F = {T 1 , . . . , T 5 } of Min-5-Dup. Then, we will demonstrate that any species tree S such that d(F, S) < q = 6|E G | + 3|V G | + 1 must be canonical (defined afterwards). Finally, we will prove that our construction is indeed an L-reduction.

In order to define formally the gene trees, let us first define the central notion of comb graph. We will consider a specific subclass of comb graphs corresponding to a binary tree where all the internal nodes lie on a single simple (i.e. with no repeated vertices) path referred as the spine. For ease, we will nevertheless use the term comb graph in the following to denote those last. Given a sequence L = l 1 , . . . , l k of k labels, let C(L) denote the comb graph whose leaves are labelled according to a postorder traversal using L (i.e. l x ∈ L is the label of the unique leaf of depth x). For example, in Fig. 1, the gene tree (a) corresponds to the comb graph C( g 2 , g 4 , g 5 ).

Let us now define two operations on trees. Let T 1 T 2 be a tree obtained from two trees T 1 and T 2 , by connecting the roots of T 1 and T 2 to a new vertex v which becomes the root of T 1 T 2 . Inserting T 2 in the edge e of T 1 will denote the operation that leads to a tree obtained from T 1 and T 2 by replacing the edge e = (v, v ) in T 1 by two edges (v, w) and (w, v ) and connecting the root of T 2 to the new vertex w.

We are now ready to define the gene trees T 1 , . . . , T 5 . Roughly, we will associate to each vertex v ∈ V G , a specific tree T v and to each edge e ∈ E G , two trees T 1 e , T 2 e . These trees will be then combined to build the gene trees T 1 , . . . , T 5 . For ease, let us consider the following order of edges of E G , e 1 , e 2 , . . . e |E G | s.t. ∀e x = (v i , v j ), e y = (v h , v k ) with x < y, i < j and h < k, either (i < h) or (i = h and j < k). According to this order, we define the following three sequences of labels:

M 1 = m 1 1 , m 1 2 , . . . m 1 |E G | , M 2 = m 2 1 , m 2 2 , . . . m 2 |E G | and L = l 1 1 , l 2 1 , l 1 2 , l 2 2 , . . . l 1 |E G | , l 2 |E G | .
Roughly, any edge e x is represented by the four labels {m 1

x , m 2 x , l 1 x , l 2 x }. First of all, for any edge e x ∈ E G , let us build the two trees

T 1 ex = C( l 1 x , m 2 x , l 2
x ) and

T 2 ex = C( l 2 x , m 2 x , l 1
x ). Moreover, for any v ∈ V G s.t. v is incident to the edges e x , e y and e z , we build a tree

T v = C( m 1 x , m 1 y , m 1 z ) C( l 1 x , l 1 y , l 1 z ) C( m 2
x , m 2 y , m 2 z ) (see Fig. 2). We will now build the gene trees T 1 to T 5 by starting from a comb graph where subtrees representing vertices and edges will be inserted in. Let T 5 be obtained from

C( f |V G |+1 , f 1 |V G | , . . . , f q |V G | , f |V G | , . . . f 1 1 , . . . , f q 1 , f 1 )
, by inserting in the edge connecting f 1 and its parent the subtree C(M 1 ) C(M 2 ). Regarding the construction of T 1 to T 4 , let us assume that we are also provided a 4-coloring λ : V G → {1, 2, 3, 4} of G (for example, by applying the polynomial-time greedy Welsh-Powell algorithm [START_REF] Welsh | An upper bound for the chromatic number of a graph and its application to timetabling problems[END_REF]). Let any T i , 1 ≤ i ≤ 4, be first define as a the following comb graph:

T i = C( f 1 , f 2 , . . . , f |V G |+1 , f 1 |V G | , . . . f q |V G | , f 1 |V G |-1 . . . , f q 1
). We then insert, for each v i ∈ V G , the tree T vi in the edge connecting the parents of f i and f i+1 in the gene tree T x where x = λ(v i ) (see Fig. 3). Moreover, for each e x = (v i , v j ) ∈ E G (ordered from e 1 to e |E G | ), the tree T 1 ex is inserted in the edge connecting the parent of f i and its other child in the gene tree T x where x = min{1, 2, 3, 4} \ {λ(v i ), λ(v j )} (i.e. the gene tree having the smallest index and not containing neither T vi , nor T vj ). Finally, for each e x = (v i , v j ) ∈ E G , the tree T 2 ex is inserted in the edge connecting the parent of f i and its other child in the gene tree T x where x = max{1, 2, 3, 4} \ {λ(v i ), λ(v j )} (i.e. the gene tree having the biggest index and not containing neither T vi , nor T vj ). A sketch of this construction is given in Fig. 3.

Due to space constraints, we only provide here a sketch of our proof (full details available in appendix). First of all, we can prove that, by construction, all the gene trees are indeed uniquely leaf-labelled. Then, we can prove that only canonical solutions are of interest. Roughly, a canonical solution (i.e. a species tree S) is a copy of T 5 where extra leaves of L = {l 1

x , l 2

x : ∀e x ∈ E G } are each inserted either in C(M 1 ) or C(M 2 ). The insertion of l 1

x , l 2 x in C(M 1 ) or C(M 2 ) depends on the fact that the edge e x = (v i , v i ) is covered by v i or v j .

We can, moreover, prove that, in a canonical solution, (1) each vertex on the path from the root of T j , with 1 ≤ j ≤ 4, to the parent of

f |V G |+1 (excluding this last) induces a duplication (that is 5|V G | + 2|E G | in total), (2) each edge e x = (v i , v j ) ∈ E G induces a duplication in the root of one of {T 1 ex , T 2
ex } and a duplication in the root of either T vi or T vj . One can then easily see that the minimum number of duplications is then related to the minimum cover size. Hence the following lemma holds.

Lemma 1. Let G = (V G , E G ) be an instance of MVCC and let F = {T 1 , . . . , T 5 } be the corresponding instance of Min-5-Dup. Then, starting from a cover V G of G, we can compute in polynomial time a solution S of Min-5-Dup for F s.t. d(F, S) ≤ 5|V G | + 3|E G | + |V G |; starting from a solution S of Min-5-Dup for F s.t. d(F, S) ≤ 5|V G | + 3|E G | + p, we can compute in polynomial time a cover of G of size at most p.
* f = f 1 |V G | , . . . , f q |V G | , . . . , f 1 1 , . . . , f q 1 and ∀1 ≤ i ≤ 4, λ(v i ) = i.
Lemma 1 concludes the reduction. Since MVCC is APX-hard [START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF], provided our L-reduction, we can conclude that Min-5-Dup is also APX-hard.

Theorem 1. The Minimum Duplication problem is APX-hard, even when the input consists of five uniquely leaf-labelled gene trees

A randomized approach

In this section, we investigate the complexity of the Minimum Duplication Bipartite problem and show that it can be solved efficiently by a randomized algorithm when the input gene trees have bounded depth. A randomized algorithm can be seen simply as an algorithm that is allowed to do some random decisions as it processes the input. Whereas defining a randomized algorithm is quite easy, the performance analysis of this last is more complicated. Indeed, first, one has to compute the probability of success of the randomized algorithm (i.e. probability to end up with an optimal solution). Then, one can amplify the probability of success simply by repeatedly running the algorithm, with independent random choices, and taking the best solution found. If one, moreover, prove that the overall running time required to get a high probability of success is polynomial in the size of the input, then it implies that the problem is randomized polynomial (in RP-class). For further details on randomized algorithms, the reader should consider the book of Kleinberg and Tardos [START_REF] Kleinberg | Algorithm Design[END_REF].

In order to prove that the Minimum Duplication Bipartite problem is randomized polynomial, we first provide a randomized algorithm for a variant of the Minimum Cut problem, called Minimum Cut in Colored Graph. Then, we will prove that the Minimum Duplication Bipartite problem can be translated into a Minimum Cut in Colored Hypergraph problem that can be solved efficiently applying our randomized algorithm on hypergraphs with bounded hyperedges degree. It is of importance to note that, as far as we know, this is the first attempt of solving by randomization the minimum cut in colored hypergraph. Providing a randomized algorithm for general hypergaphs with unbounded hyperedges degree is still open.

Let us first introduce the Minimum Cut in Colored Graph problem: Given a set of colors C and an undirected colored graph G = (V, E) where any edge is colored with a color from C, find a minimal colored cut of G -that is a partition of V into two non-empty sets A and B such that the number of colors used by the edges having one end in A and the other in B is minimized.

For ease, let col : E → C be a function returning the color of a given edge and mul(c) = |{e : e ∈ E and col(e) = c}| be a function returning the multiplicity of a given color. Moreover, for sake, given a graph G = (V, E), let col(G) = e∈E col(e) denote the set of colors used in G. Let us now describe an algorithm inspired by the folklore Contraction Algorithm [START_REF] Kleinberg | Algorithm Design[END_REF] used for solving the classical Minimum Cut problem (i.e. minimizing the number of edges having one end in A and the other in B) on uncolored graph by randomized algorithm.

As in [START_REF] Kleinberg | Algorithm Design[END_REF], our Colored Contraction Algorithm uses a connected multigraph G = (V, E) -that is an undirected graph that is allowed to have more then one edge between the same pair of vertices -which is moreover colored. The algorithm starts by choosing, uniformly at random, a color c ∈ col(G) and contracting any edge e ∈ E such that col(e) = c (and thus all such edges). Contracting an edge (u, v) ∈ E will produce a new graph G = (V , E ) in which u and v are identified as a single new vertex w whereas all other vertices are keeping their original identity (i.e.

V = {V ∪ {w}} \ {u, v}). In G , E = {E ∪ {(w, v ) : v ∈ {u, v}, (v , v ) ∈ E}} \ {(v , v ) : v ∈ {u, v}, v ∈ V }.
Roughly, E is a copy of E where any edge (u, v) has been removed whereas any other edge has been preserved, but if one of its ends was equal to u or v, then this end is updated to be equal to the new node w. Note that the contraction operation may end up in a multigraph even when starting from a classical graph G. In this process, contracting all the edges that have the selected color c roughly corresponds to a sequence of mul(c) contractions, each reducing the number of vertices by one. Colored Contraction Algorithm then continues recursively on G , by choosing, uniformly at random, a color c ∈ col(G ) and contracting any edge e ∈ E such that col(e) = c. As these recursive calls proceed, the vertices of V should be viewed as supervertices: each supervertex w corresponds to the subset S(w) ⊆ V that has been "swallowed up" in the contractions that produced w. The algorithm ends when it reaches a graph G with only two super-vertices v A and v B . We output (A = S(v A ), B = S(v B )) as the colored-cut found by the algorithm.

Let us now analyze the performance of the Colored Contraction Algorithm -which cannot be derived directly from the one of the original Contraction Algorithm. Since the algorithm is making random choices, there is some probability that it will succeed in finding a minimum colored-cut (and some probability that it would not). In order to prove that this algorithm is worthwhile, we will prove that the probability of success is only polynomially small; inducing that, by running the algorithm a polynomial number of times and returning the best colored-cut found in any run, one would be able to produce an optimal colored-cut with high probability.

Theorem 2. The Colored Contraction Algorithm returns an optimal colored-cut G with probability at least

(|V | 2k ) -1 where k = max c∈C mul(c)
Proof. Let us assume that the optimal minimum colored-cut (A, B) of G is of size opt; that is the set of edges having one end in A and the other end in B (referred afterwards as the cut-set) is colored using opt colors of C. Note that unlike the classical minimum cut problem, the goal here is to minimize the number of colors in the cut-set itself. Moreover, let

G opt = G[A ∪ B, {(u, v) : (u, v) ∈ E and u ∈ A, v ∈ B}]
corresponds to the bipartite graph representing the cut-set of (A, B). In order to compute a lower bound on the probability that the Colored Contraction Algorithm returns the minimum colored-cut (A, B), we first notice some important properties.

First, remark that any vertex v ∈ V cannot have a degree less than opt. Indeed, otherwise, ({v}, V \ {v}) would correspond to a colored-cut inducing at most opt -1 colors, contradicting our hypothesis that (A, B) is an optimal minimum colored-cut of G. Therefore, any vertex of G is of degree at least opt; inducing the following lower bound on E: |E| ≥ opt|V |

2

. We know moreover that, since each color of C can be used at most k = max c∈C mul(c) times in E, we have that |E| ≤ k • |C|. This leads to the following inequalities.

|V | • opt ≤ 2 • |E| ≤ 2k • |C| (1)
Let us now evaluate the probability P r[F j ] that the Colored Contraction Algorithm fails at the j th step of the recursion (that is when already j -1 contractions have been done). Considering what could go wrong in the j th step of the Colored Contraction Algorithm, one can check that the unique issue would be that the uniformly at random choice of a color c unfortunately select one color of the set of opt colors used by the cut-set -which will be then contracted inducing that the algorithm would not be able to find the optimal colored-cut (A, B) since at least a node of A and a node of B would be both contracted into the same supervertex. Hence the probability that an edge of the current graph G is both in the optima cut-set and contracted is at most opt |C | , since there are at most opt edges to be chosen among |C | edges, where C = col(G ). According to Inequality 1, considering that the graph at j th step is G and

C = col(G ) P r[F j ] ≤ opt |C | ≤ 2k • |C | |V | • |C | = 2k |V | (2)
The colored-cut (A, B) will actually be returned by the algorithm if no edge of the cut-set is contracted in any of the at most |V | -2 iterations. If we write S j for the event that an edge of the cut-set has not been contracted until the j th step, then, according to Inequality 2, P r

[S j ] ≥ 1 -P r[F j ] = 1 -2k
|V | where the graph at j th step is G = (V , E ). For ease, let us consider the sequence of color choices as being S c = (c 1 , c 2 . . .) and λ j = i<j and ci∈Sc mul(c i ). On the whole the probability that the Colored Contraction Algorithm returns the optimal colored-cut (A, B) is thus at least

P r[Success] ≥ λ1-1 i=0 (1 - 2k |V | -i ) • λ3-1 i=λ2 (1 - 2k |V | -i
) . . .

λ |Sc | -1 i=λ |Sc |-1 (1 - 2k |V | -i ) (3) ≥ λ1-1 i=0 ( |V | -i -2k |V | -i ) • λ3-1 i=λ2 ( |V | -i -2k |V | -i ) . . . λ |Sc | -1 i=λ |Sc |-1 ( |V | -i -2k |V | -i ) (4)
≥

λ |Sc | -1 i=0 ( |V | -i -2k |V | -i ) = |V | -2k |V | . . . |V | -2k -2k |V | -2k . . . |V | -(λ |Sc| -1) -2k ( ( ( ( ( ( ( ( |V | -(λ |Sc| -1) (5)
≥

λ |Sc | -1 i=2k |V | -i -2k 2k-1 i=0 |V | -i ≥ 1 |V | 2k = (|V | 2k ) -1 (6)
Then according to Theorem 2, we know that a single run of the Colored Contraction Algorithm fails to find an optimal colored-cut with probability at most (1 -(|V | 2k ) -1 ). One can then amplify the probability of success simply by repeatedly running the algorithm, with independent random choices, and taking the best colored-cut found. It is known that the function (1 -n -1 ) n converges monotonically from 1 4 up to 1 e as n increases from 2 [START_REF] Kleinberg | Algorithm Design[END_REF]. Thus, if we run the algorithm |V | 2k times, then the probability that we fail to find an optimal colored-cut in any run is at most (1 Proof. In the following, for ease, given a binary tree T = (V, E) and a vertex v ∈ V , let us denote by v L (resp. v R ) the left (resp. right) child of v and by ζ v the cluster of v i.e. the set of all leaves belonging to the subtree rooted in v. Moreover, for ease, ϑ T will denote the root of the tree T . Given a gene tree forest F = {T 1 = (V 1 , E 1 ), T 2 = (V 2 , E 2 ), . . .} built on Λ, considering the definition of the Minimum Duplication Bipartite problem, one wants to define a bipartition (Λ 1 , Λ 2 ) of Λ = Ti∈F V i inducing the minimum number of pre-duplications. In T i , a node v of V i is a duplication with respect to (Λ

-(|V | 2k ) -1 ) |V | 2k ≤ 1 e . As
1 , Λ 2 ), if ∃v ∈ {v L , v R }, such that (Λ 1 ζ v = ∅) ∧ (Λ 2 ζ v = ∅) is true.
In other words, v is a duplication if for one of its children -say v -ζ v contains two leaves not belonging to the same part of the bipartition (Λ 1 , Λ 2 ). Given F and a set of colors C, we define the following colored hypergraph G F = (V, E) associated to F. Let V = Λ = T ∈F ζ ϑ T and there are two hyperedges, for any node v k of the tree T i ,

α i k = {ζ v L k : |ζ v L k | ≥ 2} and β i k = {ζ v R k : |ζ v R k | ≥ 2} colored with color col(α i k ) = col(β i k ) = c i k ∈ C in E.
An illustration of such construction is provided in Fig. 4. Then in G F , a colored-cut of size k corresponds to a bipartition of the set Λ inducing k duplications. Indeed, if the hyperedge α i k (resp. β i k ) belongs to the cut-set, then it induces a duplication for the corresponding vertex v k in T i since there exist at least two leaves in

ζ v L k (resp. ζ v R k ) belonging to different parts of the bipartition (Λ 1 , Λ 2 ).
Thus, if one can find a minimum colored-cut in such hypergraphs, then one would be able to solve in polynomial time the Minimum Duplication Bipartite problem. Just consider the Colored Contraction Algorithm presented previously in this section. From any colored hypergraph G F = (V, E), one may build a colored graph G = (V, E ) where any hyperedge e = {v i1 , v i2 . . . v ik } colored with color c = col(e) has been replaced by a path v i1 , v i2 . . . v ik colored with c in E (i.e. E = {(v ik , v ik+1 ) : v ik ∈ e, e ∈ E}). Notice that an edge e ∈ E colored with c is cut if and only if an hyperedge colored c of G F is cut. Once this colored graph has been obtained, one may apply the Colored Contraction Algorithm which will produce a minimum colored-cut of G which also induces a minimum colored cut in G F . Since this algorithm has a complexity exponential in the maximum multiplicity of any color of the considered graph, when the size of each hyperedge is bounded, so does the multiplicity of any color since the maximal size of an hyperedge corresponds to the maximal depth of the input gene trees: leading to a randomized polynomial solution for the Minimum Duplication Bipartite problem.

Conclusion

In this paper we have investigated the complexity of two variants of the Minimum Duplication problem. We have proved that the Minimum Duplication problem is APX-hard, even when the input consists of five uniquely leaf-labelled gene trees. Then, we have shown that the Minimum Duplication Bipartite problem can be solved efficiently by a randomized algorithm when the input gene trees have bounded depth.

A natural open problem is the complexity of the Minimum Duplication Bipartite problem when the gene trees have unbounded depth. Furthermore, it would be interesting to deepen the analysis on the complexity of the Minimum Duplication problem, when the input consists of less than five uniquely leaflabelled gene trees.

5 Appendix -Detailed proof of APX-hardness

Extra notations

Given a binary tree T = (V, E), with leaves labelled by Λ and Λ ⊆ Λ, we define the restriction of T to Λ , denoted T |Λ , as the subtree obtained from T by retaining only leaves with a label belonging to Λ and by contracting all the internal vertices of degree 2. For ease, we will note lca T (u, v) the lowest common ancestor of two nodes u and v in a tree T .

For ease, in the following, we will consider that n = |V G | and m = |E G |. Let us define the following ordered sequences of labels:

-L f = f n+1 , f 1 n , . . . , f q n , f n , . . . f 1 1 , . . . , f q 1 , f 1 ; -L * f = f 1 n , . . . , f q n , . . . , f 1 1 , . . . , f q 1 ; -L f = f n+1 , f n , . . . , f 1 . -L i f = f 1 i , .
. . , f q i , with 1 ≤ i ≤ n. Moreover, let P x be the set of internal vertices in T x , 1 ≤ x ≤ 4, belonging to the path from the root of T x to the parent p x n+1 of f n+1 . We define the spine of any gene tree T x , 1 ≤ x ≤ 4, as P x \ {p x n+1 }. Recall that given a gene tree T and a species tree S, a vertex v of T is duplicated with respect to S if M(v) = M(v ) where v is a descendant of v in T (i.e. v belongs to T v ).

Preliminary properties

Let us introduce some fundamental properties that will be used in the rest of this appendix. Property 3. Let T = (V T , E T ) be a gene tree and S = (V S , E S ) be a species tree. Let v be a vertex of V T such that v has at least one child v , which is not a leaf. If there exists a vertex w of V S such that (a)

ζ v \ ζ v ⊆ ζ w , (b) ζ w ⊇ ζ v and (c) ζ w ∩ ζ v = ∅, then v is duplicated.

Missing proofs

First of all, let us prove that, by construction, all the gene trees T 1 , . . . , T 5 are uniquely leaf-labelled.

Lemma 2. The trees T 1 , . . . , T 5 are uniquely leaf-labelled trees.

Proof. It is easy to see that T 5 is uniquely leaf-labelled by construction. Indeed, each of the three comb graphs C(L f ), C(M 1 ), C(M 2 ) used to build T 5 is uniquely leaf-labelled. Moreover, the trees C(L f ), C(M 1 ), C(M 2 ) have pairwise disjoint sets of leaves. Now consider the gene trees T 1 , T 2 , T 3 and T 4 . First, remark that any tree T v with v ∈ V G is uniquely leaf-labelled and so do the trees T 1 ex and T 2 ex . Then, one has only to pay attention to their relative placement in the gene trees. More precisely, by construction, one has to be sure that a tree T v where v ∈ V G is incident to edges e x = (v, v ), e y = (v, v ) and e z = (v, v ) does not belong to the same gene tree than none of {T v , T v , T v } and none of {T 1 ex , T 2 ex , T 1 ey , T 2 ey , T 1 ez , T 2 ez }. This is indeed true since all those trees are associated to the gene trees considering their corresponding color in the 4-coloring of G. One has also to be sure that the trees T 1 ex and T 2 ex do not belong to the same gene tree (which is the case by construction). Fig. 6. Illustration of Lemma 3 when for each

f z i ∈ L i f , lca S (f i , f z i ) > lca S (f i+1 , f z i ).
Let us now prove that only canonical solutions are of interest. Remind that a canonical solution (i.e. a species tree S) is a copy of T 5 where extra leaves of L = {l 1

x , l 2

x : ∀e x ∈ E G } are each inserted either in C(M 1 ) or C(M 2 ). More formally, a species tree S is canonical if and only if S|(M 1 ∪M 2 ∪L f ) is isomorphic to T 5 and any label in ζ S \ ζ T5 belongs to ζ v where v is the other child of the parent of f 1 in S.

First, let us consider the following order induced by the lca mapping M. Consider three vertices v, v , v of a tree T and the following ordering of their lowest common ancestors: we write lca T (v, v ) > lca T (v , v ) when the depth of the lca of v , v is greater than the one of v, v . We will moreover note lca T (v, v ) ≥ lca T (v , v ) or lca T (v , v ) ≥ lca T (v, v ) when the depth of the lca of v, v and the lca of v , v is equal. Lemma 3. Let S be a solution of Min-5-Dup for the instance F = {T 1 , . . . , T 5 }. Then, either d(F, S) ≥ 6n + 3m + 1 or all the vertices on the spines of the gene trees T 1 , T 2 , T 3 , T 4 are duplicated.

Proof. Consider any species tree S and two leaves f i , f i+1 of T 5 , for a given 1 ≤ i < n + 1. Let w j i (resp. w j i+1 ) be the parent of f i (resp. f i+1 ) in the gene tree T j , with j ∈ {1, 2, 3, 4}. Let x i (resp. x i+1 ) denote the parent in T 5 of f i (resp. f i+1 ). Moreover, let y 1 (resp. y 2 ) be the vertices in S mapped, according to the lca mapping M, with x i (resp.

x i+1 ) -i.e. M(x i ) = y 1 (resp. M(x i+1 ) = y 2 ).
In what follows, we consider a label f z i , with 1 ≤ z ≤ q, and prove that, considering the previously mentioned mapping, either all the internal vertices on the path from x i to x i+1 in T 5 are duplicated (hence d(F, S) ≥ q = 6n + 3m + 1) or all the internal vertices on the path from w j i (included) to w j i+1 (not included) are duplicated in T j , 1 ≤ j ≤ 4. To do so, we will consider a case by case analysis based on the possible mappings of f i , f i+1 and f z i in S. Assume that for each

f z i ∈ L i f , lca S (f i , f z i ) ≥ lca S (f i+1 , f z i ). Notice that there exists two possible cases: lca S (f i , f z i ) > lca S (f i+1 , f z i ), for each f z i , or
there exists at least one

f z i such that lca S (f i , f z i ) > lca S (f i+1 , f i ). If lca S (f i , f z i ) > lca S (f i+1 , f z i ),
for each f z i , then Property 3 applies to each internal vertex between x i , x i+1 . Indeed for each internal vertex between x i , x i+1 , there exists a vertex between lca S (f i , f z i ) and lca S (f i+1 , f z i ) such that Property 3 applies, as the cluster of each of the latter vertices does not contain f i (see Figure 6). Hence d(F, S) ≥ q = 6n + 3m + 1. Now assume that for some f i z , lca S (f i , f z i ) > lca S (f i+1 , f i ). Let us consider the leaves in ζ w x i \ζ w x i+1 and let S x i be the set of internal vertices of T x between w x i+1 and w x i . Property 3 applies to the vertex w x i , as lca S (f i+1 , f i ) contains f i , f i+1 but not f z i , which is contained in both ζ w x i+1 and ζ w x i . Hence w x i is duplicated. Now, consider the lowest vertex s x i ∈ S x i not duplicated and denote by t x i its child which is not on the spine of T x , 1 ≤ x ≤ 4. Let z 1 be the vertex of S where s x i is mapped (i.e. M(s x i ) = z 1 ), and notice that z 1 ≥ lca S (f z i , f i ). Since s x i is not duplicated, then the cluster of one of the children of z 1 contains ζ t x i , while the other contains {f z i , f i , f i+1 }, for each 1 ≤ z ≤ q. But then, since m 1

x , m 2 x ∈ ζ s x i , it follows that for each internal node between x i , x i+1 , there exists a vertex between lca T (f i , f z i ) and z 1 such that Property 3 applies, as the cluster of each of the latter vertices does not contain m 2

x , while the cluster of each vertex between x i and x i+1 contains a label m 2 x . Hence d(F, S) ≥ 6n + 3m + 1. Now, let us consider the case lca S (f i , f z i ) < lca S (f i+1 , f z i ). It follows by Property 3 that the internal vertices of S x i and w x i are all mapped in a vertex z 1 , hence inducing a duplication in w x i . Indeed,

ζ w x i = ζ s x i \ {f i }, while lca T (f i , f z i ) contains f i , but not f i+1 .
Now consider the lowest vertex s x i ∈ S x i that is not duplicated. Then the cluster of one of the children of z 1 (the vertex where s x i and w x i are mapped) contains ζ s x i , while the other contains {f z i , f i , f i+1 }, for each 1 ≤ z ≤ q. Since m 2 x ∈ ζ s x i , it follows that for each internal node between x i , x i+1 , there exists a vertex between lca S (f i , f z i ) and z 1 such that Property 3 applies, as the cluster of each of the latter vertices does not contain m 2

x , while the cluster of each vertex between x i and x i+1 contains m 2

x . Hence d(F, S) ≥ 6n + 3m + 1. Since we have shown that for each pair of leaves f i , f i+1 , either d(F, S) ≥ 6n + 3m + 1, or all the internal nodes between w x i (included) and w x i+1 (not included) are duplicated, it follows that we have proved the lemma.

While in the previous lemma we have focused on the duplications induced on vertices of the spine of the gene trees T 1 , . . . , T 4 , in what follows, we will focus on the duplications induced in the subtrees representing the vertices and edges (i.e. T v , T x e ). Proof. It follows from Property 1 that the root of at least one of T 1 ex , T 2 ex is duplicated with respect to S since both T 1 ex , T 2 ex are labelled by the same set of leaves and they are not isomorphic. Now, let us prove the second part of the lemma. We have shown that any species tree induces a duplication in the root of at least one of T 1 ex , T 2 ex . Let us consider a species tree S. If S induces a duplication in the roots of both T 1 ex and T 2 ex , then the lemma holds. Hence assume that S induces a duplication in exactly one of T 1 ex , T 2 ex , w.l.o.g. T 1 ex . Thus, assume that S does not induce a duplication in the root of T 2 ex . Let us define L x = {m 1

x , m 2 x , l 1 x , l 2 x } and consider the following restrictions of T vi and T vj : T vi |L x , T vj |L x . The roots of both T vi |L x and T vj |L x induce the following bipartitions B(v i ) = ({m 1

x , l 1 x }; {m 2 x }) and B(v j ) = ({m 1 x , l 2 x }; {m 2 x }). Let v be the vertex of S, which is the lowest common ancestor of {m 2

x , l 1 x , l 2 x }. Since we have assumed that the root of T 2 ex is not duplicated, it follows that the subtree rooted at v restricted to {m 2

x , l 1 x , l 2 x } must induce the bipartition ({m 2

x , l 1 x }; {l 2 x }). Now assume that both the root of T vi and the root of T vj are mapped to v and consider where the leaf m 1

x is possibly placed in a the subtree rooted in v. If m 1

x is clustered with l 2 x , then the root of T vj is duplicated, as bipartition B(v j ) = ({m 1

x , l 2 x }; {m 2 x }). If m 1

x is clustered with l 1 x and m 2 x , then the root of T vi is duplicated, as bipartition B(v i ) = ({m 1

x , l 1 x }; {m 2 x }). Assume now that the root of T vi or the root of T vj , w.l.o.g. ϑ Tv i , is not mapped to v. Then, both the root of T vi and at least one of its children are mapped to an ancestor of v. Let y be the ancestor of v to which ϑ Tv i is mapped. The clusters of both children of y contain a leaf of ζ ϑ Tv i

. More precisely, the cluster of the child z of y that is on the path from v to y will contain the leaf set {m 1

x , l 1 x , m 2 x }, as so does the ζ v . Hence, one of the children of ϑ Tv i , w.l.o.g. ϑ L T (Vi) , has a cluster not included in ζ z but sharing some elements with ζ z . This implies that ϑ L T (Vi) is mapped in y, thus a duplication occurs in the root of T vi . Let us now consider canonical solution and prove the following lemma. Proof. Let S be a solution of Min-5-Dup over instance T 1 , . . . , T 5 . If S induces at least 6n + 3m + 1 duplications, since a canonical solution induces at most 5n + 3m + p duplications, where p ≤ n, it follows that for any canonical solution S * that satisfies properties (1) and (2) of the lemma, d(F, S * ) ≤ d(F, S). Indeed in a canonical solution S * , there are 5n + 2m duplications on the spines of the gene trees T 1 , T 2 , T 3 , T 4 , plus m duplications in the root of either T 1 ex or T 2 ex , for any e x ∈ E G and p duplications in the roots of any subtree T vi , for any v i ∈ V G .

Hence, assume that S induces less than 6n+3m+1 duplications. By Lemma 3, it follows that S induces a duplication in all the the vertices on the spine of each gene tree T i , 1 ≤ i ≤ 4. Now, consider the set R of clusters associated with the roots of subtrees T 1 ex , T 2 ex , T vi , T vj and define two subsets of R as follows: Saf e(S) = {x ∈ R : x is not duplicated in S}, Dup(S) = R \ Saf e(S). Now let us compute a canonical solution S * . First, starting from Saf e(S) and Dup(S), let us compute two sets Saf e(S * ) and Dup(S * ) as follows. Notice that by Lemma 4, at least one of the roots of T 1 ex , T 2 ex is duplicated. We assume w.l.o.g. that if the cluster of ϑ Tv i (resp. of ϑ Tv j ) is in Dup(S), then the cluster of ϑ T 1 ex (resp. of ϑ T 2 ex ) is in Dup(S). Notice that, if the clusters of both ϑ T 1 ex , ϑ T 2 ex are in Dup(S), then we can assign one of these two clusters to Saf e(S) and eventually one of ϑ Tv i , ϑ Tv j to Dup(S), without improving the size of Dup(S). Now, define Saf e(S * ) = Saf e(S) and Dup(S * ) = Dup(S).

Let S be a tree isomorphic to T 5 . Then starting from S we construct a solution S * of Min-5-Dup as follows. Let us consider the subtree of S having as leaf set M 1 ∪ M 2 . Let r be the root of this subtree, and let r i , 1 ≤ i ≤ 2, be the root of C(M i ) in S .

First, let us assign the elements of L = l 1 1 , l x (resp. l 2 x ) to L 1 . If the cluster of ϑ Tv i belongs to Saf e(S * ), then assign l 1

x , l 1 y , l 1 z to L 1 where v i is incident to the edges e x , e y and e z . All the other leaves in L are assigned to L 2 . Then a subtree C(L 1 ) is inserted in the edge {r , r 1 }. The subtree C(M 2 ) is substituted with a subtree C(M 2 ∪ L 2 ), where the order on M 2 ∪ L 2 is induced by the order on the corresponding edges and that l 1

x < m 2

x . Now, we claim that the tree S * induces at most Dup(S * ) duplications, for the trees T 1 ex , T 2 ex , T vi , T vj . Indeed, assume that T 1 ex is in Saf e(S * ). Then, since at most one of l 1

x , l 2

x is assigned to L 1 , at least one of l 1 x and l 2

x is assigned to L 2 . It follows that the root of T 1 ex is not duplicated (a similar proof holds for T 2 ex ). Now consider a subtree T vi in Saf e(S * ). As l 1

x , m 1 x are assigned to L 1 , and as m 2

x is assigned to L 2 , it follows that the root of T vi is not duplicated. Since the other vertices are arranged following the order on L, it follows that no duplication is induced in any internal vertex of T vi . Now consider a subtree T vi in Dup(S * ). By construction, the subtrees of T vi |M 1 and T vi |M 2 do not have duplications. Furthermore, as all the leaves l 1

x , l 1 y , l 1 z (related to v i ) are assigned to L 2 , it follows that also the vertices in the restriction T vi |{l 1

x , l 1 y , l 1 z } are not duplicated. Finally, the vertex of T vi associated with clusters {m 1

x , m 1 y , m 1 z , l 1 x , l 1 y , l 1 z } is mapped to r , hence it is not duplicated as its children are not mapped to r . Now, consider the other vertices of T 1 , T 2 , T 3 , T 4 not yet considered. Since by construction, the only other vertices of T 1 , T 2 , T 3 , T 4 that are duplicated with respect to S * are those vertices in the spines of the gene trees T 1 , T 2 , T 3 , T 4 , the correctness of the lemma follows.

We are now ready to prove the main lemma; that is that our reduction is an L-reduction. Proof. Given a cover V G of G = (V G , E G ), define a solution S to Min-5-Dup as follows. The construction follows that of Lemma 5, by assigning T vi to Saf e(S) if v i / ∈ V . Let us consider a species tree S inducing at most 5n + 3m + p duplications. By Lemma 5, it follows that starting from S, we can compute in polynomial time a canonical solution S * of Min-5-Dup over instance F = {T 1 , . . . , T 5 }, inducing 5n + 3m + p duplications, with p ≤ p. Since S * is a canonical solution, we can assume that there exists exactly p duplications induced by S * in the subtrees {T vi : v i ∈ V G }. By Lemma 5, for each edge {v i , v j } ∈ E G , at least one of the subtrees from {T vi , T vj } has a duplication in its root. Hence, the set of vertices V ⊆ V corresponding to those trees in {T vi : v i ∈ V G } having a duplication in their root forms a cover of G. Since |V | = p ≤ p, it follows that the lemma holds.

Fig. 2 .

 2 Fig. 2. The trees T v , T 1 ex and T 2 ex for v ∈ V G incident to the edges e x , e y and e z .

Fig. 3 .

 3 Fig. 3. Gene trees T 1 to T 5 obtained from the cubic graph G where L* f = f 1 |V G | , . . . , f q |V G | , . . . , f 1 1 , . . . , f q 1 and ∀1 ≤ i ≤ 4, λ(v i ) = i.

Fig. 4 .

 4 Fig. 4. Illustration of the construction of G F and G given F = (T 1 , T 2 ). Considering the minimum colored-cut {1, 2, 3, 4, 5}, {6, 7, 8, 9} of size 1, the only induced duplication is represented as a star on T 1 .

Property 1 .

 1 Let T , T be two gene trees labelled by the same sets of leaves Λ.Consider the bipartitions b1 = (ζ ϑ L T , ζ ϑ R T ), b 2 = (ζ ϑ L T , ζ ϑ R T ) of Λ.Then either b 1 and b 2 are identical or any species tree S induces at least one duplication in the root of one of {T, T }. Property 2. Let T be a gene tree and S be a species tree labelled by the same sets of leaves Λ. Then either T and S are isomorphic or d(T, S) ≥ 1.Proof. Let us prove this lemma by induction. By hypothesis, let T and S be two trees not isomorphic. If both T and S have depth 2, it is easy to check that d(T, S) ≥ 1. Assume now that T and S have depth larger than 2. Then at least one of the following statements holds: (a) T |ζ ϑ L T and S|ζ ϑ L S are not isomorphic or (b) T |ζ ϑ R T and S|ζ ϑ L S are not isomorphic or (c) T |ζ ϑ R T and S|ζ ϑ L S are not isomorphic or (d) T |ζ ϑ R T and S|ζ ϑ R S are not isomorphic. Then, by induction, d(T, S) ≥ 1.

Fig. 5 .

 5 Fig. 5. Illustration of Property 3 where (a) ζ v \ ζ v ⊆ ζ w , (b) ζ w ⊇ ζ v and (c) ζ w ∩ ζ v = ∅.

Lemma 4 .

 4 Let S be a solution of Min-5-Dup over instance F = {T 1 , . . . , T 5 } and let T 1 ex , T 2 ex , T vi , T vj be four subtrees of T 1 , . . . , T 4 , s.t. e x = (v i , v j ) ∈ E G . Then (1) the root of at least one of T 1 ex , T 2 ex is duplicated with respect to S; (2) the roots of at least two of T 1 ex , T 2 ex , T vi , T vj are duplicated with respect to S.

Lemma 5 .

 5 Let S be a solution of Min-5-Dup over instance F = {T 1 , . . . , T 5 }. Then, we can compute in polynomial time a canonical solution S * of Min-5-Dup over instance F, such that d(F, S * ) ≤ d(F, S), and such that for each e x = (v i , v j ) ∈ E G and the corresponding subtrees T 1 ex , T 2 ex , T vi , T vj of T 1 , T 2 , T 3 , T 4 : (1) the root of exactly one of T 1 ex , T 2 ex is duplicated with respect to S * ; (2) the root of at least one of T vi , T vj is duplicated with respect to S * .

Lemma 6 .

 6 Let G = (V G , E G ) be an instance of MVCC and let F = {T 1 , . . . , T 5 } be the corresponding instance of Min-5-Dup. Then, starting from a cover V G of G, we can compute in polynomial time a solution of Min-5-Dup over instance F = {T 1 , . . . , T 5 } such that d(F, S) ≤ 5n + 3m + |V G |. Moreover, starting from a solution S to Min-5-Dup over instance F = {T 1 , . . . , T 5 } such that d(F, S) ≤ 5n + 3m + p, we can compute in polynomial time a cover of G of size at most p.

  2 1 , l 1 2 , l 2 2 , . . . l 1 |E G | , l 2 |E G | to two sets L 1 , L 2 as follows. If the cluster of ϑ T 1 ex (resp. ϑ T 2 ex ) belongs to Saf e(S * ), then assign the leaves l 1