Cédric Bentz
email: cedric.bentz@cnam.fr

Pierre Le Bodic

Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth

Keywords:

Introduction

Cut problems in graphs are known to have strong links with many other combinatorial problems [START_REF] Shmoys | Cut problems and their application to divideand-conquer, chapter 5[END_REF], and are a relevant framework for modeling various real-life problems. In particular, many reliability network problems can be reduced to several kinds of cut problems: the failure of a node or a link of the telecommunication network corresponds to the removal of the associated vertex or edge in the graph that represents it.

In the classical Multicut problem (MC), we are given a connected (un)directed graph G = (V, E) with n = |V | vertices, a set S ⊆ V 2 of pairs of terminals, a weight function w : E → Z + , and we ask for a set of edges E * ⊆ E of minimum weight e∈E * w(e) that disconnects all pairs of terminals, i.e., such that in (V, E\E * ) there remains no path from the first terminal (source) to the second one (sink) of each pair in S.

MC is known to be equivalent to the Vertex Cover problem in stars with unit weights [START_REF] Garg | Primaldual approximation algorithms for integral flow and multicut in trees[END_REF], and hence it is APXhard even in trees. However, if |S| is fixed, then MC is tractable in bounded-treewidth graphs [START_REF] Bentz | On the complexity of the multicut problem in bounded tree-width graphs and digraphs[END_REF][START_REF] Guo | Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs[END_REF], and in planar graphs [START_REF] Bentz | A polynomial-time algorithm for planar multicuts with few source-sink pairs[END_REF][START_REF] Colin De Verdière | Multicuts in planar and boundedgenus graphs with bounded number of terminals[END_REF]. In other recent articles, MC have been proved to be FPT w.r.t. the solution size [START_REF] Bousquet | Multicut is FPT[END_REF][START_REF] Marx | Fixed-parameter tractability of multicut parameterized by the size of the cutset[END_REF].

We also have to mention that MC with unit weights is APX-hard in unrestricted graphs, even if |S| = 3 [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF], and that a few interesting special cases have been proved to be tractable: paths (and more generally directed trees) [START_REF] Costa | Erratum to "Minimal multicut and maximal integer multiflow: A survey[END_REF], rings [START_REF] Bentz | Multicuts and integral multiflows in rings[END_REF], and undirected graphs when |S| = 2 [START_REF] Yannakakis | Cutting and partitioning a graph after a fixed pattern[END_REF]. In directed graphs, however, MC becomes APX-hard when |S| = 2, even in acyclic graphs where the maximum degree is bounded and weights are unitary [START_REF] Bentz | On the hardness of finding near-optimal multicuts in directed acyclic graphs[END_REF]. In [START_REF] Gottlob | A logical approach to multicut problems[END_REF], the parameter tw(G + H), which is the treewidth of the graph G + H (the notion of treewidth will be defined properly at the end of this section), is introduced, where H = (V H , E H ) is the support graph of S (or demand graph), i.e. V H is the set of terminals of G, and any two vertices u, v ∈ V H are connected by an edge iff (u, v) ∈ S. The authors prove that MC can be expressed using monadic second order logic, and, as such, using Courcelle's theorem [START_REF] Courcelle | Graph rewriting: An algebraic and logic approach[END_REF] in an extended and constructive version [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF], MC can be shown to be FPT w.r.t. parameter tw(G + H). In [START_REF] Pichler | Multicut algorithms via tree decompositions[END_REF], an explicit dynamic programming algorithm is given, which also proves this result. Moreover, MC admits a 2-approximation algorithm in trees [START_REF] Garg | Primaldual approximation algorithms for integral flow and multicut in trees[END_REF], a O(1)-approximation algorithm in planar graphs [START_REF] Tardos | Improved bounds for the max-flow min-multicut ratio for planar and kr,r-free graphs[END_REF], a O(log |S|)-approximation algorithm in undirected graphs [START_REF] Garg | Approximate max-flow min-(multi)cut theorems and their applications[END_REF], and a O( √ n)-approximation algorithm in digraphs [START_REF] Gupta | Improved results for directed multicut[END_REF]. On the negative side, assuming the Unique Games Conjecture, MC has no (2 -)-approximation algorithm in trees for any > 0 (from [START_REF] Khot | Vertex cover might be hard to approximate to within 2[END_REF] and the equivalence between MC in stars with weights 1 and the Vertex Cover problem), and no O(1)-approximation algorithm in general graphs [START_REF] Chawla | On the hardness of approximating multicut and sparsest-cut[END_REF].

In MC, we are interested in the minimum number of edges whose removal makes the network entirely collapse (no pair of terminals can communicate with each other). In this paper, we investigate partial and generalized versions of MC, which are at least as hard as MC. The motivation for considering this partial version comes from the fact that, in practice, we are not always interested in the minimum number of link or node failures that can make the entire network collapse, but in the minimum number of such failures that can make a given portion of the network collapse.

Formally, in the Partial Multicut problem (PMC), we are given an integer P ≥ 1, and we are asking for the minimum weight of a set of edges that disconnects at least P pairs of terminals. Hence, when P = |S|, PMC is exactly MC. In the Generalized Partial Multicut problem (GPMC), we additionally define a profit function p : S → Z + , and a feasible solution must disconnect a set of terminal pairs of total profit at least P .

PMC has been studied in [START_REF] Daniel Golovin | Approximating the k-multicut problem[END_REF][START_REF] Levin | Partial multicuts in trees[END_REF], where (8/3 + ) and O(log 2 n log log n)-approximation algorithms are given for trees and unrestricted graphs, respectively. The approximation ratio in trees has been improved to 2 + in [START_REF] Mestre | Lagrangian relaxation and partial cover (extended abstract)[END_REF], and the O(log 2 n log log n)-approximation algorithm has been extended to GPMC in [START_REF] Könemann | A unified approach to approximating partial covering problems[END_REF]. To the best of our knowledge, the only known tractable case for PMC is the one of rooted trees [START_REF] Daniel Golovin | Approximating the k-multicut problem[END_REF] (which immediately implies the tractability of PMC in graphs of maximum degree two), and GPMC has only been studied in [START_REF] Levin | Partial multicuts in trees[END_REF] as the "prize-collecting multicut problem", and in [START_REF] Könemann | A unified approach to approximating partial covering problems[END_REF]. As MC is also tractable in rooted trees (which are directed trees), and as PMC is hard whenever MC is, this means in particular that we are not aware of any special case where MC and PMC behave differently (with respect to their computational complexity).

We provide new results for (G)(P)MC in particular in the case where the treewidth tw(G) of the input graph G is bounded, together with additional assumptions on either the demand graph H or its complement H. Table 1 provides a summary of state-of-the-art and new complexity results for MC and related problems depending on the treewidth of G, H, H, G + H and G + H.

We end this section by defining properly the notion of treewidth. Given a graph G = (V, E), a tree decomposition of G is a pair {X i |i ∈ I}, T where X i ⊆ V, ∀i ∈ I, is a bag of vertices of G, T = (I, F ) is a tree, and:

(1) i∈I X i = V , (2) For every edge uv ∈ E, there is an i ∈ I such that u, v ∈ X i , (3)
For all i, j, l ∈ I, if j lies in the path between i and l, then

X i ∩ X l ⊆ X j .
The width of a given tree decomposition of a graph G is equal to max i∈I |X i | -1. The treewidth of a graph G, denoted by tw(G), is the minimum width of a tree decomposition of G, taken over all tree decompositions of G. Note that trees (and hence chains and stars) have treewidth 1. Without loss of generality, we can also assume that the tree decomposition is nice [START_REF] Kloks | Treewidth: Computations and approximations[END_REF], i.e.:

• T is rooted at some node r,

• T is binary and has O(|V |) nodes,

• If a node i has two children j and k then X i = X j = X k (join node)

• If a node i has one child j, then either

(a) |X i | = |X j | -1 and X i ⊂ X j (forget node) (b) |X i | = |X j | + 1 and X j ⊂ X i (introduce node)
Such a nice tree decomposition of width tw(G) can be computed in polynomial time when tw(G) = O(1) [START_REF] Kloks | Treewidth: Computations and approximations[END_REF].

(G)(P)MC with tw(G) = 1 when G is directed

We begin by studying MC, PMC and GPMC when G is directed and tw(G) = 1, meaning that G is a directed tree. Recall that, in this case, MC is tractable. Moreover, PMC is tractable in rooted trees. We shall show that, on the contrary, PMC (and hence GPMC with unit profits) is strongly NP-hard in directed stars, hence providing the first special case where MC and PMC do not have the same behavior with respect to their computational complexity.

First, we show that PMC in directed stars is polynomially equivalent to another partial covering problem, called the Partial Weighted Vertex Cover problem (PWVC), in bipartite graphs. In this problem, we are given a nodeweighted graph, and the goal is to compute the minimum weight of a set of vertices that covers at least a given number of edges. It is clearly NP-hard in general graphs (as optimally covering all edges is), and in [START_REF] Caskurlu | Subramani. Partial vertex cover and budgeted maximum coverage in bipartite graphs[END_REF] it was shown to remain NP-hard in bipartite graphs as well, even when all weights are 1. Let us show the following proposition: Proof. Take any PMC instance in a directed star. We can assume without loss of generality that all sources have outdegree 1 and in-degree 0, and that all sinks have out-degree 0 and in-degree 1. We associate an undirected bipartite graph to this directed star by taking as vertices the sources and sinks (the weight of each vertex being the weight of the arc incident to the corresponding source or sink), and by adding an edge between two vertices if the corresponding source and sink in the directed star belong to the same terminal pair. Then, in the PMC instance defined in a directed star, removing an arc is clearly equivalent, in the PWVC instance defined in a bipartite graph, to selecting the vertex (source or sink) this arc is incident to. Conversely, any PWVC instance in a bipartite graph can be polynomially reduced to a PMC instance in a directed star, using the same correspondence (edges become terminal pairs).

Proposition 1. PMC in directed
Together with [START_REF] Caskurlu | Subramani. Partial vertex cover and budgeted maximum coverage in bipartite graphs[END_REF], Proposition 1 immediately implies:

Corollary 1. PMC is NP-hard in directed stars, even when all weights are 1.

The results in the rest of the paper are concerned with undirected graphs.

(G)(P)MC with bounded tw(G + H)

We now study MC, PMC and GPMC when the parameter tw(G + H) is bounded. We already know that MC is FPT w.r.t. tw(G+H) [START_REF] Gottlob | A logical approach to multicut problems[END_REF], and that it is APX-hard if only tw(G) is bounded. First, in Section 3.1, we prove that MC remains APX-hard if both tw(G) and tw(H) are bounded. Second, in Section 3.2, we show that GPMC is weakly NP-hard even if tw(G+H) is bounded. Third, in Section 3.3, we provide a pseudopolynomial-time algorithm for GPMC if tw(G + H) is bounded. This algorithm is FPT w.r.t. tw(G + H) when profits are unitary, thereby extending [START_REF] Gottlob | A logical approach to multicut problems[END_REF] to PMC. Fourth, in Section 3.4, we show how a simple rounding scheme can provide an FPTAS for GPMC when tw(G + H) is bounded.

APX-hardness of MC with bounded tw(G) and tw(H)

We now prove that MC with bounded tw(G) remains APX-hard even if we additionally suppose that tw(H) is bounded.

Proposition 2. MC in trees of height 1 is equivalent to MC in trees of height 2 with H a set of vertex-disjoint edges.

Proof. Let I i denote an instance of MC in a tree T i of height i, with demand graph H i , for i ∈ {1, 2}. First, let I 1 be given with arbitrary H 1 , and let r be the central vertex of T 1 . We can suppose w.l.o.g. that r has no incident edge in H 1 . We create an instance I 2 by replacing each leaf v of T 1 by a star with as many leaves as there are edges incident to v in H 1 . In I 2 , v is no longer a terminal, and each created leaf is a terminal that is incident to a single edge of H 2 . The graph H 2 is thus a set of vertex-disjoint edges, implying that tw(H 2 ) = 1, and hence that tw(T 2 ) + tw(H 2 ) = 2. Figure 1 shows an example where the edges of T i are solid, while the edges of H i are dashed. Moreover, the vertices appearing both in T 1 and T 2 are the black ones, while the vertices appearing in T 2 only are the white ones. The equivalence directly comes from the fact that, from each solution to I 2 , we can always build an alternative solution that costs no more, and that contains only edges incident to r.

Note that the equivalence naturally extends to the weighted case. This proposition, together with the fact that MC with unit weights is APX-hard in stars (Theorem 3.1 of [START_REF] Garg | Primaldual approximation algorithms for integral flow and multicut in trees[END_REF]), directly leads to the following result: Theorem 1. MC with unit weights is APX-hard in trees of height 2, even if H is a set of vertex-disjoint edges.

Weak NP-hardness of GPMC with bounded tw(G+H)

There is a natural reduction from the Minimum Knapsack problem (MinKP), which is weakly NP-hard (since it is equivalent to the classical Maximum Knapsack problem), to GPMC where G = H is a star, and thus tw(G + H) = 1. Given a MinKP instance, the associated GPMC instance consists of a central vertex with one leaf for each knapsack item. For each knapsack item, there is a terminal pair between the central vertex and a leaf, with corresponding profit and weight (on the edge). Hence the edges of H are the edges of G. In a solution to GPMC, an isolated terminal translates into a selected item in a MinKP solution. Conversely, given a non-trivial instance of GPMC where G = H is a star, we can build an equivalent instance of MinKP in the same fashion: there is an item for each leaf, whose weight (resp. profit) is the one of the edge of G (resp. of H) incident to this leaf. This proves the following:

Theorem 2. MinKP is equivalent to GPMC if G = H is a star.
Hence GPMC is weakly NP-hard when tw(G + H) = 1.

An algorithm for GPMC with bounded tw(G + H)

We design a dynamic programming algorithm which is FPT w.r.t. tw(G + H) for PMC and runs in pseudopolynomial time for GPMC.

Suppose that the graph G + H has bounded treewidth tw(G + H), and that a nice tree decomposition {X i |i ∈ I}, T of G + H of width tw(G + H) is provided, such that the bag of each leaf of T contains a single vertex of G (given a nice tree decomposition where the bag of a leaf is of arbitrary cardinality, adding at most tw(G + H) forget nodes is sufficient for each leaf). We add to the root r of T a gadget similar to the one for the leaves, that is to say a path in T , with r at one end, composed only of forget nodes, and which other end is an empty bag.

For each i ∈ I, E i = E ∩ X 2 i , i.e., E i denotes the set of edges of G + H induced by X i .
The output of the algorithm will be a partitioning of vertices into components, determined by a coloring of vertices. A coloring function on vertices is a function c : V → C, where C ⊆ Z is a set of colors, such that two vertices with different colors are not in the same component. Two vertices with the same color are in the same component if and only if there exists a path in G using only vertices with the same color. Hence two different components may be represented with the same color if they are not adjacent, i.e. if there exists no edge between any vertex of the first component and any vertex of the second component. Such a graph coloring determines the components as well as the set of edges between them (i.e., the bicolored ones). In general, the number of components of a graph G is thus not bounded by the number of colors |C|.

The weight (resp. profit) associated with a given coloring function c in a subtree T i rooted at an arbitrary node i ∈ I is defined as the sum of the weights (resp. profits) over all edges uv of G (resp. H) such that (1) both u and v lie in a bag at a node of T i , (2) uv ∈ E i , and (3) c(u) = c(v). At the root r, this definition corresponds to the total weight (resp. profit) associated with a coloring function c.

Given a partial coloring function c i on a bag X i , we therefore define f (i, c i , p i ) to return the minimum weight in the subtree T i rooted at i over all coloring functions c which extend c i and yield a profit at least p i in T i . If no such coloring exists, then f (i, c i , p i ) returns +∞.

The function f is defined recursively via four node cases.

If i is a leaf. Then, by convention, X i = {v}, and

f (i, c i , p i ) = 0 if p i = 0, +∞ otherwise.
If i is an introduce node. Let j be the child of i such that X i = X j ∪ {v}. We then simply have

f (i, c i , p i ) =f (j, c j , p i )
where c j is the restriction of c i to X j .

If i is a join node. Let j and h be the children of i, such that X i = X j = X h . We then have

f (i, c i , p i ) = min pi=pj +p h f (j, c i , p j ) + f (h, c i , p h ) If i is a forget node. Let j be the child of i such that X i = X j \ {v}. Then, f (i, c i , p i ) = min a∈C f (j, c j , max(0, p i - uv∈Ej , ci(u) =a p uv ))+ uv∈Ej , ci(u) =a w uv
where c j is the coloring function that extends c i over X j and c j (v) = a, and where p uv = 0 if uv ∈ S.

At the root node r. Calling f (r, c r , P ) returns the minimum cost of a partition of the vertices of G which yields a profit at least P .

Proof of correctness. The algorithm relies on the fact that the tree decomposition has exactly one forget node per vertex of G. The algorithm provides a coloring of G, which determines a partition of G, and therefore the set of edges of G and H that are cut. The weight or profit of an edge uv of G + H is taken into account at the forget node where one of the two vertices is removed (both u and v belonging to its child). Such a node necessarily exists by property of the tree decomposition, and because the bag of r is empty. Furthermore, such a node is necessarily unique, as the vertex removed cannot be introduced again at a later point in the tree decomposition.

Number of colors.

The following lemmas help us establish better running times:

Lemma 3. Given a graph G, χ(G) ≤ tw(G) + 1
where χ(G) is the chromatic number of G.

Proof. Given any graph G and a nice tree decomposition for G of minimum width tw(G), rooted at r, we show how to define a coloring of G using tw(G) + 1 colors. Start at the root bag X r , and give every vertex in X r a different color. We process the tree in a top-to-bottom fashion: once a color has been assigned to a vertex, the color of this vertex does not change. At a forget node, the new vertex is given a color that is not used in the parent bag (it may have been used earlier). The number of colors used in each bag is its cardinality, hence the total number of colors needed to color the whole graph is tw(G) + 1. This coloring is proper since for every edge there exists a bag containing its two endpoints.

Lemma 4. tw(G) + 1 colors are sufficient to color any feasible solution of a GPMC instance in a graph G.

Proof. Suppose we have a feasible solution E ⊆ E to such a GPMC instance. Let G be the minor of G obtained by contracting every edge in E \ E . Since tw(G ) ≤ tw(G) (see [START_REF] Robertson | Graph minors. II. Algorithmic aspects of tree-width[END_REF]), we have χ(G ) ≤ tw(G) + 1 by Lemma 3. Thus, we can compute a proper coloring c of G with size at most tw(G)+1, and, in G, give each vertex the color of the vertex of G it has been contracted into. This way, every edge in E has endpoints with different colors, or c would not be proper.

In the following analysis, we can thus suppose that the set of colors C has size bounded by tw(G+H)+1. Throughout, two vertices u and v which have been assigned the same color lie in the same component if and only if there exists a path in G between u and v that only goes through vertices with the same color. Furthermore, PMC corresponds to the case where all profits are equal to 1, and therefore P ≤ n 2 . This yields: Theorem 6. PMC is FPT w.r.t. tw(G + H).

An FPTAS for GPMC with bounded tw(G + H)

We present an FPTAS for GPMC in graphs with bounded tw(G + H) based on an FPTAS by rounding for MinKP [START_REF] Pruhs | Approximation schemes for a class of subset selection problems[END_REF]. In the traditional FPTAS for the Maximum Knapsack problem [START_REF] Vazirani | Approximation Algorithms[END_REF], the sum of the objective coefficients provides a trivial upper bound on the optimal value, which can be readily used to determine an appropriate scaling factor. By contrast, there is no trivial lower bound for MinKP. One alternative consists in computing a lower bound using a separate algorithm (as hinted in [START_REF] Gens | Complexity of approximation algorithms for combinatorial problems: a survey[END_REF]). We first show how an FPTAS can be obtained if these bounds can be guessed correctly.

Algorithm 1 A rounding FPTAS for GPMC with bounded tw(G + H) and bounds Let a precision > 0 and an instance of GPMC in a graph with n vertices and bounded tw(G + H) be given. Also suppose that 0 < LB ≤ U B are given. Proof. First, we prove that Algorithm 1 achieves a (1 + ) ratio. For any edge uv ∈ E, we have

K w(uv) < w(uv) + K,
and thus, for an optimal solution E * ,

K w(E * ) < w(E * ) + mK. (1)
Finally, we can prove: In establishing this result, we have not used the fact that we set W = (1 + )U B/K in Algorithm 1. We have just proved that K w( Ẽ) ≤ (1 + )OP T , and thus W = (1 + )U B/K is a valid upper bound on w( Ẽ). Second, we prove that the running time of Algorithm 1 is indeed polynomial in n and 1/ . Step 1 is linear in the number of edges, hence in O(n 2 ). Step 2 requires an algorithm polynomial in n and W . One such algorithm can be obtained by defining a function h(i, c i , w i ) similar to f (i, c i , p i ) (see Section 3.3), where h returns the maximum profit rather than the minimum weight (for f ), and essentially exchanging the role of P and W . By an analysis similar to the one used for f , the computation of h(r, c r , W ) can be done in O(n (tw(G+H)+1) tw(G+H)+1 W ( W +tw(G+H) 2 )) time. In the modified instance, we have

w( Ẽ) ≤ K w( Ẽ)
W = (1 + )U B K = ng(n) + ng(n),
which is polynomial in n and 1/ . Since, when tw(G + H) = O(1), Step 2 runs in O(n( W ) 2 ) time, this enables us to conclude that the whole running time is O(n 3 g 2 (n)/ 2 ), which is polynomial in n and 1/ .

Theorem 8. There exists an FPTAS for GPMC with bounded tw(G + H).

Proof. Simply call the approximation algorithm given in [START_REF] Könemann | A unified approach to approximating partial covering problems[END_REF]Theorem 13] for general graphs to compute a valid upper bound U B with g(n) = log 2 (n) log(log(n)).

Theorem 8 relies on an auxiliary algorithm to produce a valid upper bound U B. Complementary to this approach, we present a simple scaling scheme that allows to identify suitable LB and U B values in polynomial time by iteratively calling Algorithm 1. We first need a simple observation: Lemma 9. If LB ≤ OP T , then the output SOL of Algorithm 1 has the following properties: Lemma 9 allows us to write an algorithm which scales up LB and U B geometrically until they define an interval on OPT.

1. SOL ≤ (1 + )U B ⇒ SOL ≤ (1 + )OP T , 2. SOL > (1 + )U B ⇒ OP T > U B. Proof. 1. Suppose SOL ≤ (1 + )U B. If U B ≤ OP T , this directly implies SOL ≤ (1 + )OP T . Otherwise, LB ≤ OP T < U B,
Algorithm 2 A scaling and rounding FPTAS for GPMC with bounded tw(G + H) Let a scaling factor α > 1 be given. Proof. At the first iteration, LB = 1, hence the property holds. The value of LB is only changed at step 4, under the condition that SOL > (1 + )U B. From Lemma 9, this implies OP T > U B, hence in the next iteration we will have OP T > LB.

Theorem 11. Algorithm 2 is an FPTAS for GPMC with bounded tw(G + H).

Proof. At step 4, as LB ≤ OP T holds by Lemma 10, Lemma 9 guarantees that either (1) SOL is a (1 + )approximation, and the algorithm stops, or (2) OP T > U B, and the algorithm iterates. At iteration i ≥ 0, we have LB = α i and U B = α i+1 , and thus W = nα + nα for any iteration. The running time at each iteration is thus O(n 3 / 2 ), since α is a constant. Since the algorithm stops at the first iteration k for which OP T ≤ SOL ≤ (1 + )α k+1 , this means that log α (OP T ) ≤ log α (1 + ) + (k + 1), which gives the stopping criterion k ≥ log α (OP T ) -log α (1 + ) -1, hence the total running time is O(n 3 log(OP T )/ 2 ), which is polynomial in n, the size of the binary encoding of w, and 1/ .

It is interesting to notice that the maximum value W of an optimal solution considered in the modified problem with rounded weights in Algorithm 1 is fixed for all iterations of Algorithm 2. The modified weights of individual edges become increasingly smaller, and thus more edges can belong to an optimal solution of the modified problem. Indeed, in Algorithm 1, any edge uv with w(uv) ≥ W cannot be cut.

(G)(P)MC with bounded tw(G + H)

In this section we introduce the parameter H, which is simply defined as the complement of H. It turns out that a well-structured dense H can help design efficient algorithms for MC, as a well-structured sparse H does. Indeed, the case where H is complete (and therefore tw( H) = 0) is equivalent to the Multiterminal Cut problem, a well-studied special case of MC, which is polynomial-time solvable if tw(G) only is bounded [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF]. Furthermore, the problem becomes trivially linear-time solvable in trees [START_REF] Chopra | On the multiway cut polyhedron[END_REF][START_REF] Costa | Multiway cut and integer flow problems in trees[END_REF].

In Section 4.1, we show that PMC (and thus MC) is polynomial-time solvable in graphs with bounded tw(G + H). Note that the algorithm we design is not FPT w.r.t. tw(G+ H), and that, to the best of our knowledge, no result more general than the tractability of the Multiterminal Cut problem in graphs of bounded treewidth was known so far, even for MC.

We then show in Section 4.2 that the generalized version of this problem is not even solvable in pseudopolynomial time in this case, unlike the case where tw(G + H) = O(1). More precisely, we prove that GPMC is APX-hard when G is a star and H is complete, i.e., when tw(G + H) = 1. This highlights the fact that tw(G + H) is a parameter that does make the problem easier when bounded, and hence may seem similar to tw(G + H) (which was introduced in [START_REF] Gottlob | A logical approach to multicut problems[END_REF]) in that regard, but actually behaves a bit differently.

i = E ∩ X 2
i , and assume that a gadget is used to set up an empty bag at the root node of T , such that there is exactly one forget node in T per vertex of G.

The profit of a solution to a PMC instance is the number of edges of H having their two endpoints in different components (obtained after the removal of the edges in the solution), and can thus be computed as:

• |S|, i.e. the total number of edges of H,

• minus the number of edges of H with both endpoints in the same component. This is itself accounted as the sum, over each component:

of the number of edges of a complete graph over the vertices of H in that component,

minus the number of edges of H with both endpoints in that component.

Hence, we can compute the profit of a solution by knowing the number of vertices of H in each of these components, and the number of edges of H with both endpoints in the same component. In particular, the parameters of the recursive function f we define must keep track of these quantities. Since we consider a tree decomposition of G + H, for any pair of vertices of H that are non adjacent in H, and hence adjacent in H, there must exist a bag of this tree decomposition that contains both vertices. This implies that the number of edges of H with both endpoints in a given component can be updated any time a vertex of H is "forgotten", while the number of vertices of H in a given component can be computed only once the last vertex of this component has been "forgotten". The complete list of parameters of f is:

• a node i of T ,

• a coloring function c i defined as in Section 3.3.

• a counting function n i : C → {0, . . . , |V H |}, which, for each color a ∈ C, stores 0 if no vertex in X i has been assigned color a, and the number of vertices of H (possibly 0) not in X i that lie in the subtree of T rooted at i and belong to that component (colored by a) otherwise. Hence n i (a) counts the number of "forgotten" vertices of H in the component colored by a at node i, if there is at least one vertex of H having color a in X i .

• p i ∈ {-|E H |, . . . , |S| -P } keeps track of the uncut edges of H in the subtree rooted at node i. More precisely, it is computed as the sum of:

1. Plus the number of edges of H for which both endpoints belong to a same "forgotten" component, i.e. such that these components lie in the subtree rooted at i and have no vertex in X i .

2. Minus the number of edges of H for which at least one endpoint does not belong to X i (i.e., has been "forgotten"), both endpoints lie in the subtree rooted at node i and have the same color, say a, and this color appears in X i as well as in each bag lying between X i and any bag containing the first of the two endpoints that has been forgotten (meaning that both endpoints are in the component of color a having at least one vertex in X i ).

Note that, when there remains in X i only one vertex of H belonging to a component, all the edges of H whose endpoints belong to that component have been taken into account. Hence, when the last vertex of this component is forgotten, it suffices to add the number of edges of a complete graph over the vertices of H in that component in order to obtain exactly the number of edges of H whose endpoints belong to that component.

The returned value of f (i, c i , n i , p i ) is defined as in Section 3.3.

If i is a leaf. Then, by convention, X i = {v}, and f (i, c i , n i , p i ) = 0 if n i = 0 and p i = 0, +∞ otherwise.

If i is an introduce node. Let j be the child of i such that X i = X j ∪ {v}. We then simply have

f (i, c i , n i , p i ) = f (j, c j , n i , p i ),
where c j is the restriction of c i to X j .

If i is a join node. Let j and h be the children of i, such that X i = X j = X h . We then have f (i, c i , n i , p i ) = min pi=pj +p h , ni=nj +n h f (j, c i , n j , p j ) + f (h, c i , n h , p h ) where n i = n j + n h is an element-wise vector addition.

If i is a forget node. Let j be the child of i such that X i = X j \ {v}. Then, f (i, c i , n i , p i ) = min where c i and n i are such that, for each a ∈ C, c i (w) = a ∀w ∈ X i ⇒ n i (a) = 0, and where comp(c i , n i ) is the set of (c j , n j ) compatible with (c i , n i ). For all c i ∈ C, n i ∈ {0, . . . , |V H |} |C| , (c j , n j ) ∈ comp(c i , n i ) if and only if

• c j is a coloring function that extends c i over X j , such that c j (v) ∈ C \ {a ∈ C, n i (a) = 0, ∃u ∈ X i :

c i (u) = a} if v ∈ H.
• for all a ∈ C, At the root node r. We have added to r the same gadget as in Section 3.3. We call f with parameters i = r, c i = 0, n i = 0, p i = |S| -P .

n j (a)                = n i (a) -1 if c j (v) =
Proof of correctness. This algorithm relies on the fact that we can keep track of the number of vertices of H in the components of G associated with coloring c by using n i . When the last vertex of a component with color a is "forgotten" at a forget node i, we know the number of vertices of H in this component, and thus we know how many edges of H would not be cut if H was complete (this is the term ). Since H is in general not complete, we count the uncut edges of H as follows: each such edge is taken into account when its first endpoint v of color a is forgotten (this is the term |{uv ∈ H, u ∈ X i , c i (u) = a}|). We know that, in this way, all uncut edges of H will be taken into account, as T is a tree decomposition of G + H, and hence, for each edge in H, there is a bag in T containing its two endpoints. Thus, we can retrieve the number of edges of H which were not cut. The other parts of f are similar to those of f .

• We prove that PMC (and hence MC) can be solved in polynomial time when tw(G + H) = O(1), generalizing the tractability of MC when tw(G) = O(1) and tw( H) = 0. Can we also prove that (P)MC is not FPT w.r.t. tw(G + H)?

• We finally prove that, on the contrary, GPMC remains APX-hard even if tw(G + H) = 1 and all profits are polynomially bounded.

Figure 1 :

 1 Figure 1: Example of instances I 1 (left) and I 2 (right).

1 . 2 .

 12 Let K = LB m and, for each edge uv, set w(uv) = w(uv) K Return the optimal solution Ẽ found by an algorithm polynomial in n and W = (1+ )U B/K on the modified instance Theorem 7. Given LB ≤ OP T ≤ U B = g(n)LB as input, where g is a polynomial, Algorithm 1 is an FPTAS for GPMC with bounded tw(G + H).

  by rounding up, ≤ K w(E * ) by optimality of Ẽ for w, < w(E * ) + mK because of (1), = OP T + LB by definition of K, ≤ (1 + )OP T by definition of LB.

  in which case Theorem 7 applies, hence SOL ≤ (1 + )OP T . 2. Suppose SOL > (1 + )U B. If we had LB ≤ OP T ≤ U B, this would contradict Theorem 7. Hence OP T > U B.

1. Let LB = 1 . 2 .

 12 Let U B = αLB 3. Call Algorithm 1 with values LB and U B. Let SOL denote the value of the solution (+∞ if there is none). 4. If SOL > (1 + )U B, let LB = U B, and go to Step 2. 5. Return SOL. Lemma 10. At any point of Algorithm 2, LB ≤ OP T .

( 2 if

 2 cj ,nj )∈comp(ci,ni) f (j, c j , n j , p i c j (v) = a, v ∈ H, and c i (w) = a ∀w ∈ X i , nj (a)(nj (a)-1) 2 if c j (v) = a, v / ∈ H, and c i (w) = a ∀w ∈ X i , 0 otherwise. + |{uv ∈ H, u ∈ X i , c i (u) = c j (v)}|) + uv∈Ej , ci(u) =a w uv ,

  a, n i (a) ≥ 1, and v ∈ H, ∈ {0, . . . , |V H |} if c j (v) = a and c i (w) = a ∀w ∈ X i , = n i (a)otherwise.

Table 1 :

 1 Summary of complexity results for MC in graphs of bounded treewidth.

	stars is equivalent to

Table 2 :

 2 Running time for computing f on each type of node.Running time. The running time depending on the type of nodes is given inTable 2. There were O(n) nodes initially, but we added some forget nodes. However, af-

ter this transformation, there are exactly n forget nodes, hence there are still O(n) nodes in T . Moreover, there are O((tw(G + H) + 1) tw(G+H)+1 ) possible colorings for each bag and P possible profits, hence the overall running time of this dynamic programming algorithm is O(n (tw(G+H)+ 1) tw(G+H)+1 P (P + tw(G + H) 2 )).

Theorem 5. There is a pseudopolynomial-time algorithm that solves GPMC if tw(G + H) is bounded.

  Suppose that the graph G + H has bounded treewidth tw(G + H), and that a nice tree decomposition {X i |i ∈ I}, T of G + H of width tw(G + H) is provided. As in Section 3.3, we let E

	4.1. A polynomial-time algorithm for PMC in graphs with
	bounded tw(G + H)

APX-hardness of GPMC in stars with complete H

We have proved in Section 4.1 that Partial Multicut is polynomial-time solvable in graphs with bounded tw(G + H). We now prove that the generalized version of this problem, GPMC, is actually APX-hard in these graphs. This result may seem surprising considering the fact that the algorithm for PMC in graphs with bounded tw(G + H) can be extended naturally to handle arbitrary profits in pseudopolynomial time, as shown in Section 3.3. However, the one given in Section 4.1 cannot be adapted to GPMC, as in this case the edges of H have no associated profit, and hence cannot be used to compute the total profit of the uncut edges of H. Theorem 13. The Generalized Partial Multicut problem with unit weights is APX-hard if G = (V, E) is a star and H is complete.

Proof. We reduce MC with arbitrary

H GP M C is the complete graph on V M C , and in both problems G = (V, E) is a star with unit weights. As in [START_REF] Garg | Primaldual approximation algorithms for integral flow and multicut in trees[END_REF], we can suppose w.l.o.g. that the central vertex r of G is not a terminal in MC and thus not in GPMC, and that every leaf is a terminal, i.e., that V M C = V \ {r}. We define the profits of pairs of terminals (u, v) ∈ E GP M C to be

We set the target profit to be

For any w ≥ 0, we prove that there exists a solution of size w to MC if and only if there exists a solution of size w and profit at least P for GPMC.

(⇒ direction) Suppose that a solution to an instance of MC is a set of edges E * of size w. Then, in the associated instance of GPMC, E * disconnects each pair of terminals that has a profit |E GP M C |, therefore the profit retrieved is at least

(⇐ direction) Suppose that a set of edges E * of size w is a solution to an instance of GPMC, i.e., that it disconnects pairs of terminals in H GP M C with a total profit at least P . Suppose now that there exists a pair of terminals (u, v) ∈ E M C that is not disconnected in G by the removal of E * . Then, even if every other pair of terminals in E GP M C is disconnected, the associated profit is

which is a contradiction. Therefore, in any solution E * to this GPMC instance, all pairs of terminals in E M C must be disconnected. Since the set of edges E * has size w, it is a solution to the associated MC instance.

The encoding size of the additional input in GPMC is polynomial in the size of the MC instance, as at most |V | 2 profits of value |E GP M C | ≤ |V | 2 must be encoded, and the reduction itself can be performed in a time polynomial in the size of the MC instance. Since MC is APX-hard in stars with unit weights [START_REF] Garg | Primaldual approximation algorithms for integral flow and multicut in trees[END_REF], the result follows.

Intuitively, the proof of Theorem 13 shows that we can emulate an arbitrary H M C for MC with a complete H GP M C in GPMC using hierarchical profits.

Conclusion and open problems

We summarize our main results, and highlight two open questions:

• We prove that PMC is strongly NP-hard in directed stars, while it is tractable in rooted trees, and while in addition MC is tractable in directed trees. This is the first such case we are aware of: are there other cases where MC and PMC behave differently, with respect to their computational complexity?

• We prove that MC remains APX-hard even if tw(G) + tw(H) = 2, while it was known to be FPT w.r.t. tw(G + H).

• We prove that, like MC, PMC is FPT w.r.t. tw(G + H), and that GPMC, which is weakly NP-hard when tw(G + H) = O(1), admits both a pseudopolynomialtime algorithm and an FPTAS in this case.


C Dufour

C Crampon

C Delbecque

P-P Garry

E Badens

Sclareol Purification Using the Supercritical Fractionation Process: A Modeling Case Study

Keywords: Supercritical carbon dioxide, Fractionation, Counter-current column, Sclareol, Group method

The aim of this study was to model experimental results obtained for the supercritical CO2 fractionation of a liquid mixture containing 24% of sclareol in order to recover a raffinate with increased sclareol content. First, supercritical CO2 fractionation experiments were carried out at pressures (10 to 12) MPa, and temperatures (313 to 338) K. Secondly, the modeling of the raffinate and extract compositions for 12 selected compounds including sclareol was performed using the group method. The modeling was carried out at a temperature of 323 K and pressures of (10 to 11) MPa, and at a temperature of 338 K and a pressure of 12 MPa. The calculation of the raffinate and extract compositions required the adjustment of the number of theoretical stages and of the distribution coefficients for the selected compounds. Experimental raffinate and extract compositions were represented by the model with a relative error of about 15%.

Introduction

Clary sage (Salvia sclarea L.) is a very odorous herbaceous plant [START_REF] Hao | Temporal transcriptome changes induced by methyl jasmonate in Salvia sclarea[END_REF], endemic to Provence in the South of France. The calyx of Clary sage flowers contains about 1-4% of sclareol [START_REF] Caissard | Extracellular Localization of the Diterpene Sclareol in Clary Sage (Salvia sclarea L., Lamiaceae)[END_REF] 2 which is a raw material used in perfumery for the production of Ambrox® or Ambroxan® [START_REF] Caniard | Discovery and functional characterization of two diterpene synthases for sclareol biosynthesis in Salvia sclarea (L.) and their relevance for perfume manufacture[END_REF][START_REF] Schmiderer | Diversity of essential oil glands of clary sage (Salvia sclarea L., Lamiaceae)[END_REF]. Sclareol (fig. 1) is used as a base and fixative note with a view to substituting natural ambergris (whale intestinal secretions).

The aim of this study was to carry out the modeling of experimental data obtained by fractionating a clary sage complex mixture containing 24% of sclareol and about 200 other compounds, using supercritical CO2, with a simple method already applied to supercritical fractionation results [START_REF] Pieck | A new model for the fractionation of fish oil FAEE[END_REF].

Very little modeling of the supercritical fractionation process according to this approach is proposed in the litterature. Mathematical models do not often take into account the physical phenomena such as the model used by Varona et al. [START_REF] Varona | Supercritical carbon dioxide fractionation of Lavandin essential oil: Experiments and modeling[END_REF]. Other models, such as Martín and Cocero's, study the purification of one single compound [START_REF] Martín | Mathematical modeling of the fractionation of liquids with supercritical CO2 in a countercurrent packed column[END_REF]. To carry out this modeling, the choice fell upon a simple model called the group method, which was developped by Kremser [START_REF] Kremser | Theoretical analysis of absorption columns[END_REF] for absorbers and improved by Edminster [START_REF] Edmister | Absorption and stripping-factor functions for distillation calculation by manual-and digital-computer methods[END_REF] for vapor/liquid separations under low pressure. Henley and Seader [START_REF] Henley | Approximate Methods for Multicomponent, Multistage Separations[END_REF] then applied this method to the vapor/liquid separation of hydrocarbons. More recently, Pieck et al. [START_REF] Pieck | A new model for the fractionation of fish oil FAEE[END_REF] used the group method to represent the supercritical fractionation of an esterified fish oil.

The supercritical fractionation is a process allowing the compounds contained in a liquid mixture to be separated by using a solvent under supercritical conditions. The feed diluent and the solvent must not be miscible under the implemented operating conditions. Supercritical fractionation process is generally carried out in continuous mode, using a counter-current packed column, in which the liquid feed and the supercritical solvent are introduced at the top and bottom of the column respectively, and put in contact with each other [START_REF] Brunner | Counter-current separations[END_REF][START_REF] Bejarano | Fractionation technologies for liquid mixtures using dense carbon dioxide[END_REF]. In this configuration, supercritical fractionation is similar to absorption where the extract (or light phase) composed of the most soluble compounds in the supercritical solvent is recovered at the top of the column. Conversely, the raffinate, corresponding to the highest density phase containing the least soluble compounds, is collected at the bottom of the column. Carbon dioxide (CO2) is the most frequently encountered solvent for the supercritical fractionation operation and allows such a process to cumulate many advantages when compared to conventional techniques. First of all, supercritical CO2 fractionation is a sustainable and continuous process. The process selectivity can be tuned according to the pressure and temperature conditions applied in the column, which are directly linked to the physicochemical properties of supercritical CO2, and according to the feed and solvent flowrates on which the hydrodynamics depends. CO2 can be easily recycled and the raffinate and the extracts are free of solvent since gaseous CO2 is spontaneously separated after depressurization. A post-treatment is generally not required. Even if supercritical fractionation involves high pressure equipment, it can be economically viable thanks to its compacity and flexibility. In addition, it is a low temperature operation which allows processing thermolabile compounds. To conclude, supercritical CO2 fractionation can be an interesting alternative for complex separations [START_REF] Pieck | Multi-scale experimental study and modeling of the supercritical fractionation process[END_REF]. Finally, this operation can also be coupled with conventional ones to improve their overall separation efficiency.

In this work, an experimental study followed by a modeling stage is proposed. In the first step, experiments were conducted at pressures of (10 to 12) MPa, at temperatures of (313 to 338) K and for solvent-over-feed ratios between 13 and 173 with the objective of obtaining a sclareol-rich raffinate, the solubility of sclareol in supercritical CO2 being low. These operating conditions were determined after a preliminary study presented in a previous article [START_REF] Dufour | Purification of sclareol by supercritical CO2 fractionation process[END_REF]. In the second step, the group method was used to model the distribution of sclareol and 11 selected compounds in extract and raffinate during the supercritical CO2 fractionation process. The assumptions for the model application were checked and the number of theoretical stages and the distribution factors for each selected coumpound were adjusted on experimental composition data. Finally, the calculated compositions in raffinate and extracts were compared to the experimental ones.

Materials and Methods

Materials

Carbon dioxide with a purity of 99.7% was supplied by Linde Gaz (France).

The studied feed used for supercritical CO2 fractionation experiments was provided by the company Bontoux SAS (Saint Auban sur l'Ouvèze, France). This liquid mixture was the lightest fraction of an extract obtained from Clary sage flowers and was composed of 24 wt% of sclareol as well as about 200 other compounds.

Experimental set-up

Fig. 2 shows a simplified schematic diagram of the supercritical CO2 fractionation apparatus.

The apparatus and procedure have already been described in a previous paper [START_REF] Dufour | Purification of sclareol by supercritical CO2 fractionation process[END_REF]. The unit consists in a 2.6 m high packed column with a 30 mm internal diameter.

A typical run was carried out as follows: the column was first heated up to the targetted temperature before CO2 was introduced. A CO2 high-pressure piston pump was then set at the desired flow rate and operating pressure by means of a back-pressure regulator. When the steady-state was installed relative to CO2, the liquid mixture was introduced at the desired flow rate using a piston pump. Extract and raffinate samples were collected and analyzed at regular time intervals and steady-state conditions were assumed to be reached as soon as the standard deviations for three successive samples were less than 1wt% of sclareol. After repeatability tests, the experimental raffinate and extract compositions were determined with an uncertainty around 2.6% and the error on the ratio S/Z (solvent massic flowrate divided by the liquid mixture massic flowrate) was about 3%.

Experimental data were obtained for operating conditions as follows: temperatures between 313 K and 338 K, pressures between 10 MPa and 12 MPa and for solvent-over-feed ratios between 13 and 173. These operating conditions were deduced after a preliminary study presented in a previous article [START_REF] Dufour | Purification of sclareol by supercritical CO2 fractionation process[END_REF]. The objective was to find the optimum operating conditions for concentrating sclareol in the raffinate.

Analytical methods

The process input (feed mixture) and outputs (extract and raffinate collected through the fractionation experiments) were analyzed by gas chromatography with a column HB5HT: 15 m × 0.25 mm × 0.1 µm with Flame Ionization Detector (FID) (Autosystem XL, Perkin Elmer). The recovered extract and the liquid feed mixture were diluted to 20% in chloroform (Sodipro, 99.5%). Diethyl phthalate (Grasse Chimie's World, 99.5%) was used as a standard for the quantification of sclareol.

Modeling

The extract and raffinate compositions were calculated using a model based on the group method developed by Kremser and Edmister [START_REF] Kremser | Theoretical analysis of absorption columns[END_REF] for the modeling absorption process. The choice fell on this model because it had already been validated on the experimental results of Pieck et al. [START_REF] Pieck | A new model for the fractionation of fish oil FAEE[END_REF].

The model is based on a simple relation linking the extraction yield (ε) and the stripping factor ( i) for each component i (Eq. 1).

i = Ki ε (1)
Where Ki is the overall distribution coefficient of component i, and ε, the extraction yield, is the ratio between the extract mass flow rate E and the feed mass flow rate Z. The extraction yield ε is calculated as follows (Eq. 2), considering that the feed mass flowrate Z is equal to the sum of the extract mass flow rate E and the raffinate mass flow rate R:

= = (2)
The stripping loss was determined by (Eq. 3):

φ . = (3)
The expression shown as eq. 3 can be used to compute the extract and raffinate compositions (respectively X E and X R ) if the stripping loss for each component i is known.

= . . (4)
= .

.

Xi Z is the composition of compound i in the feed.

The error distribution in the experimental data was assumed to be log-normal. Hence, the number of theoretical stages n and the overall distribution ratio Ki were fitted altogether to experimental data using the GRG (Generalized Reduced Gradient) nonlinear Solving Method from the Microsoft Excel solver, by minimizing the objective function (Eq. 6):

# = ∑ %&'( )*+ , -&'( ./0. ,1 2 ∀ (6)
In which Xi represents both the extract and raffinate mass fractions of the selected components i and the rest of the compounds cumulated into a single pseudo-component.

Modeling using the group method requires the validation of two hypotheses: that the steadystate is established and the studied mixture is considered as ideal.

Results and discussion

Experimental results

For each experimental condition, the overall mass balance in sclareol was satisfactory since the mean deviation was 2%. For all experiments, the compound of interest, sclareol, was concentrated in the raffinate. Table 1 gives the experimental results obtained for the operating conditions studied.

Z, S, R, and E, are the mass flow rates of the feed, supercritical CO2, raffinate, and extract, respectively. X Z is the mass fraction of sclareol in the feed and X R , and X E , are the supercritical solvent-free mass fractions of sclareol in the raffinate and the extract, respectively. β* is the ratio between the recalculated mass fraction of sclareol in the feed from a partial mass balance when the steady state was assumed, and the initial mass fraction in the feed. Finally, τ is the sclareol yield in the raffinate. highlights that a 338 K pressure had a slight influence on the mass fraction of sclareol in the extract, whatever the CO2-over-feed ratio from 15 up to 160. The influence of pressure was a little more pronounced on the sclareol content in the raffinate since at a constant CO2-overfeed ratio, the mass fraction of sclareol at 12 MPa is slighly higher than at both 10 MPa and 11 MPa. Even in Fig. 4 (b) which illustrates the evolution of the sclareol yield versus the ratio R/(R+E), no significant influence of pressure was noted.

Some assays were finally carried out at 323 K (Fig. 5). At that temperature, the pressure had a significant influence on the mass fraction of sclareol both in the raffinate and the extract. At the highest pressure of 12 MPa, Fig. 5 (b) reveals the fall in sclareol yield while the ratio R/ R+E decreased. As for the temperature of 313 K, at 323 K there was a drop in the selectivity when the pressure increased.

Selection of the 12 compounds from the feed selected for modeling

The liquid mixture to be fractionated was composed of about 200 different compounds. In this work, 12 compounds including sclareol were selected to study their distribution in the extract and in the raffinate versus the extraction yield. The choice fell on compounds easily identifiable by gas chromatography, distributed over the entire length of the chromatogram, having interesting behavior for sclareol purification, and present both in the extract and the raffinate. Sclareol (I12), together with seven major compounds (named I1 to I7) were identified as major compounds in the mixture. Four impurities (named I8 to I11) characterized the quality of the separation since they are due to the degradation of sclareol during storage and prove difficult to remove by currently used purification techniques. Fig. 6 shows the gas chromatographic profile of the feed in which the selected compounds are highlighted and table 2 gives the content of the selected compounds in the feed.

Assumptions for model application

The first assumption to be checked is that the steady-state was well established. To that aim, the mass balance for each component i in the feed should be verified:

8 = 9 + : (5)
With Zi, Ei and Ri the massic flow rates of compound i in the feed, extract and raffinate, respectively.

The following equation is obtained:

= + 1 - (7)
The right term represents the global composition of the Xi Z feed calculated using the mass fraction measured in the extract Xi E and in the raffinate Xi R . This calculated value has to be compared to the experimental one. If the mass balance is verified, when plotting the calculated mass fraction in the feed versus the experimental corresponding value, a straight line passing through the origin and with a slope of 1 is obtained. Fig. 7 shows the calculated (Xi Z )calc versus the experimental (Xi Z )exp and thus illustrates the mass balance obtained for the selected components at 10 MPa and 323 K. As a proportionality is observed between the calculated and the experimental mass fractions, with in addition a slope of the straight line very close to 1, the steady-state was well established.

The second assumption to be checked for the application of the model is that the studied mixture can be considered as an ideal mixture, meaning that the solubility of each compound in CO2 is independent of the proportion of each compound in the mixture. If the solubility is considered independent of the composition, the extraction yield is a linear function of the solvent-over-feed ratio (S/Z). This hypothesis was checked for three studied operating conditions: a temperature of 323 K for pressures of 10 MPa and 11 MPa and a temperature of 10 338 K for a pressure of 12 MPa. Fig. 8 shows the extraction yield versus the CO2-over-feed ratio for experiments carried out at 323 K and 10 MPa. A straight line of equation (y = 0.004

x ) was obtained leading to the conclusion that the feed mixture could be considered as ideal under such operating conditions.

Modeling of the extract and raffinate compositions

The model was applied for three different operating conditions that respected the assumptions of the model (323 K for pressures of 10 MPa and 11 MPa and 338 K for a pressure of 12 MPa) and table 3 gives the estimation of overall distribution coefficient (Ki) for each compound and each operating condition. Fig. 9 shows the modeling of the 12 compounds selected in the mixture.

The estimation of the distribution coefficients in table 3 and the curves obtained in Fig. 9 emphasize three different types of behavior. Firstly, compounds I1, I2, I3, I4 and I6 behaved similarly (Fig. 9 (a-d) and (e)). Indeed, they had a distribution coefficient greater than 1 so that they were preferentially collected in the extract. On the contrary, compounds I7, I8, I9, I10, I11, and the sclareol had a distribution coefficient lower than 1; they were indeed collected in the raffinate (Fig. 9 (f-l)). And finally, a third type of behavior was observed: compound I5 had a distribution coefficient around 1 and was evenly distributed between the extract and the raffinate (Fig. 9 (e)).

Experimental data were represented by the model with a relative error of about 15% which is satisfactory regarding the complexity of the system. Indeed, it was a natural extract with a real industrial application. The same error of 15% was determined by Pieck et al. [START_REF] Pieck | A new model for the fractionation of fish oil FAEE[END_REF]. Varona et al. [START_REF] Varona | Supercritical carbon dioxide fractionation of Lavandin essential oil: Experiments and modeling[END_REF] predicted the separation factor with an average deviation of 20%. Fig. 10 compares the experimental composition values to the calculated ones for the three operating conditions considered and for the 12 selected compounds. A good correlation was observed between the model and the experimental data. The points outside the outline were those corresponding to traces of the light compounds in the raffinate, implying a bigger error between the model and the experimental data.

Conclusion

Supercritical CO2 fractionation was applied to a complex feed mixture containing more than 200 compounds with the objective of concentrating sclareol in the raffinate. The group method was used in order to model the compositions of 12 selected compounds including sclareol. Although such a model may only suit ideal mixtures, a good correlation was obtained between experimental compositions and calculated values for three different operating conditions. A relative error of about 15% was reached and for such a complex system, those results can be considered as satisfactory. Moreover, modeling allowed to highlight three different types of behavior in relation to the values of the distribution coefficients. Compounds having a distribution coefficient greater than 1 were preferentially collected in the extract; when the distribution coefficients were lower than 1, the compounds were collected in the raffinate; and, finally, the compounds fairly distributed between the extract and the raffinate had distribution coefficients close to 1. Such modeling, although its simplicity, may offer a better understanding of component behavior when considering the separation of complex mixtures using supercritical fractionation. 3 for peak identification.

Figure captions

(X i Z ) calc (X i Z ) exp

Figs. 3

 3 Figs. 3 to 5 regroup the results obtained and highlight the influence of pressure, temperature,

Fig. 4

 4 Fig.4 and 5show the influence of pressure at two temperatures: 323 K and 338 K. Fig.4(a)

Fig. 1 .

 1 Fig. 1. Sclareol skeletal formula.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Supercritical fluid fractionation unit.

Fig. 4 .

 4 Fig. 4. Evolution of the mass fraction of sclareol (a) in the extract at 10 MPa (○), 11 MPa (□),

Fig. 5 .

 5 Fig. 5. Evolution of the mass fraction of sclareol (a) in the extract at 10 MPa (○), 11 MPa (□),

Fig. 6 .

 6 Fig. 6. Chromatographic profile of the feed containing about 24% of sclareol with an

Fig. 7 .

 7 Fig. 7. Mass balance checking for the essays performed at 10 MPa and 323 K -Calculated

Fig. 8 .Fig. 9 .

 89 Fig.8. Extraction yield versus the CO2-over-feed ratio at 323 K and 10 MPa -the slope of the straight line is equal to 0.004 and the regression coefficient R 2 is equal to 0.9761.

Fig. 10 .

 10 Fig. 10. Comparison between experimental and calculated compositions in the extract and the

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Sclareol skeletal formula

Fig. 4 .

 4 Fig. 4. Evolution of the mass fraction of sclareol (a) in the extract at MPa (○), 11 MPa (□),

Fig. 5 .

 5 Fig. 5. Evolution of the mass fraction of sclareol (a) in the extract at MPa (○), 11 MPa (□),

Fig. 6 .

 6 Fig. 6. Chromatographic profile of the feed containing about 24% of sclareol with an

Fig. 7 .

 7 Fig. 7. Mass balance checking for the essays performed at 10 MPa and 323 K -Calculated global fraction in the feed (Xi Z )calc versus the experimental one (Xi Z )exp. The slope of the straight

Fig. 8 .

 8 Fig. 8. Extraction yield versus the CO2-over-feed ratio at 323 K and 10 MPathe slope of the straight line is equal to 0.004 and the regression coefficient R 2 is equal to 0.9761

Table 1 .

 1 Experimental results obtained for operating conditions studied. * Supercritical solvent free mass fractions; ** β: partial mass balance in sclareol

	P	T	S	Z	XZ	E	XE *	R	XR *	β **	τ
					±0.1		±0.1		±0.1
	(MPa)	(K)	(kg⋅h -1 )	(kg⋅h -1 )	(%)	(kg⋅h -1 )	(%)	(kg⋅h -1 )	(%)		(%)
	10	338		1.93	23.3	0.049	0.7	1.88	23.9	0.99	99.9
				0.22	23.3	0.044	0.7	0.17	28.9	0.96	99.4
				0.97	23.3	0.048	0.6	0.93	24.7	1	99.8
				0.49	24.3	0.047	0.9	0.44	27.1	1	99.7
				1.43	24.0	0.26	1.6	1.17	27.6	0.95	98.7
				0.68	24.0	0.23	1.7	0.44	35.6	0.98	97.5
		323		1.16	24.5	0.089	1.3	1.07	26.7	1	99.6
				0.72	24.1	0.087	1.4	0.64	27.8	1	99.3
				0.55	22.7	0.11	1.3	0.44	28.8	1	98.9
				0.70	23.3	0.19	1.4	0.51	32.0	1	98.4
				0.48	21.4	0.19	1.5	0.29	37.4	1	97.5
				0.23	21.4	0.15	1.9	0.079	51.4	0.88	93.3
		313		1.37	24.5	0.49	3.7	0.88	37.6	1	94.8
				0.56	24.5	0.27	4.1	0.28	49.9	1	92.5
				1.94	24.3	0.97	4.0	0.97	43.7	0.98	91.6
				1.44	21.7	0.88	4.3	0.57	53.7	1	88.9
				1.47	22.0	0.87	3.8	0.60	50.4	1	90.0
				1.68	19.5	1.01	3.2	0.66	45.1	1	90.0
				1.17	19.5	0.69	3.6	0.47	49.8	1	90.6
				1.21	18.1	0.84	3.5	0.37	56.2	1	87.4
	11	338		1.91	23.9	0.088	1.1	1.82	25.0	0.99	99.8
				1.41	23.9	0.082	1.0	1.32	24.8	0.97	99.8
				1.14	23.9	0.075	1.0	1.07	25.1	0.99	99.7
				0.95	23.9	0.091	1.0	0.86	26.4	1	99.6
				0.68	23.9	0.083	1.0	0.59	27.4	0.99	99.5
				0.43	23.8	0.083	1.1	0.34	29.2	0.98	99.1
				0.18	23.8	0.055	1.3	0.12	36.6	1	98.4
		323		1.94	24.6	0.51	2.5	1.43	30.9	0.95	97.2
				1.41	24.6	0.41	2.6	1.00	34.9	1	97.0
				1.18	24.4	0.43	2.7	0.75	35.4	0.96	95.8
				1.41	24.6	0.41	2.6	1.00	34.9	1	97.0
				1.18	24.4	0.43	2.7	0.75	35.4	0.96	95.8
				0.92	24.4	0.36	2.8	0.56	40.5	1	95.6
				0.67	24.4	0.36	3.3	0.31	47.9	0.98	92.6
				0.42	24.4	0.27	4.0	0.15	59.1	0.97	89.1
	12	338		1.89	24.6	0.20	1.5	1.69	26.5	0.97	99.3
				1.36	24.6	0.17	1.5	1.19	27.3	0.98	99.2
				1.16	23.1	0.20	1.5	0.96	27.9	1	98.9
				0.90	23.1	0.17	1.5	0.73	29.1	1	98.8
				0.67	23.2	0.19	1.6	0.48	31.8	1	97.9
				0.41	23.2	0.15	1.7	0.26	36.8	1	97.2
		323		1.89	23.7	0.91	4.1	0.97	45.2	1	92.1
				1.23	23.7	0.62	4.4	0.61	49.9	1	91.7
				1.16	29.8	0.71	4.8	0.45	57.6	0.88	88.3
				0.76	29.8	0.47	5.4	0.28	62.7	0.89	87.4
				0.68	24.1	0.51	7.6	0.17	73.9	1	76.4
				0.36	24.1	0.29	13.3	0.065	76.9	1	56.0
				0.52	23.5	0.43	10.5	0.089	76.3	0.93	60.1