Maher Mallem
email: maher.mallem@lip6.fr

Claire Hanen
email: claire.hanen@lip6.fr

Alix Munier Kordon

Scheduling coupled tasks with time windows: a parameterized complexity analysis

Keywords: parameterized complexity, scheduling, coupled tasks

This paper studies the parameterized complexity of coupled tasks scheduling problems with time windows considering two parameters: the pathwidth and the slack. Three types of precedence delays are studied: minimum, maximum and exact. For all cases we prove that these problems are para-NP-hard parameterized by the slack even for unit processing time jobs. We exhibit a relation between the slack and the pathwidth that allows us to extend these results for the pathwidth parameter. Lastly a polynomial procedure is provided in the special case where the slack is equal to one.

Introduction

Since the seventies many studies have been devoted to scheduling problems on a single processor with different settings and optimization criteria. If we just consider decision problems only few problems can be solved in polynomial time -like scheduling unit execution time jobs with time windows [START_REF] Martel | Preemptive scheduling with release times, deadlines, and due times[END_REF] or scheduling jobs with precedence constraints and deadlines [START_REF] Lawler | Optimal sequencing of a single machine subject to precedence constraints[END_REF]. On the other hand many sequencing problems with simple settings are NP-hard in the strong sense, especially when time windows are considered [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF]. This paper addresses a single machine problem with time windows and precedence constraints with delays. We are given a set of jobs T . Each job J ∈ T is characterized by a processing time p(J) = 1 and a time window [r(J), d(J)) in which it should be scheduled. A non negative delay ℓ a is attached to each precedence constraint a between two jobs J and J ′ . Three types of delays are considered. In the case of minimum delays, the difference between the starting time of J ′ and the completion time of J must not be less than ℓ a ; in the case of maximum delays, this difference must be not greater than ℓ a ; for exact delays this difference must be exactly equal to ℓ a .

We study an interesting special case called coupled tasks where the precedence graph is just a set of disjoint arcs. They have been studied for many years due to their many applications. Scheduling jobs on single machine assuming unit processing times and coupled tasks has been proven NP-hard by Yu [START_REF] Yu | Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard[END_REF] for exact and minimum delays. See [START_REF] Chen | Scheduling coupled tasks with exact delays for minimum total job completion time[END_REF][START_REF] Khatami | Coupled task scheduling with exact delays: Literature review and models[END_REF] for a survey of complexity results of coupled tasks with exact delays.

In order to go beyond these results parameterized complexity gives us tools to refine the analysis and understand deeper on which parameter of the instances the problem complexity relies. Given a parameter k and denoting n the input size, a problem is called fixed-parameter tractable (FPT) with respect to parameter k if it can be solved in time poly(n) × f (k) with f an arbitrary function [START_REF] Downey | Parameterized complexity[END_REF].

When the studied problem is believed to not be FPT, the para-NP class is used as a parameterized version of NP: a problem is in para-NP with respect to parameter k if there is a non-deterministic algorithm that solves it in time poly(n) × f (k) with f an arbitrary function. In order to prove that a problem is para-NP-hard with respect to k, it is enough to prove that the un-parameterized problem is NP-hard for some fixed value of k [START_REF] Flum | Parameterized complexity theory[END_REF]. The W-hierarchy defined in [START_REF] Downey | Descriptive complexity and the W hierarchy[END_REF] is an additional widely used tool in parameterized complexity. It is a sequence of intermediate complexity classes between FPT and para-NP, which allows us to further investigate the time complexity of a parameterized problem.

Several parameters have been considered for the analysis of the parameterized complexity of scheduling problems, like the maximum processing time p max [START_REF] Mnich | Scheduling and fixed-parameter tractability[END_REF] or the width of the precedence graph [START_REF] Van Bevern | Precedence-constrained scheduling problems parameterized by partial order width[END_REF]. Considering precedence delays we can first mention the work of Bessy et al. [START_REF] Bessy | Parameterized complexity of a coupled-task scheduling problem[END_REF] about coupled tasks with due dates, a compatibility graph and a common deadline on a single machine. Their parameter was the number of jobs ending before their due date. They established W [START_REF] Baart | Single-machine scheduling with release times, deadlines, setup times, and rejection[END_REF]-hardness for this problem and developed a FPT algorithm when the maximum duration of a job (i.e. the processing time of the two tasks plus their delay) is bounded. Van Bevern et al. [START_REF] Van Bevern | Precedence-constrained scheduling problems parameterized by partial order width[END_REF] proved that the problem of scheduling a precedence graph on two machines with processing times in {1, 2} is W [START_REF] Bessy | Parameterized complexity of a coupled-task scheduling problem[END_REF]hard with respect to the width. In the same paper they introduced an additional parameter λ that measures the maximum allowed lag of a job with respect to its earliest start time (ignoring resource constraints). They proved that the Resource-Constrained Project Scheduling Problem (RCPSP) is FPT parameterized by both the allowed lag and the width.

In the presence of time windows, several authors considered parameters taking into account their maximum overlapping number. Bodlaender and van der Wegen [START_REF] Bodlaender | Parameterized complexity of scheduling chains of jobs with delays[END_REF] addressed the single-machine scheduling of a set of chain like precedence constraints with delays where the time windows are expressed on chains and not on individual jobs. Their parameter -called the thickness -corresponds to the maximum number of overlapping chains. They proved that the problem with minimum delays given in unary is W [START_REF] Bessy | Parameterized complexity of a coupled-task scheduling problem[END_REF]-hard with respect to the thickness.

Similarly the pathwidth µ is the maximum number of overlapping time windows minus one. Munier-Kordon [START_REF] Munier Kordon | A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows[END_REF] developed a FPT algorithm for the decision problem of scheduling unit execution time jobs with precedence constraints and time windows of jobs parameterized by µ. In [START_REF] Mallem | Parameterized complexity of a parallel machine scheduling problem[END_REF] scheduling chains of unit execution time jobs with minimum or exact delays on a single processor was proved to be para-NP-hard with parameter µ, whereas it was proved to be FPT if no precedence delays are assumed in [START_REF] Hanen | Parameterized complexity of singlemachine scheduling with precedence, release dates and deadlines[END_REF]. In addition to pathwidth µ the slack σ was considered by several authors as an extra property around time windows. The slack corresponds to the maximum number of starting times for a job minus one. A FPT with the tuple of parameters "slack and pathwidth" (or "maximum processing time and pathwidth") was proposed in [START_REF] Hanen | Fixed-Parameter tractability of scheduling dependent typed tasks subject to release times and deadlines[END_REF] for a parallel machine scheduling problem with precedence and time windows. For a single machine problem with job rejection criteria a FPT with parameters slack and pathwidth has also been proposed [START_REF] Baart | Single-machine scheduling with release times, deadlines, setup times, and rejection[END_REF].

The aim of this paper is to analyze the parameterized complexity of a single machine scheduling unit execution time jobs with precedence delays and time windows parameterized by the slack alone. To the best of our knowledge this parameter has not been investigated for this problem yet. In fact our goal is to establish as accurately as possible the boundary between the FPT problems and the others. Moreover we include the case of maximum delays in our study, which is usually less studied than minimum and exact delays.

Our contribution first establishes a relation between the slack and the pathwidth, leading to the following property: if a problem is FPT parameterized by the pathwidth then it is also FPT for the slack. Conversely if it appears to be NP-hard for a bounded slack, then it is for a bounded pathwidth. This implies that results already known for the pathwidth can be transferred to the slack. In Section 2 we present our notations, the parameters and the relation between slack and pathwidth.

Then we show in Section 3 that scheduling coupled tasks with unit execution time on a single machine with minimum, maximum or exact delays is para-NPhard with respect to the slack by establishing the NP-hardness of these problems with slack value σ = 2. In Section 4 we provide a polynomial algorithm for the problem with general precedence graph and slack value bounded by 1 by showing an equivalence to the 2-sat problem. Finally in Section 5 we draw some perspectives.

Definitions and parameters

Preliminary definitions

In this paper we study the problem denoted by 1|prec(ℓ i,j ), p j = 1, r j , d j |⋆ in the standard notation of Graham [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF]. An instance of this problem is characterized by a set T of n unit execution time jobs. Each job J in T has a processing time p(J) = 1, a release date r(J) and a deadline d(J). Moreover we consider an acyclic precedence graph prec representing precedence relations between the jobs in T . Each arc a = (J, J ′ ) in prec is valued by a nonnegative integer ℓ a . A schedule s defines for each job J a starting time s(J) so that r(J) ≤ s(J) < d(J) and for any arc a = (J, J ′ ) in prec:

minimum delays: s(J ′ ) ≥ s(J) + 1 + ℓ a maximum delays: s(J ′ ) ≤ s(J) + 1 + ℓ a exact delays: s(J ′ ) = s(J) + 1 + ℓ a
Definition 1 (Proper delay). Given an arc a = (J, J ′ ) the delay ℓ a is called proper when ℓ = r(J ′ ) -r(J) -1.

Lemma 1. In any feasible schedule if a job J is scheduled at time r(J)+k, k ≥ 0 and there is a proper delay ℓ between J and another job J ′ , then J ′ must be scheduled at time:

1. r(J ′ ) + k or later if ℓ is a minimum delay, 2. r(J ′ ) + k or earlier if ℓ is a maximum delay, 3. exactly r(J ′ ) + k if ℓ is an exact delay.
Proof. Let s be a feasible schedule.

1. With minimum delays we have:

s(J ′ ) ≥ s(J) + 1 + ℓ.
With s(J) = r(J) + k and ℓ = r(J ′ ) -r(J) -1 we have:

s(J ′ ) ≥ [r(J) + k] + 1 + [r(J ′ ) -r(J) -1] = r(J ′ ) + k. 2.

and 3. are proved the same way. ⊓ ⊔

A large part of this paper is devoted to the special case of coupled tasks. A coupled task is a set of two unit execution time jobs linked by an arc of the precedence graph. So a coupled task can be described by a triplet (J 1 , ℓ, J 2 ). In scheduling problems with coupled tasks we assume that each job has its time window and that no precedence constraint exists between different coupled tasks.

Definition 2 (Properly coupled task). A coupled task (J 1 , ℓ, J 2 ) with the same time window length α = d(J 1 ) -r(J 1 ) = d(J 2 ) -r(J 2 ) is called properly coupled if the delay ℓ between both jobs is proper. Then this coupled task can be represented by the triple ⟨r(J 1 ), r(J 2 ), α⟩.

We now introduce a notion that will be used in the complexity reductions.

Definition 3 (Loop of properly coupled tasks). A loop of properly coupled tasks for minimum delays (resp. maximum delays) is composed by two set of properly coupled tasks with time windows of length 2; set F with f coupled task is called the forward phase of the loop, and set B with b coupled tasks its backward phase. F = {⟨r(F (i)), r(F ′ (i)), 2⟩, i ∈ {1, . . . , f }} B = {⟨r(B(i)), r(B ′ (i)), 2⟩, i ∈ {1, . . . , b}}. The sets have the following properties:

-Time windows of two consecutive forward tasks intersect: ∀i ∈ {1, . . . , f -1}, r(

F (i + 1)) = r(F ′ (i)) + 1 (resp. r(F (i + 1)) = r(F ′ (i)) -1); -Similarly, ∀i ∈ {1, . . . , b -1}, r(B(i + 1)) = r(B ′ (i)) + 1 (resp. r(B(i + 1)) = r(B ′ (i)) - 1
); -The first and the last time windows of forward and backward phase coincide:

r(F (1)) = r(B(1)) and r(F ′ (f )) = r(B ′ (b))
. Now looking at Figure 1 which depicts a loop with two forward tasks and one backward task, the scheduled time of F (1) is accurately propagated throughout the whole loop with minimum delays no matter if it is scheduled left or right. Thus a loop can be seen as an on/off switch which can be set by any job in the loop. This property is extended to any loop in Lemma 2. Lemma 2. A loop of coupled tasks with minimum (resp. maximum) delays has exactly two feasible schedules. The first one is the schedule where every job of F is scheduled to the right (resp. the left) of its time window while every job of coupled tasks of B is scheduled to the left (resp. the right) of its time window. Then we say that the loop is ON. The second one is where all jobs in and F and B are scheduled the other way around. Then we say that the loop is OFF.

Proof. We prove the lemma in the minimum delays case (similar arguments hold for the maximum/exact delays case). Notice that for any coupled task of F if the second job of the coupled task is performed to the right of its time window at r(F ′ (i)) + 1 then the first job of the next coupled task can only be performed at r(F (i + 1)) + 1. So this "right-shift" information is propagated along F until the last forward job, which is also executed at the right of its time window. Similarly if the second job is performed to the left of its time window at r(F ′ (i)) then the first job of the same coupled tasks is performed to the left of its interval at r(F (i)). Now this implies that the previous coupled task is also performed to the left, at r(F ′ (i -1)), and this can be propagated to the left. The same argument holds for B. Now since the first time window of length 2 is common to the first job of both F and B, there can be only two possibilities: either the first job of B starts first and then the first job of F is scheduled, or the reverse case. In the first case, since we have minimum delays, this implies that all jobs of F are scheduled to the right of their time window. Now in the last time window of both chains, if the job F ′ (f ) of F is scheduled to the right, the job B ′ (b) of B that shares the same interval is scheduled to the left of its time window, and so are all the coupled tasks of B. Hence we are in the ON state of the loop. A symmetric argument holds for the OFF state. ⊓ ⊔

Slack vs pathwidth

Let us now recall the definition of the two parameters we use in this paper for our parameterized complexity analysis:

pathwidth: at most µ + 1 job time windows intersect at each time t.

slack: for all jobs J ∈ T the number of starting times minus one is given by d(J) -p(J) -r(J), so we have: d(J) -p(J) -r(J) ≤ σ.

By using these definitions a relation between both parameters in feasible schedules can be established.

Theorem 1. If a single machine scheduling instance with time windows is feasible, then µ ≤ 2σ.

Proof. By the definition of slack σ:

r(J) ≥ d(J) -p(J) -σ d(J) ≤ r(J) + p(J) + σ (1)
Let J be a job and t be a time slot. If t is part of interval [r(J), d(J)) then:

t < d(J) t ≥ r(J) (2)
Then by using both inequalities on the definition of slack σ we get:

r(J) > t -p(J) -σ d(J) ≤ t + p(J) + σ (3)
This means that whenever job J is scheduled, p(J) consecutive time slots will be taken by J in time interval [t -σ -p(J) + 1, t + σ + p(J)). Thus at least one time unit will be taken by J in time interval [t -σ, t + σ + 1). Since we only have one machine, this means that at most 2σ + 1 jobs can have t be a part of their time window [r(J), d(J)) in any feasible schedule of this instance. This yields the wanted inequality: µ ≤ 2σ.

⊓ ⊔

3 Hardness reductions with with σ = 2

In this section we prove para-NP-completeness of our three single machine scheduling problems parameterized by slack σ. Then we infer para-NP-completeness of the variants with pathwidth µ as the parameter.

We use the following result from Flum and Grohe's book [START_REF] Flum | Parameterized complexity theory[END_REF]: if a (nontrivial) problem P is NP-complete with a fixed value of some parameter k, then the parameterized problem (P, k) is para-NP-complete. For all three delay types X ∈ {min, max, ex} we prove the scheduling problem 1|(1, ℓ X , 1), r j , d j |⋆ to be NPcomplete with σ = 2.

The three problems are all trivially in NP by guessing the starting time of each job then checking if this leads to a feasible schedule. For the hardness proofs all reductions will start from the (strongly) NP-hard 3-Coloring graph problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. Let G = (V, E) be the input graph (with no self-loops). Let v 0 , . . . , v n-1 be the vertices in V and e 0 , . . . , e m-1 be the edges in E. Let n = |V | and m = |E|. The colors will be named 0, 1 and 2.

(. . .) (. . .) 0 1 2 (. . .) (. . .) (. . .) Color loop Li,0 (forward)
Color loop Li,1

Color loop Li,2

Color choice tasks

(0) (1)
(

(3)

Color loops Li,0, Li,1, Li,2 (backward)
Fig. 2. The color choice segment corresponding to node vi in the reduction with minimum delays. Color loop Li,1 is ON and the other two are OFF.

Outline of the reductions

For every delay type X ∈ {min, max, ex} an instance of 1|(1, ℓ X , 1), r j , d j |⋆ is built. The goal is to represent the color choice of each node v i in graph G and check that there is no edge e j in E where both nodes of the edge choose the same color. Time segments: We segment time into (m + 2) segments: a color choice segment [0, 25n), m edge check segments along [25n, 25(n + m)) and a closing segment [25(n+m), 25(n+2m)]. Each node v i has a time segment [25i, 25(i+1)) dedicated to its color choice -see Figure 2 -while each edge e j is represented by time segment [25(n + j), 25(n + j + 1)) -see Figure 3.

Color loops: Color choices will be propagated to edge check segments using loops of properly coupled tasks. We define for each node v i of G and each color k ∈ {0, 1, 2} a color loop L i,k . The first time window of the loop is in the beginning of the color choice segment and the last time window is in the closing segment. This loop being ON corresponds to node v i choosing color k. This is what will be used to connect color choices with our edge checks. The different parts of color loops L i,0 , L i,1 and L i,2 can be seen in Figures 2, 3 and4.

25(n + j)

25(n + j) + 8 25(n + j) + 16 25(n + j + 1) (. . .)

(. . .) (. . .) (. . .) (. . .) (. . .) (. . .) (. . .) (. . .) (. . .) (. . .) (. . .) Color loop Li 1,0 (forward)
Color loop Li 1 ,1 (forward)

Color loop Li 1 ,2 (forward)
Edge check tasks Color choice tasks: For each node v i a color choice is represented by a properly coupled task (C i (3), ℓ X , C ′ i (3)) of time window length 3. Then this coupled task is connected to the three corresponding color loops L i,k using a few extra properly coupled tasks of time window length 2. The color choice is propagated the same way as in the color loops, i.e. with an alternation of proper delays and time windows overlaps. The goal is that if job C i (3) is scheduled at r(C i (3)) + k in a feasible schedule (with k ∈ {0, 1, 2}), then color loop L i,k has to be in its ON state.

Color loop Li 2 ,0 (backward) Color loop Li 2 ,1 (backward)
Color loop Li 2 ,2 (backward)
Figure 2 shows the color choice tasks and their interactions with the color loops in the minimum delays case. In this figure color task C i (3) starts at time r(C i (3)) + 1, which indeed forces color loop L i,1 to be ON if we want a feasible schedule.

25(n + m

+ i) 25(n + m + i + 1) (. . .) (. . .) (. . .) (. . .) (. . .) (. . .) Color loops Li,0, Li,1, Li,2 (forward)
Color loops Li,0, Li,1, Li,2 Edge check tasks: Recall that for each color k ∈ {0, 1, 2} and each edge of G we defined a time segment where we check that both nodes of the edge do not have the same color k. For each edge e j = {v i1 , v i2 } with i 1 < i 2 , an edge check for a given color k ∈ {0, 1, 2} is represented by a properly coupled task (E j (k), ℓ X , E ′ j (k)) of time window length 2. This coupled task will overlap with the forward phase of loop L i1,k and the backward phase of loop L i2,k . An example with minimum delays is given in Figure 3. Color loop L i1,k in its ON state forces coupled task (E j (k), ℓ X , E ′ j (k)) into one configuration, while color loop L i2,k in its ON state forces it into another configuration. This way having both loops ON makes it impossible to schedule these edge check tasks while at most one of them being ON is allowed.

For example in Figure 3 color loop L i1,0 is ON and one of its forward tasks forces coupled task (E j (0), ℓ min , E ′ j (0)) to be scheduled at their release date plus one. This forces color loop L i2,0 to be OFF in a feasible schedule -which it is in the figure. Similarly color loop L i2,2 is ON and this time it is one of its backward tasks which forces coupled task (E j (2), ℓ min , E ′ j (2)) to be scheduled at their release date. This forces color loop L i1,2 to be OFF in a feasible schedule -which it is in the figure.

3.2 NP-hardness of 1|(1, ℓ min , 1), r j , d j |⋆ with σ = 2
We build an instance of 1|(1, ℓ min , 1), r j , d j |⋆ with σ = 2. See Figures 2, 3 and4 for an illustration of the color choice segment, an edge check segment and the closing segment respectively. Forward phase F i,k : According to Definition 3 we define F i,k a set of properly coupled tasks representing the forward phase of loop L i,k . Its purpose is to propagate the color choice of node v i to the edge check segments of edges e = {v i , v j } such that i < j. Definition 4 (Forward phase F i,k ). Let i ∈ [0, n -1] and k ∈ {0, 1, 2}. F i,k contains the following properly coupled tasks:

in the color choice segment: a properly coupled task (F i,k (0), ℓ min , F ′ i,k (0)):

• case F i,0 : ⟨25i, 25i + 9, 2⟩, • case F i,1 : ⟨25i + 2, 25i + 17, 2⟩, • case F i,2 : ⟨25i + 4, 25i + 22, 2⟩.
-If there is no edge e = {v i , v j } such that i < j:

• between the color choice segment and the the closing segment: a properly coupled task

(F i,k (1), ℓ min , F ′ i,k (1)) = ⟨r(F ′ i,k (0)) + 1, 25(n + m + i) + 2k
, 2⟩ -Else: let j 1 < . . . < j r be the indices of the edges e jq = {v i , v j } such that i < j.

• between the color choice segment and the edge check segment of edge e j1 : a properly coupled task

(F i,k (1), ℓ min , F ′ i,k (1)) = ⟨r(F ′ i,k (0)) + 1, 25(n + j 1 ) + 8k, 2⟩ • for each q ∈ [1, r -1],
between the edge check segments of edges e jq and e jq+1 : a properly coupled task (F i,k (q + 1), ℓ min , F ′ i,k (q + 1)) = ⟨r(F ′ i,k (q)) + 1, 25(n + j q+1 ) + 8k, 2⟩. • between the edge check segment of edge e jr and the closing segment: a properly coupled task

(F i,k (r + 1), ℓ min , F ′ i,k (r + 1)) = ⟨r(F ′ i,k (r)) + 1, 25(n + m + i) + 2k, 2⟩.
Backward task set B i,k : According to Definition 3 we define B i,k a set of properly coupled tasks representing the backward phase of loop L i,k . Its purpose is to propagate the color choice of node v i to the edge check segments of edges e = {v i , v j } such that i > j.

Definition 5 (Backward task set B i,k ). Let i ∈ [0, n -1] and k ∈ {0, 1, 2}. B i,k contains the following properly coupled tasks:

-If there is no edge e = {v i , v j } such that i > j:

• between the color choice segment and the the closing segment: a properly coupled task

(B i,k (0), ℓ min , B ′ i,k (0)) = ⟨25i + 2k, 25(n + m + i) + 2k, 2⟩.
-Else: let j 1 < . . . < j r be the indices of the edges e jq = {v i , v j } such that i > j.

• between the color choice segment and the edge check segment of edge e j1 : a properly coupled task

(B i,k (0), ℓ min , B ′ i,k (0)) = ⟨25i + 2k, 25(n + j 0 ) + 8k + 5, 2⟩, • for each q ∈ [1, r -1],
between the edge check segments of edges e jq and e jq+1 : a properly coupled task (B i,k (q), ℓ min , B ′ i,k (q)) = ⟨r(B ′ i,k (q -1)) + 1, 25(n + j q ) + 8k + 5, 2⟩. • between the edge check segment of edge e jr and the closing segment: a properly coupled task a properly coupled task

(B i,k (r), ℓ min , B ′ i,k (r)) = ⟨r(B ′ i,k (r -1)) + 1, 25(n + m + i) + 2k, 2⟩. Definition 6 (Color loop L i,k ). Let i ∈ [0, n -1] and k ∈ {0,
(C i (0), ℓ min , C ′ i (0)) = ⟨25i + 6, 25i + 8, 2⟩, -a properly coupled task (C i (1), ℓ min , C ′ i (1)) = ⟨25i + 6, 25i + 12, 2⟩, -a properly coupled task (C i (2), ℓ min , C ′ i (2)) = ⟨25i + 14, 25i + 16, 2⟩, -a properly coupled task (C i (3), ℓ min , C ′ i (3)) = ⟨25i + 13, 25i + 20, 3⟩. Lemma 3. Let k ∈ {0, 1, 2}.
In any feasible schedule if color choice task C i (3) starts at time r(C i (3)) + k then color loop L i,k must be ON.

Proof. We show that if color choice task which corresponds to r(C ′ i (1)). Then with its time window of length 2 this task must be scheduled at its release date. By the proper delay the other end C i (1) of this properly coupled task must also be scheduled at its release date. Then task C i (0), which has the same time window of length 2 as task C i (1), must be scheduled at its release date plus one. By the proper delay and the time window of length 2 the other end C ′ i (0) must be scheduled at time r(C ′ i (0)) + 1 = 25i + 9. By Definition 4 this corresponds to r(F ′ i,0 (0)). With this forward task having a time window of length 2 it must start at time r(F ′ i,0 (0)) + 1.

C i (3) starts at time r(C i (3)) + k then forward task F ′ i,k (0) must start at time r(F ′ i,k (1)
This concludes the proof of this lemma.

Definition 8 (Edge check task set E j ). Let j ∈ [0, m -1]. E j is a set of three properly coupled tasks: for each k ∈ {0, 1, 2} we have a properly coupled task (E j (k), ℓ min , E ′ j (k)) = ⟨25(n + j) + 8k + 2, 25(n + j) + 8k + 4, 2⟩.

Remark 1. This scheduling instance indeed has slack 2: there are n properly coupled tasks (C i (3), ℓ min , C ′ i (3)) with a time window length of 3 and all the other tasks have a time window length of 2.

Proposition 1. G is 3-colorable if and only if there exists a feasible schedule for this instance of 1(1, ℓ min , 1), r j , d j |⋆.

Proof. ( =⇒ ) Suppose we have (c 0 , . . . , c n-1 ) ∈ {0, 1, 2} n a 3-coloring of G where vertex v i has color c i . We propose the following schedule:

color loops L i,ci are ON while all the others are OFF color choice coupled task (C i (3), ℓ min , C ′ i (3)) are scheduled at their release date plus c i . The other three are scheduled so that they do not interfere with the OFF color loops:

• case c i = 0: (C i (1), ℓ min , C ′ i (1)) and (C i (2), ℓ min , C ′ i (2)
) at their release date, (C i (0), ℓ min , C ′ i (0)) at their release date plus one,

• case c i = 1: (C i (0), ℓ min , C ′ i (0)) at their release date, (C i (1), ℓ min , C ′ i (1)) and (C i (2), ℓ min , C ′ i (2)
) at their release date plus one,

• case c i = 2: (C i (0), ℓ min , C ′ i (0)) and (C i (2), ℓ min , C ′ i (2)
) at their release date, (C i (1), ℓ min , C ′ i (1)) at their release date plus one. given an edge e j = {v i1 , v i2 } with i 1 < i 2 :

• schedule edge check coupled task (E j (c i1 ), ℓ min , E ′ j (c i1 )) at their release date plus one, • schedule edge check coupled task (E j (c i2 ), ℓ min , E ′ j (c i2 )) at their release date,

• schedule the remaining edge check coupled task of this edge check segment at their release date.

We show that this schedule is feasible. First we check the color choice segment. Let i ∈ [0, n -1]. For all three possible color choices c i only one color choice task might interfere with a color loop: this task is scheduled at the release date of task F ′ i,k (0). However color loop L i,ci is ON, so F ′ i,k (0) is scheduled at its release date plus one and the machine constraint is fulfilled in this segment of the schedule. Now let j ∈ [0, m -1]. Let edge e j = {v i1 , v i2 } with i 1 < i 2 . In the corresponding edge check segment only two color loops are ON: L i1,ci 1 the forward way and L i2,ci 2 the backward way. Thus in this edge check segment only two tasks from the color loops might interfere with an edge check task. Since (c 0 , . . . , c n-1 ) is a 3-coloring we have c i1 ̸ = c i2 and so two different edge check coupled tasks are involved. On the one hand let q F be the index such that e j is the q th F edge in the definition of the forward tasks. Then task F i,ci 1 (q F + 1) is scheduled at the release date of edge check task E j (c i1 ) while the latter is scheduled at its release date plus one, so no interference there. On the other hand let q B be the index such that e j is the q th B edge in the definition of the backward tasks. Then task F ′ i,ci 2 (q B ) is scheduled at the release date of edge check task E ′ j (c i2 ) plus one while the latter is scheduled at its release date, so no interference there either. Thus the machine constraint is fulfilled in all edge check segments of the schedule. Finally all color loops are either ON or OFF so the machine constraint is also fulfilled in the closing segment. Thus the proposed schedule is feasible.

( ⇐= ) Suppose we have a feasible schedule. For all i ∈ [0, n -1] let s i ∈ {0, 1, 2} be such that r(C i (3)) + s i is the starting time of color choice task C i (3). We show that (s 0 , . . . , s n-1 ) is a 3-coloring of G. By contradiction suppose there is an edge e j = {e i1 , e i2 } such that s i1 = s i2 . Let k = s i1 = s i2 . Then by Lemma 3 both color loops L i1,k and L i2,k must be ON. Then all configurations of edge check task (E j (k), ℓ min , E ′ j (k)) are blocked: task E j (k) can only be scheduled at its release date plus one while task E ′ j (k) can only be scheduled at its release date. Then the proper minimum delay cannot be abided by. Thus the schedule is not feasible, which leads to a contradiction. Thus (s 0 , . . . , s n-1 ) is indeed a 3-coloring of G.

This proves that 1|(1, ℓ min , 1), r j , d j |⋆ with σ = 2 is NP-hard, which concludes the para-NP-completeness proof of the corresponding parameterized problem.

Theorem 2. 1|(1, ℓ min , 1), r j , d j |⋆ is para-NP-complete parameterized by slack σ.

NP-hardness of 1|

(1, ℓ max , 1), r j , d j |⋆ with σ = 2

We build an instance of 1|(1, ℓ max , 1), r j , d j |⋆ with σ = 2. See Figures 5, 6 and7 for an illustration of the color choice segment, an edge check segment and the closing segment respectively. The reduction is very similar to the minimum delays case, except most jobs have their window slightly shifted in order to propagate color choices with maximum delays instead of minimum ones. Definition 9 (Forward task set F i,k ). Let i ∈ [0, n -1] and k ∈ {0, 1, 2}. F i,k contains the following properly coupled tasks:

in the color choice segment: a properly coupled task (F i,k (0), ℓ max , F ′ i,k (0)):

• case F i,0 : ⟨25i, 25i + 13, 2⟩, • case F i,1 : ⟨25i + 2, 25i + 18, 2⟩, • case F i,2 : ⟨25i + 4, 25i + 22, 2⟩.
-If there is no edge e = {v i , v j } such that i < j:

• between the color choice segment and the the closing segment: a properly coupled task

(F i,k (1), ℓ max , F ′ i,k (1)) = ⟨r(F ′ i,k (0)) -1, 25(n + m + i), 2⟩ -
Else: let j 1 < . . . < j r be the indices of the edges e jq = {v i , v j } such that i < j.

• between the color choice segment and the edge check segment of edge e j1 : a properly coupled task

(F i,k (1), ℓ max , F ′ i,k (1)) = ⟨r(F ′ i,k (0)) -1, 25(n + j 1 ) + 8k + 2, 2⟩ 25i
Color loop Li,2

Color choice tasks

(0) (1) (2)
(3)

Color loops Li,0, Li,1, Li,2 (backward)
Fig. 5. The color choice segment corresponding to node vi in the reduction with maximum delays. Color loop Li,1 is ON and the other two are OFF.

• for each q ∈ [1, r -1], between the edge check segments of edges e jq and e jq+1 : a properly coupled task (F i,k (q + 1), ℓ max , F ′ i,k (q + 1)) = ⟨r(F ′ i,k (q)) -1, 25(n + j q+1 ) + 8k + 2, 2⟩ • between the edge check segment of edge e jr and the closing segment: a properly coupled task

(F i,k (r + 1), ℓ max , F ′ i,k (r + 1)) = ⟨r(F ′ i,k (r)) -1, 25(n + m + i) + 2k, 2⟩. Definition 10 (Backward task set B i,k ). Let i ∈ [0, n -1] and k ∈ {0, 1, 2}.
B i,k contains the following properly coupled tasks:

-If there is no edge e = {v i , v j } such that i > j:

• between the color choice segment and the the closing segment: a properly coupled task

(B i,k (0), ℓ max , B ′ i,k (0)) = ⟨25i + 2k, 25(n + m + i) + 2k, 2⟩.
-Else: let j 1 < . . . < j r be the indices of the edges e jq = {v i , v j } such that i > j.

Checking that nodes vi 1 and vi 2 do not choose color 0 at the same time Checking that nodes vi 1 and vi 2 do not choose color 1 at the same time Checking that nodes vi 1 and vi 2 do not choose color 2 at the same time Fig. 6. The edge check segment corresponding to edge ej = {vi 1 , vi 2 } with i1 < i2 in the reduction with maximum delays. Here color loops Li 1 ,1 and Li 2 ,0 are ON and the other four are OFF.

• between the color choice segment and the edge check segment of edge e j1 : a properly coupled task

(B i,k (0), ℓ max , B ′ i,k (0)) = ⟨25i + 2k, 25(n + j 1 ) + 8k + 5, 2⟩, • for each q ∈ [1, r -1],
between the edge check segments of edges e jq and e jq+1 : a properly coupled task

(B i,k (q), ℓ max , B ′ i,k (q)) = ⟨r(B ′ i,k (q -1)) -1, 25(n + j s+1 ) + 8k + 5, 2⟩.
• between the edge check segment of edge e jr and the closing segment: a properly coupled task

(B i,k (r), ℓ max , B ′ i,k (r)) = ⟨r(B ′ i,k (r -1)) -1, 25(n + m + i) + 2k, 2⟩. Definition 11 (Color loop L i,k ). Let i ∈ [0, n -1] and k ∈ {0, 1, 2}. Color loop L i,k is the combination of properly coupled task sets F i,k and B i,k .
We define the following states:

1. the ON state:

(a) all tasks F in F i,k are scheduled at time r(F ), (b) all tasks B in B i,k are scheduled at time r(B) + 1,

the OFF state:

(a) all tasks F in F i,k are scheduled at time r(F ) + 1, (b) all tasks B in B i,k are scheduled at time r(B).

Definition 12 (Color choice task set C i ). Let i ∈ [0, n -1]
. C i is a set of four properly coupled tasks:

a properly coupled task

(C i (0), ℓ max , C ′ i (0)) = ⟨25i + 8, 25i + 14, 3⟩, -a properly coupled task (C i (1), ℓ max , C ′ i (1)) = ⟨25i + 8, 25i + 19, 2⟩, -a properly coupled task (C i (2), ℓ max , C ′ i (2)) = ⟨25i + 6, 25i + 23, 2⟩, -a properly coupled task (C i (3), ℓ max , C ′ i (3)) = ⟨25i + 6, 25i + 10, 2⟩. Lemma 4. Let k ∈ {0, 1, 2}.
In any feasible schedule if color choice task C i (0) starts at time r(C i (0)) + k then color loop L i,k must be ON.

Proof. This is proved in the same fashion as Lemma 3.

Definition 13 (Edge check task set E j ). Let j ∈ [0, m -1]. E j is a set of three properly coupled tasks: for each k ∈ {0, 1, 2} we have a properly coupled task (E j (k), ℓ max , E ′ j (k)) = ⟨25(n + j) + 8k, 25(n + j) + 8k + 6, 2⟩. Remark 2. This scheduling instance indeed has slack 2: there are n properly coupled tasks (C i (0), ℓ max , C ′ i (0)) with a time window length of 3 and all the other tasks have a time window length of 2.

Proposition 2. G is 3-colorable if and only if there exists a feasible schedule for this instance of 1|(1, ℓ max , 1), r j , d j |⋆.

Proof. This is proved in the same fashion as Lemma 1.

This proves that 1|(1, ℓ max , 1), r j , d j |⋆ with σ = 2 is NP-hard, which concludes the para-NP-completeness proof of the corresponding parameterized problem.

Theorem 3. 1|(1, ℓ max , 1), r j , d j |⋆ is para-NP-complete parameterized by slack σ.

NP-hardness of 1|

(1, ℓ ex , 1), r j , d j |⋆ with σ = 2
We build an instance of 1|(1, ℓ ex , 1), r j , d j |⋆ with σ = 2. One can simply take the reduction with minimum delays and replace the minimum delays with exact ones. Then the whole reduction works the same way: color loops still have the same two possible schedules, each color choice is propagated through color choice tasks and color loops the exact same way, and the ON color loops force the edge check tasks to be scheduled at the exact same configurations.

This proves that 1|(1, ℓ ex , 1), r j , d j |⋆ with σ = 2 is NP-hard, which concludes the para-NP-completeness proof of the corresponding parameterized problem.

Corollary 1. 1|(1, ℓ ex , 1), r j , d j |⋆ is para-NP-complete parameterized by slack σ.

25(n + m

+ i) 25(n + m + i + 1) (. . .) (. . .) (. . .) (. . .) (. . .) (. . .)
Color loops Li,0, Li,

Color loops Li,0, Li,

Fig. 7. The closing segment corresponding to node vi in the reduction with maximum delays. Here color loop Li,1 is OFF and the other two are ON.

Implications to parameter µ

With Theorem 1 we know that our three results of para-NP-completeness with slack σ imply para-NP-completeness with pathwidth as the parameter instead.

In fact upon closer inspection of our reductions, there were never more than two time windows overlapping at any time. This leads to the following result:

Corollary 2. The problems 1|(1, ℓ X , 1), r j , d j |⋆ with X ∈ {min, max, ex} and µ = 1 are (strongly) NP-hard. As a consequence they are all para-NP-complete parameterized by µ.

4 Polynomial-time solvability with σ = 1

In this section delays can be exact, minimum or maximum. We prove polynomialtime solvability of the scheduling problem 1|prec, p i = 1, ℓ ij , r i , d i , σ = 1|⋆ by reducing it to 2-SAT. We achieve this in two steps: first we reduce from a slightly more restricted scheduling problem with proper delays and all time windows of length 2, with a straightforward reduction to 2-SAT. Then we show how to convert a general instance of this problem into a restricted one equivalent to it in terms of feasibility.

Reduction with time windows of length exactly 2 and proper delays

Let us consider an instance of our restricted problem. The set of n jobs is denoted by T . Each job J must be performed in a time window of length 2 [r(J), r(J)+2).

We consider an acyclic graph G of precedence constraints with proper delays, so that for each arc a = (J i , J j ) in G, its delay ℓ a = r(J j ) -r(J i ) -1.

We build a boolean formula in conjunctive normal form with only clauses of two literals. This formula will encode our scheduling instance and we want it to be satisfiable if and only if the scheduling instance is feasible.

We have n boolean variables x i , one per job in the scheduling instance. All jobs have exactly two possible starting times, which correspond to the two possible values of each boolean variable. In particular we want to have:

x i = 0 if job J i is scheduled at time r(J i ) 1 if job J i is scheduled at time r(J i ) + 1 (4)
We now describe the clauses in our boolean formula. For the sake of better understanding clauses will be presented as implications of the form (x =⇒ y) which are indeed equivalent to clauses of two literals (¬x ∨ y) in classical logic. We distinguish two types of clauses: clauses from machine constraints and clauses from precedence constraints. The former will depend on the length of the overlap of time windows while the latter will take into account the nature of the delay (exact, minimum or maximum).

Machine constraints: There are two possibilities, which are described below. Consider two jobs J i , J j ∈ T and without loss of generality assume that r(J i ) ≥ r(J j ). If their two time windows are disjoint, no constraint is needed. Otherwise, there may be two cases:

1. The two jobs have the same time windows, so r(J i ) = r(J j ). Two symmetric clauses are then added (x i =⇒ ¬x j ) and (x j =⇒ ¬x i ) in order to ensure that if J i is scheduled at r(J i ) then J j is scheduled at r(J i ) + 1, and conversely. 2. The jobs time windows overlap on one time unit, so r(J i ) = r(J j ) + 1. We must ensure that if J j is scheduled at r(J j ) + 1 J i is not scheduled at the same time: (x j =⇒ x i ).

Precedence constraints : Consider a precedence constraint a = (J i , J j ) with proper delay ℓ a = r(J j ) -r(J i ) -1. The clauses depend on the nature of the delay (minimum, maximum or exact).

-In case of a minimum delay: x i =⇒ x j (if J i is right shifted in its time window, so is J j ) -In case of a maximum delay: ¬x i =⇒ ¬x j (if J i is left shifted in its time window, so is J j ) -In case of an exact delay, the two clauses associated to minimum and maximum delays are added.

If I is an instance of the scheduling problem, we denote by SAT (I) the 2 -SAT associated instance as described above.

We can now state our lemma:

Lemma 5. An instance I of the one machine scheduling problem with precedence constraints, proper delays and time windows of length 2 is feasible if and only if SAT (I) is satisfiable.

Proof. ( =⇒ ) Let us consider a feasible schedule for the instance I and the instantiation of variables described in Equation ( 4). As the machine constraint is satisfied, no two jobs are scheduled at the same time. So if r(J i ) = r(J j ) and J i is scheduled at r(J i ), then J j is scheduled at r(J i )+1 (and symmetrically). So we cannot have x i ∧x j or ¬x i ∧¬x j . Similarly if r(J j ) = r(J i )+1, then J i and J j are not scheduled both at r(J i ) + 1 so x i ∧ ¬x j is false (and thus the implication is true). Now for a precedence constraint a with a proper delay, depending on the kind of delay, all the implications are true with similar arguments. For example for a minimum delay, if J i is scheduled at r(J i ) + 1 then J j is scheduled at r(J i ) + 1 + 1 + ℓ a = r(J j ) + 1, so x i =⇒ x j is true.

( ⇐= ) Let us consider a feasible instantiation of variables fo SAT (I). We schedule the jobs according to Equation (4). Let us verify that the precedence constraints are satisfied. Let a = (J i , J j ) be a precedence constraint. Assume first that this is a minimum delay. Then if x i = 0, J j can be scheduled in both positions. Otherwise, if x i = 1 then we know by the corresponding clause that x j = 1, so that J j is scheduled at r(J j )+1 = r(J i )+1+1+ℓ a , and the precedence constraint is satisfied. Similar arguments hold for maximum and exact delays. Now assume that there would be two jobs J i , J j scheduled at the same time. These two jobs would have overlapping intervals, and assume that r(J i ) ≥ r(J j ). Assume that both jobs are scheduled at r(J i ). Then if r(J j ) = r(J j ) we would have x i = x j = 0 which is impossible since x j ∨ ¬x i , so that ¬x j ∨ x i = 1. Similarly if r(J i ) = r(J j ) + 1 then x i = 0, x j = 1 which is impossible since the clause (x j =⇒ x i ) is satisfied. Similar arguments hold assuming the two jobs are performed at r(J i ) + 1.

Preprocessing from time windows of length at most 2 and general delays

Starting from a scheduling instance of 1|prec(ℓ i,j ), p j = 1, r j , d j ≤ r j + 2|⋆ there are two missions in this preprocessing step:

1. dealing with non-proper delays. 2. removing jobs with a time window of length 1,

1. Dealing with non-proper delays: Consider a precedence relation a = (J i , J j ) with delay ℓ a . Let us consider the case of minimum delays first.

If r(J j ) + 1 < r(J i ) + 1 + ℓ a then no feasible schedule exist: even if J i is scheduled as early as possible, the completion time of J i plus the minimum delay is greater than all possible execution times for J j . Let us assume that r(J j ) -r(J i ) ≥ ℓ a . If r(J j ) -r(J i ) = ℓ a then there is only one possibility to fulfill the precedence constraint: J i should be scheduled at r(J i ) and job J j at r(J j ) + 1. So the time windows of both jobs can be reduced to time windows of length 1: d(J i ) = r(J i ) + 1, r(J j ) = d(J j ) -1. The precedence constraint is then useless. Now assume that r(J j ) -r(J i ) -1 ≥ ℓ a . If the inequality is strict, then in any schedule fulfilling the time windows, this constraint will be satisfied: indeed if J i is scheduled at r(J i ) + 1, then J j can be scheduled at r j and the precedence constraint still holds. Hence in this case, the precedence constraint can be removed without loss of generality. This proves that in case of minimum non proper delays, either we can conclude of infeasibility, or reduce the time windows, or remove the precedence constraint.

Let us now consider the case of maximum delays. Symmetrically, If r(J j ) > r(J i ) + 2 + ℓ a then no feasible schedule exist. If r(J j ) = r(J i ) + 2 + ℓ a , then J i must be scheduled at r(J i ) + 1 while J j must be scheduled at r(J j ), so the time windows of the two jobs can be reduced and the precedence constraint removed. If r(J j ) < r(J i ) + 1 + ℓ a the precedence constraint can be removed: it is fulfilled even if J i is scheduled at r(J i ) and J j at r(J j ) + 1. Hence only proper delays are of interest here.

Finally, in the case of exact delays, which combine the constraints of both minmum and maximum delays, the same property holds. Given an instance I of 1|prec(ℓ i,j ), p j = 1, r j , d j ≤ r j + 2|⋆, either we can conclude of infeasibility, or there is an equivalent instance prop(I) of the problem with proper delays.

2. Removing jobs with a time window of length 1: such a job J j has no other option and books an entire time position for itself since there is a single machine. Thus other jobs will never been scheduled at that time and this time position can be removed in the time windows of the other jobs. If some time window becomes empty, the instance is unfeasible. The iterative application of such transformation of the instance I is called P rune(I). Each time such a transformation is made an equivalent instance with proper delays P rop(P rune(I)) can be computed.

Consider now a precedence constraint a = (J i , J j ) with delay ℓ a = r(J j )r(J i ) -1 as we assumed proper delays.

If the time window of both jobs J i , J j is of length 1, the precedence constraint is always satisfied, so it can be removed from the instance.

If the time window of J i is of length 2 and the other of J j is of length 1, then in the case of a minimum delay or exact delay, the only valid position for J i is left shifted, so that its interval can be reduced to [r(J i ), r(J i ) + 1) and the precedence constraint removed. In the case of a maximum delay, both positions for J i will satisfy the constraint, so the precedence constraint can be removed.

Symmetrically, if the time window of J i is of length 1 and the other of J j is of length 2, then similar arguments lead to either reduce the time window of J j in the case of maximum or exact delays, and in any case to remove the precedence constraint.

Such a transformation of instance I based on the precedence constraints is called P rec(I)

We can then iteratively apply the operations P rune, P rop and P rec either to detect unfeasibility, or to generate an instance such that:

-All delays are proper delays -No time window of length 1 is included in another time window -No job with time window of length 1 has a predecessor nor a successor in the precedence graph.

Such transformation can be done in polynomial time (at each step at least one time window is reduced or one arc is removed) Then, the jobs with time window of length 1 can be removed from the instance, because the feasibility does not rely on them anymore.

This leads to our result: Lemma 6. Considering an instance I of 1|prec(ℓ i,j ), p j = 1, r j , d j ≤ r j + 2|⋆ there is a polynomial algorithm that either indicates that instance I is unfeasible, or computes an instance I ′ in which all delays are proper delays and all time windows are of length 2.

From Lemma 6 we deduce the main result of this section:

Theorem 4. 1|prec(ℓ i,j ), p j = 1, r j , d j ≤ r j + 2|⋆ is polynomially solvable Proof. By applying the transformation described in Lemma 6 we can either detect unfeasibility or generate an equivalent instance with proper delays and time windows of length 2. By Lemma 5, the problem is polynomially solvable.

Conclusion

In this paper we established a relation between the pathwidth and the slack, which are two parameters commonly considered to analyze the parameterized complexity of scheduling problems with time windows. This relation leads to new complexity results: FPT with the slack and para-NP-completeness proofs with the pathwidth. We also proved that scheduling coupled tasks on a single machine with time windows is para-NP-hard parameterized by the slack for either minimum, maximum or exact precedence delays. Lastly we established that the problem with time windows of length at most 2 and precedence delays -minimum, maximum or exact -can be solved in polynomial time.

Looking ahead, we believe that the relations between the parameters usually considered for scheduling problems should be further investigated. In fact the objective would be to replicate the method used in this paper -where a negative complexity result for the slack induced a negative one for the pathwidth -for other existing scheduling parameters. We also feel that the slack should be investigated beyond feasibility. It is likely that some of the existing FPT results could be extended to several optimization criteria. Finally finding a frontier subproblem with a FPT algorithm for the slack while hard when parameterized by the pathwidth would complete the analysis of the relation between the two parameters.

Fig. 1 .

 1 Fig. 1. A loop of properly coupled tasks for minimum delays.

Fig. 3 .

 3 Fig. 3. The edge check segment corresponding to edge ej = {vi 1 , vi 2 } with i1 < i2 in the reduction with minimum delays. Here color loops Li 1 ,0 and Li 2 ,2 are ON and the other four are OFF.

Fig. 4 .

 4 Fig. 4. The closing segment corresponding to node vi in the reduction with minimum delays. Here color loop Li,1 is ON and the other two are OFF.

) + 1 .

 1 Then Lemma 2 will imply that the whole loop L i,k is ON. -Case k = 2 : by the proper delay and the time window of length 3 job C ′ i (3) must be scheduled at time r(C ′ i (3)) + 2 = 25i + 22. However by Definition 4 this corresponds to r(F ′ i,2 (0)), with this task having a time window of length 2. Thus forward task F ′ i,2 (0) must start at time r(F ′ i,2 (0)) + 1. -Case k = 1 : color choice task C i (3) starts at time r(C i (3)) + 1 = 25i + 14 which corresponds to the release date of color choice task C i (2). Then with its time window of length 2 this task must be scheduled at time r(C i (2)) + 1. By the proper delay and the time window of length 2 task C ′ i (2) must be scheduled at time r(C ′ i (2)) + 1 = 25i + 17. By Definition 4 corresponds to r(F ′ i,1 (0)). With this forward task having a time window of length 2 it must start at time r(F ′ i,1 (0)) + 1. -Case k = 0 : color choice task C i (3) starts at time r(C i (3)) = 25i + 13

  1, 2}. Color loop L i,k is the combination of properly coupled task sets F i,k and B i,k . According to Lemma 2 we define the only two ways this loop can be scheduled: 1. the ON state: (a) all tasks F in F i,k are scheduled at time r(F ) + 1, (b) all tasks B in B i,k are scheduled at time r(B), 2. the OFF state: (a) all tasks F in F i,k are scheduled at time r(F ), (b) all tasks B in B i,k are scheduled at time r(B) + 1. Definition 7 (Color choice task set C i ). Let i ∈ [0, n -1]. C i is a set of four properly coupled tasks:


Dhoha Triki

Sandrine Fartek

Benoit Visseaux

Diane Descamps

Anne-Claude Camproux

Leslie Regad
email: leslie.regad@univ-paris-diderot.fr

Characterizing the

Introduction

There are two types of HIV: HIV type 1 (HIV-1) and HIV type 2 (HIV-2) corresponding to distinct simian origins. The drugs used for the treatment of HIV-2 A c c e p t e d M a n u s c r i p t correspond to those developed for HIV-1, targeting various viral proteins: fusion complex, integrase, reverse transcriptase, and protease. HIV-2 is naturally resistant to all non-nucleoside inhibitors of reverse transcriptase or fusion inhibitors [START_REF] Ren | Structure of HIV-2 reverse transcriptase at 2[END_REF][START_REF] Poveda | Enfuvirtide, the first fusion inhibitor to treat HIV infection[END_REF] and also demonstrated reduced susceptibility to protease inhibitors (PIs) (Rodés et al., 2006;[START_REF] Masse | In vitro selection and characterization A c c e p t e d M a n u s c r i p t of human immunodeficiency virus type 2 with decreased susceptibility to lopinavir[END_REF]Desbois et al., 2008;[START_REF] Brower | Inhibition of HIV-2 protease by HIV-1 protease inhibitors in clinical use[END_REF][START_REF] Cavaco-Silva | Mutations selected in HIV-2-infected patients failing a regimen including atazanavir[END_REF][START_REF] Raugi | Complex patterns of protease inhibitor resistance among antiretroviral treatment-experienced HIV-2 patients from senegal: Implications for second-line therapy[END_REF][START_REF] Raugi | Four Amino Acid Changes in HIV-2 Protease Confer Class-Wide Sensitivity to Protease Inhibitors[END_REF]Visseaux et al., 2016). In vivo studies showed that HIV-2 does not produce a stronger immunological response to the more recently developed class of integrase inhibitors than previously observed with PIs [START_REF] Ntemgwa | Nucleoside and nucleotide analogs select in culture for different patterns of drug resistance in human immunodeficiency virus types 1 and 2[END_REF]. Thus, it is still necessary to develop new molecules specifically designed for HIV-2. One approach is based on the identification of new molecules inhibiting HIV-2 protease (PR2).

PR2 is an aspartic protease hydrolyzing the viral Gag and the Gag-Pol precursor polyproteins during the maturation of viral particles. It is a homodimer of 99 residues in each monomer, including the catalytic triplet Asp-Thr-Gly conserved in all aspartic proteases. Substrates and inhibitors bind the PR2 at the interface of the two monomers.

Their bindings are associated with large conformational changes in PR2 resulting in a transition from a semi-open form, allowing the ligand entry, to a closed form, allowing the catalytic action [START_REF] Menéndez-Arias | Antiretroviral therapy and drug resistance in human immunodeficiency virus type 2 infection[END_REF]. Currently, available data about the PR2 deformation upon ligand binding are very limited. A comparison of the PR2 crystallographic structures showed that PR2 in complex with different inhibitors exhibit similar fold with large structural deviations occurring in the elbow region (Tong et al., 1995). More recently, molecular dynamics simulations of PR2 in complex with darunavir (DRV) and amprenavir (APV)i.e., two FDA-approved drugsshowed that residues near the catalytic position D25A/B present a high degree of rigidity, whereas regions around residues 17, 40, 65, and 80 show big dynamics fluctuations (Kar & A c c e p t e d M a n u s c r i p t Knecht 2012; [START_REF] Chen | Revealing origin of decrease in potency of darunavir and amprenavir against HIV-2 relative to HIV-1 protease by molecular dynamics simulations[END_REF]. They also showed that the binding of these two drugs does not produce the same flap move [START_REF] Chen | Revealing origin of decrease in potency of darunavir and amprenavir against HIV-2 relative to HIV-1 protease by molecular dynamics simulations[END_REF]. This different flexible behavior induced by these two drugs could be linked to their different effectiveness against PR2. However, these studies were performed only on PR2 in complex with DRV and APV and did not yield information about deformation induced by other ligands. Thus, a better understanding of flexible behaviors of PR2 for all PIs could help to provide new insights on PI binding and PR2 resistance against commercially available PIs and is important for the design of new fully active PIs.

Currently 19 structures of the wild-type PR2 are available in the Protein Data Bank [START_REF] Berman | The Protein Data Bank[END_REF]. These structures are in different forms (unbound and bound) and are in complex with diverse ligands. Comparing such multiple conformations of a given target is an easy and efficient method to provide information about the target structural variability (Zoete et al., 2002;van Westen et al., 2010;Venkatakrishnan et al., 2012;[START_REF] Regad | Exploring the potential of a structural alphabet-based tool for mining multiple target conformations and target flexibility insight[END_REF]. In our previous study, we characterized the structural asymmetry of PR2 by locating positions exhibiting different local conformations in the two chains of the 19 available PR2 structures (Triki et al., 2018). To do so, we developed a method based on the structural alphabet HMM-SA (Hidden Markov Model -Structural Alphabet), a tool allowing the simplification of protein 3D structures [START_REF] Camproux | A hidden markov model derivated structural alphabet for proteins[END_REF][START_REF] Regad | A hidden Markov model applied to the protein 3D structure analysis[END_REF]. Applying this tool on this large and diverse set of PR2 structures allowed us to localize (i) structural asymmetry specific to particular ligands and (ii) the one conserved across most PR2 structures. In addition, we highlighted the structural asymmetry induced by ligand binding that is important for the ligand recognition and specificity (Triki et al., 2018).

In this study, we focused our investigation on the analysis of PR2 flexibility by exploring the conformational space sampled by the 18 available PR2 structures A c c e p t e d M a n u s c r i p t complexed with various ligands. The SA-conf tool [START_REF] Regad | Exploring the potential of a structural alphabet-based tool for mining multiple target conformations and target flexibility insight[END_REF] was used to compare local structures of each PR2 structures resulting in the location of PR2 structurally variable positions, i.e. positions exhibiting different local conformations in the 18 PR2 structures. Crossing detected PR2 structural variability with its flexibility, quantified by crystallographic B-factor values, allowed us to localize the structural variability induced by PR2 intrinsic flexibility. The study of structural variability of the PR2 binding pocket highlighted the structural variability induced by ligand binding and important for ligand recognition and the adaptation of PR2 to these ligands. We finally explored the link between structural variability and the bound ligands by building a PR2-ligand interaction network. The analysis of this network provided the first PR2 pocket annotation that allows localizing residues for which the conserved conformation is important for ligand binding, as well as residues undergoing structural changes upon ligand binding. Our results could improve the understanding of structural changes of PR2 and its adjustments to recognize and bind various inhibitors, as well as the understanding of PR2 determinants important to explain its resistance to some FDAapproved drugs.

Material and Methods

PR2 set composition

For this study, we used a set developed in our previous study (Triki et al., 2018), composed of the 19 crystallographic structures of wild-type PR2 available in the PDB [START_REF] Berman | The Protein Data Bank[END_REF]. These structures have a good resolution ranging from 1.18 Å to 3 Å and present the same amino-acid sequence except eight PR2 sequences having the mutation K57L experimentally introduced to help the crystallographic process. This A c c e p t e d M a n u s c r i p t originally set contains one unbound PR2 structure, i.e., not in complex with ligand (PDB code: 1HSI), and 18 bound structures. These 18 bound PR2 structures, referred to as the PR2 set, are in complex with various ligands corresponding to three FDAapproved drugs (DRV, APV, and indinavir), two molecules chemically related to DRV, three peptides (including two non-determined ones), and nine chemical molecules (Figure 1).

Quantification of PR2 structural variability using SA-conf tool

We used SA-conf tool [START_REF] Regad | Exploring the potential of a structural alphabet-based tool for mining multiple target conformations and target flexibility insight[END_REF] to extract structurally variable positions defined as positions exhibiting different local backbone conformations in the PR2 set, i.e. the 18 bound PR2 structures. As PR2 is a homodimer, we separately applied SAconf on the 18 chains A and the 18 chains B of each PR2 structure (Figure 2). Supplementary Appendix S1 presents the different steps of the SA-conf software, which are briefly explained in below. Using the structural alphabet HMM-SA [START_REF] Camproux | A hidden markov model derivated structural alphabet for proteins[END_REF][START_REF] Regad | A hidden Markov model applied to the protein 3D structure analysis[END_REF], SA-conf simplifies the 3D structure of each 99-residue chain into sequences of 96 structural letters, where each structural letter describes the local geometry of each four-Cα fragment (Figure 2). Based on these structural-letter sequences, SA-conf quantifies the structural variability of each position by computing the number of structural letters seen at each position within the 18 structures using the Shannon entropy criterion (neq SL ). The higher the value of neq SL is, the more structurally variable the position is, as more PR2 structures exhibit different local conformations (structural letters) at this position.

A c c e p t e d M a n u s c r i p t

Classification of PR2 residues according to their variability or/and their flexibility

2.3.1-Classification of PR2 residues according to their structural variability

First, we classified PR2 positions according to their structural variability quantified by their neq SL value (Figure 2). We identified two position classes: (i) structurally conserved positions and (ii) structurally variable positions. Structurally conserved positions are positions with a neq SL value equal to 1 and they correspond to positions where the 18 PR2 structures exhibit the same conformation. Structurally variable positions have a neq SL value higher than 1 and they correspond to positions where the 18 PR2 structures exhibit different conformations.

2.3.2-Classification of PR2 residues according to their flexibility

Second, we classified PR2 residues according to their flexibility quantified using Bfactor values (temperature factor/atomic displacement factor) extracted from each PDB file. This B-factor value reflects the degree of isotropic smearing of electron density around its center [START_REF] Drenth | Principles of protein X-ray crystallography[END_REF]. We had two choices to quantify the flexibility of PR2 residues. First, we assigned to each residue the B-factor values of its Cα atom, noted Bα. This allowed simplifying PR2 structures using only their Cα atoms as in the quantification of the structural variability of PR2 set. Second, we computed the average B-factor value for each residue using all residue atoms, noted B allAtoms . This allowed considering the flexibility of residue side-chains, which is important in the protein A c c e p t e d M a n u s c r i p t deformation induced by ligand binding. Figure S1 presents the Bα and B allAtoms values for each PR2 residue and shows that these two flexibility parameters are strongly correlated (Pearson correlation coefficient = 0.94). As the induced-fit deformation is important in this study, we chose to quantify the residue flexibility using B allAtoms .

First, the B allAtoms values of all residues in the 18 PR2 structures were computed and then normalized using Equation 1.

B norm (i, j) = [B(i, j)-< Bj >]
s Bj Equation 1B norm (i,j) corresponds to the normalized B allAtoms value of the residue i of the PR2 structure j. B(i,j) is the B allAtoms value of the residue i of the PR2 structure j. <Bj> and σ Bj are the average value and the standard deviation of the B allAtoms values of residues in the PR2 structure j. Average B norm values were then calculated for each PR2 position using B norm values of corresponding residues in the 18 PR2 structures.

A flexible position is defined as a position with an average B norm higher than 0. A rigid position is defined as a position with an average B norm smaller than 0.

Extraction of the different types of PR2 positions/residues according to their variability and their flexibility

Finally, we mixed these two residue classifications to define four residue types:

 Type I: structurally conserved and rigid residues that have a neq SL value equal to 1 and B norm smaller than 0,

A c c e p t e d M a n u s c r i p t

 Type II: structurally conserved and flexible residues that have a neq SL value equal to 1 and B norm higher than 0,  Type III: structurally variable and rigid residues that have a neq SL value higher than 1 and B norm smaller than 0,  Type IV: structurally variable and flexible residues that have a neq SL value higher than 1 and B norm higher than 0.

The structural variability observed for type IV residues is considered as resulting from their intrinsic flexibility. In contrast, structural variability of type III residues could result from induced-fit effects, such as ligand binding or different experimental conditions.

Characterization of PR2 structure

We localized PR2 pocket residues by defining the consensus pocket across the 18 structures as we previously done (Triki et al., 2018). To do so, for each bound PR2 structure, we extracted the ligand-binding pockets by determining PR2 atoms at less than 4.5 Å from the co-crystallized ligand. The consensus-pocket residues across the 18 PR2 complexes were then defined as the 38 residues involved in at least one extracted ligand-binding pocket.

The PR2 structure was also divided into eight structural and functional regions as previously described (Sadiq et al., 2004): the dimerization (1-5 + 96-99), fulcrum (10-23), catalytic (24-30), elbow (37-42), flap (43-58), cantilever (59-72), wall (80-83), and α-helix (87-95) regions (Figure 2).

To study the closeness of each PR2 region, we built the intraproteic hydrogen-bond (Hbond) network of PR2. It is based on the 212 unique intraproteic H-bonds occurring A c c e p t e d M a n u s c r i p t between two PR2 residues and extracted from the 18 PR2 structures using PyMoL software and a distance threshold of 3.5 Å. This network links two PR2 residues if they establish together an H-bond in at least one PR2 structure. It was drawn using the igraph library of R software [START_REF] Csárdi | The igraph software package for complex network research[END_REF].

Construction and analysis of the PR2-ligand interaction network

Construction of the PR2-ligand interaction network and extraction of PR2 residue communities

To study the link between the four defined PR2 residue types and ligand-binding modes, we analyzed the PR2-ligand interaction network according to these four residue types. The PR2-ligand interaction network was built based on 1451 interactions (Hbonds and non-bonded interactions) established between PR2 residues and cocrystallized ligands in the 18 PR2 complexes. These interactions were extracted using LigPlot software (Wallace et al., 1996), see Supplementary Appendix S2.

To facilitate the visualization of the network, the 725 ligand atoms extracted from the 18 bound structures were classified using a hierarchical classification according to their closeness in the 3D space. The obtained tree was cut using an optimal distance criteria of 0.925 to 216 atom clusters. Ligand atoms grouped in the same cluster were named equivalent ligand-atoms and we supposed that they establish similar interactions with PR2 (see Supplementary appendix S2). Using these data interactions were described by four arguments (i) the complex name (PDB code) from the interaction was extracted, (ii) the name ("residue number"_chain) of the PR2 residue involved in the interaction, (iii) the name ("atom number"_chain) of the ligand atom involved in the interaction, and (iv) the cluster to which the ligand atom belongs. We drew the PR2-ligand A c c e p t e d M a n u s c r i p t interaction network using the igraph library of R software [START_REF] Csárdi | The igraph software package for complex network research[END_REF]. A PR2 residue and a ligand-atom cluster was linked by an edge if the residue established an interaction with one ligand atom of this cluster. From this PR2-ligand interaction network, we extracted ten communitiesi.e., sets of nodes strongly connected internallyusing the multi-level modularity optimization algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. In this network, a community groups PR2 pocket residues that interact with similar ligand atoms.

2.5.2-Analysis of the PR2-ligand interaction network according to the residue types.

We analyzed the PR2-ligand interaction network according to the four residue types to assess the link between residue types, the ligand structure, and the established interactions. We first studied the link between residue types and their capacity to establish interactions with ligand by comparing the distribution of the 1451 interactions in the four residue types using a Chi-squared test. Then, we focused on the link between residue types and ligand structure conservation by comparing average size of ligandatom clusters for each residue type using a Kruskal-Wallis test. Finally, we analyzed the link between residue types and the conservation of the PR2-ligand interactions across the 18 PR2 complexes by comparing the average number of complexes exhibiting an interaction for each residue type using a Kruskal-Wallis test. For more explanations, see Supplementary Appendix S3.

A c c e p t e d M a n u s c r i p t

Results & Discussion

Localization and quantification of PR2 structural variability

Local structural changes observed across the 18 available structures of bound PR2 were detected using SA-conf tool [START_REF] Regad | Exploring the potential of a structural alphabet-based tool for mining multiple target conformations and target flexibility insight[END_REF]. SA-conf compares local conformations of each PR2 residue and computes the number of structural conformations observed in each position using the neq SL parameter that quantifies its structural variability (Figure 3).

The PR2 set contains much more structurally variable positions (150 positions with neq SL higher than 1 that exhibit several conformations in the PR2 structures) than conserved positions (42 positions with a neq SL value equal to 1 that exhibit only one conformation in the 18 PR2 structures). A total of 34% of the observed structurally variable positions are highly variable (neq SL ≥ 2), meaning that at least two local conformations are observed at these positions in the PR2 set. Thus, despite their conserved global fold previously described [START_REF] Raugi | Complex patterns of protease inhibitor resistance among antiretroviral treatment-experienced HIV-2 patients from senegal: Implications for second-line therapy[END_REF], the 18 PR2 structures still present structural variability in terms of local conformations. In agreement with previous results about PR2 structural asymmetry (Tong et al., 1993;[START_REF] Mulichak | The crystallographic structure of the protease from human immunodeficiency virus type 2 with two synthetic peptidic transition state analog inhibitors[END_REF]Tong et al., 1995;[START_REF] Chen | Revealing origin of decrease in potency of darunavir and amprenavir against HIV-2 relative to HIV-1 protease by molecular dynamics simulations[END_REF], SA-conf results highlight an asymmetric behavior of PR2. Indeed, we noted that chain A contains less structural conserved positions than chain B (81 versus 72), showing that chain B is more conserved than chain A.

Structurally variable positions are located along the sequence with a strong frequency in the tail, elbow, flap regions, and in the region between the cantilever and the wall (Figure 3). These results are in agreement with the flexible behavior of the regions around residues 17, 40, and 80 observed during molecular dynamics simulations of the PR2 complexed with DRV [START_REF] Kar | Origin of decrease in potency of darunavir and two related antiviral inhibitors against HIV-2 compared to HIV-1 protease[END_REF]. However, we also identified a high frequency of variable positions in the α-helix region (90-93) that have not been detected previously. This highlights the relevance of analyzing several structures of the same target together, as allowed by SA-conf tool, to detect structural variability and changes, particularly in regular secondary structures.

3.2-Putative factors explaining structural variability of the PR2

According to the PR2 set composition, structural changes observed across the 18 structures of PR2 could be explained by several factors: the intrinsic flexibility of PR2, the binding of diverse ligands, the different experimental conditions (pH, space group, …), and crystal packing used to solve structures. To locate structurally variable positions resulting from PR2 intrinsic flexibility, we crossed the structural variability, quantified by the neq SL parameter, and the flexibility, measured by B norm values, of each PR2 position. This resulted in the differentiation of four position/residue types (Table 1).

A total of 66 positions are of type IV, i.e., exhibiting different local conformations in the 18 PR2 structures and a large intrinsic flexibility. The structural changes observed at these positions across the 18 PR2 structures could result from an intrinsic property of PR2 and not from ligands or experimental conditions. 33% of these positions are located in the elbow and flap regions, this is expected due to their implication in the transition from the semi-open (unbound dimer) to closed (bound dimer) conformations of PR2 [START_REF] Kar | Origin of decrease in potency of darunavir and two related antiviral inhibitors against HIV-2 compared to HIV-1 protease[END_REF][START_REF] Chen | Revealing origin of decrease in potency of darunavir and amprenavir against HIV-2 relative to HIV-1 protease by molecular dynamics simulations[END_REF]. They were also A c c e p t e d M a n u s c r i p t located in the fulcrum and cantilever regions (Figure 3 and Table 1). The intraproteic Hbond network between PR2 residues highlights H-bond interactions between some elbow residues (37A-42A), cantilever residues (61A, 63A, 70A, and 72A), and fulcrum residues (14A, 16A, and 18A) (Figure 4). This could indicate that conformational transition in flap regions affects other PR2 regions.

To locate structural variability induced by ligand binding, we analyzed structural variability of the PR2 consensus pocket. This PR2 pocket has an average neq SL of 1.61 ± 0.65, revealing a strong structural variability in this region. A total of 63% of pocket residues are structurally variable (24 positions), with 7 residues having a strong structural variability (neq SL ≥ 2, Figure 3). Five of these latter positions are in the flap region, one in the catalytic region and one in the wall region (Figure 3 and Table 1).

Amongst the 38 pocket residues, 18 are of type III (structurally variable and rigid)

suggesting that the different conformations occurred at these positions result from induced-fit effects. As these positions are within the pocket, we conclude that these structural changes observed across the 18 bound PR2 are directly involved by ligand binding.

In addition, a total of 66 type III positions are located outside the pocket (Table 1). Amongst of them, 10 are neighbors of pocket residues (Figure 3 and Table 1) and their structural variability can be induced directly by ligand binding. Others are located all along the sequence, particularly in the fulcrum, flap, cantilever, and α-helix regions (Figure 3 and Table 1). The observed structural changes at these positions across the 18 PR2 structures could result from crystal packing, different experimental conditions or indirect effects of ligand binding through cooperative moves. Figure 4 highlights a network of intraproteic H-bonds occurring between the pocket residues (23B, 29A, 47B, and 49A) and flap residues (52A and 54B), α-helix residue 88A, and wall residue (83B).

A c c e p t e d M a n u s c r i p t

This corroborates the putative structural-changes induced by ligand binding at these positions. Thus, the structural deformation of pocket residues caused by ligand binding may be accompanied by changes in other regions underlying cooperation between these regions upon ligand binding. Our observations reinforce with a larger dataset and a new approach, the cooperation in motions previously observed using molecular dynamics simulations of PR2 complexed with APV and DRV [START_REF] Kar | Origin of decrease in potency of darunavir and two related antiviral inhibitors against HIV-2 compared to HIV-1 protease[END_REF].

Localization of structurally conserved residues

The PR2 set contains 42 structurally conserved positionsi.e., positions with a neq SL value equal to 1exhibiting only one local conformation in the 18 structures whatever their diversity (different crystal space groups and ligands). According to B norm values, 13 of these conserved positions are flexible (type II residues, Figure 3 and Table 1).

Three of these positions have conformations encoded by one of the structural letters exhibiting the largest structural diversity (F, R, and U) [START_REF] Camproux | A hidden markov model derivated structural alphabet for proteins[END_REF]. Thus, the structural conservation of these positions may be a methodological artefact. The remaining 29 structurally conserved positions correspond to rigid residues; they were characterized as type I residues. Amongst them, 11 are located in the binding pocket, including five in the catalytic region (Figure 3 and Table 1). These positions are structurally conserved in all bound PR2 structures regardless of the co-crystallized ligands. In addition, the structural-letter map of these pockets (Figure 5) showed that these positions exhibit the same local conformation in the unbound PR2 structure. This underlies the important role of these particular local conformations in PR2 structure and function. The structural conservation of these catalytic residues (27B, 28A/B, and 30A/B) is in agreement with the high degree of rigidity previously observed near the A c c e p t e d M a n u s c r i p t catalytic residues D25A/B [START_REF] Chen | Revealing origin of decrease in potency of darunavir and amprenavir against HIV-2 relative to HIV-1 protease by molecular dynamics simulations[END_REF]. Other type I residues, which are also conserved in the unbound PR2 structures (data not shown), are observed all along the PR2 structure: in the flap, fulcrum, cantilever, and α-helix regions (Figure 3 and Table 1). Figure 4 highlights that some type I residues established H-bond with bindingpocket residues, such as α-helix residue 87A/B, residue 33B, and residue 85B that interact with pocket residues 28A/B, 76B, and 33B, respectively. These results suggest that the conserved conformation of these residues is also of importance for the maintenance of the PR2 catalytic-site structure.

-Relationship between binding pocket residue types and ligand diversity and binding mode

We analyzed the link between (i) PR2 variability and ligand structure and (ii) between PR2 variability and ligand binding mode. To do so, we first classified the 725 atoms of the 18 co-crystallized ligands into 216 atom clusters based on their 3D coordinates. We then built the PR2-ligand interaction network based on the 1451 PR2-ligand interactions extracted from the 18 PR2-ligand complexes (Material & Method). This network linked a PR2 residue (square node) to a ligand-atom cluster (circle node) if the PR2 residue establishes an interaction with a ligand atom belonging to the cluster (Figure 6).

The obtained network has a modularity value of 0.62 indicating the strength of division into communities, i.e. PR2 residues and ligand-atom clusters sharing similar interactions. As expected, this network contains most of the 38 ligand-binding pocket residues: only five residues do not establish interaction with at least one ligand (Figure 2).

By taking into account the number of residues in each type, we observed that the four residue types do not establish the same number of interactions: variable residues (type II and type IV) are involved in more interactions than conserved residues but they do not establish more interactions with ligand atoms on average (Table 2). No link was observed neither between residue types and size of cluster of atoms involved in interactions with these residues (Table 2) nor between the residue types and the conservation of interaction across the 18 complexes (Table 2). This indicates that regions conserved across the 18 ligands bound the four residue types and not only PR2

residues with a conserved conformation, i.e., structurally conserved residues (type I and type II residues).

-Relationship between binding pocket residues, their variability, and ligand interactions

In the PR2-ligand interaction network, we identified ten communities, named G1 to G10, with three singletons (G7, G8, and G10) using the multi-level modularity optimization algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] (Figure 7A).

Each community corresponds to a set of nodes strongly connected internally. The composition of communities in terms of residue types is different. For example,

A c c e p t e d M a n u s c r i p t communities G2, G3, G5, G7, G8, and G10 contain only rigid residues suggesting that these regions are important for ligand binding and PR2 activity. Figure 7B shows that communities G3 and G5 residues form the pocket floor, communities G2 and G10 correspond to the right side of the pocket entrance, community G9 constitutes the left wall of the pocket, and the community G1 forms a part of the pocket tip. Community G3 residues interact with ligand regions densely populatedi.e., corresponding to larger atom-clustersand establish most of interactions strongly conserved across the 18 PR2 complexes (Figure 7A). This means that the community G3 residues, corresponding to catalytic residues, bind conserved regions across the 18 ligands with similar interactions. In contrast, communities G4 and G6 residues establish very few interactions with ligands. Most community G1 residues are flexible (residue of type II and IV) and correspond to flap residues. These residues interact with conserved ligand regions through many conserved interactions (Figure 7A). Thus, we conclude that these residues and their flexibility are important for the ligand interaction. Communities G2, G5, and G9 residues establish many interactions with less conserved ligand regions than community G3. Thus, we conclude that these three regions are important for ligand recognition and for the specificity of ligand interactions. For example, the three PR2 structures binding molecules chemically related to the 4-hydroxycoumarin (PDB codes: 3UPJ, 5UPJ, and 6UPJ (Thaisrivongs et al., 1995))) exhibit a particular structural letter at position 84A (community G9 residue of type III) compared to other PR2 structures (Figure 5). This suggests that the specific local conformation observed at position 84A results from backbone deformation specifically induced by the binding of molecules chemically related to the 4-hydroxycoumarin. In addition, the pocket extracted from PR2-APV and PR2-DRV complexesi.e., two PR2 complexed with very similar FDAapproved drugs but presenting totally different effectiveness against PR2 (with a Ki A c c e p t e d M a n u s c r i p t value of 4.4 and 0.17 nM, respectively (Tong et al., 1993;[START_REF] Brower | Inhibition of HIV-2 protease by HIV-1 protease inhibitors in clinical use[END_REF] have pockets with similar structural-letter profiles. The differences between these two pockets are located at structurally variable positions 47A (community G9 residue of type IV) and 48A (community G2 residue of type III) and at two type III residues: 23B (community G3) and 31A (Figure 5). These results suggest that the binding of DRV and APV causes different backbone deformations at these four positions that could lead to the modification of interaction networks. In consequences, they provide a new explanation for their differential action on PR2. This is confirmed by the fact that residue 48A backbone establishes two not bounded interactions with DRV but only one with APV.

Conclusion

In this study, we provided for the first time a large and robust description and characterization of the PR2 structural variability. Using SA-conf tool, we detected the structural variability in a set containing the 18 available PR2 crystallographic structures complexed with various ligands and presenting different experimental conditions (X-ray space group, and resolution). Our study demonstrated that PR2 presents a large structural variability with 66% of its positions characterized as structurally variable.

These structurally variable positions are observed all along the PR2 structures, mainly in the tail, flap, and α-helix regions.

Moreover, our results confirmed that the PR2 pocket is composed of three types of residues: (i) residues having a well-defined conserved conformation that are important for ligand binding and catalytic function, (ii) those that adjust their backbone conformation in response to ligand binding that are important for ligand recognition,

A c c e p t e d M a n u s c r i p t and (iii) those having intrinsic flexibility that could be important for the pocket opening and closing. The analysis of the PR2-ligand interaction patterns allowed us to characterize the ligand-binding site. We showed that the pocket floor, which contains the catalytic region, is the region that establishes the most interactions with similar regions of the diverse ligands. In addition, the left side and entrance of the pocket is important for ligand recognition and for the specificity of ligand interactions. Our results suggested that the different drug effectiveness observed for the various PIs against PR2 could be partially explained by different induced backbone deformations in the pocket. For example, we suggested that DRV and APV binding do not cause similar backbone deformations at 31A, 48A, and 23B positions. This could modify their binding mode and partially explain the differences of DRV and APV effectiveness on HIV-2 [START_REF] Raugi | Complex patterns of protease inhibitor resistance among antiretroviral treatment-experienced HIV-2 patients from senegal: Implications for second-line therapy[END_REF]. Furthermore, it would be interesting to study the relationship between drug effectiveness and local conformations of PR2 positions by considering an even larger number of drugs. This could help to better understand the PR2 resistance and the optimization of new PIs.

In addition, our results suggested that the conformation of some residues of the α-helix, flap, and fulcrum region is important for maintaining the conserved structure of certain catalytic-pocket residues. We also showed that the ligand-induced deformation in the binding pocket seems to be accompanied by structural changes of residues outside the binding pocket, particularly in the α-helix, the end of flaps, and the beginning of the fulcrum regions. This underlies the cooperative movements in the PR2 structure upon ligand binding that needs to be taken into account for the comprehension of ligand binding. These results could help to develop new allosteric PIs with original mode of action. Indeed, the usual strategy consists in identifying chemical molecules binding catalytic-site to prevent substrate binding. However, to develop small molecules able to ligands. An edge represents an interaction (H-bonds or non-bonded interactions) between a PR2 residue and a ligand atom belonging to a cluster. Edge thickness is proportional to the number of structures exhibiting the interaction.

A c c e p t e d M a n u s c r i p t A c c e p t e d M a n u s c r i p t

  analyze the link between residue type and interactions, we determined the total number of interactions established by each residue type in the network (Table

  s c r i p t bind positions involving pocket deformation through allosteric effects or positions important for the maintain of the catalytic-site conformation could efficiently alter PR2 substrate binding and catalytic activity.To conclude, our results provide new insights about PR2 structural changes upon ligand binding and mechanism of PR2 ligand recognition. Understanding and taking advantage of such conformational flexibility will be important for understanding the natural resistance of PR2 to PIs as well as for the design and optimization of new PR2 inhibitors.Supplementary MaterialsS1 appendix: Presentation of SA-conf tool S2 appendix: Construction of the PR2-ligand interaction network S3 appendix: Analysis of the PR2-ligand interaction network S1 Figure:Comparison between B and B allAtoms values Zoete, V.,Michielin, O., & Karplus, M. (2002). Relation between sequence and structure of HIV-1 protease inhibitor complexes: a model system for the analysis of protein flexibility. Journal of MolecularBiology, 315,

Figure 1 :

 1 Figure 1: Description of the ligands bound to the18 PR2 structures. For each cocrystallized ligand, it is provided the PDB code of the structure where the ligand was extracted, the name HETAM code of the ligand and its 3D representation.

Figure 2 :

 2 Figure2: Detection of structural variability in the PR2 set using HMM-SA[START_REF] Camproux | A hidden markov model derivated structural alphabet for proteins[END_REF][START_REF] Regad | A hidden Markov model applied to the protein 3D structure analysis[END_REF]. A) Superimposition of the 18 bound PR2 structures onto the unbound PR2 (PDB code: 1HSI). Proteins are displayed in ribbon mode and colored according to structural regions: the Nter and Cter regions are colored in grey, the fulcrum region in magenta, the catalytic site region in yellow, the elbow region in brown, the flap region in orange, the cantilever region in blue, the wall region in green, and the α-helix in red. Pocket residues are shown in lines. B) HMM-SA was used to simplify the 3D structure of each PR2 chain into sequence of structural letters. C) Presentation of the geometry of the 27 structural letters (SL) of HMM-SA. The four structural letters specific to helices are framed in red and the five structural letters specific to β-strands are framed by a blue rectangle. D) Part of the 18 structural-letter sequences corresponding to the 3D structures of the 18 PR2 chains. Each structural letter represents the geometry of a four-Cα fragment. Structural letters are colored according to the PR2 structural regions. E) From the set of 18 structural-letter sequences, structural variable and conserved positions were located.

Figure 3 :

 3 Figure 3: Structural variability of all positions of PR2 chains A and B quantified by the neq SL parameter. Each neq SL value is colored according to the secondary structure (SS) statue. The first line of rectangles indicates the position flexibility quantified by the B norm parameter. The second line localizes situates pocket residues.

Figure 4 :

 4 Figure 4: The intraproteic H-bond network of PR2. H-bonds were extracted from each PR2 structure using PyMoL software. Circle nodes represent PR2 residues of chain A, and square nodes represent PR2 residues of chain B. Nodes are colored according to residue types: type I residues (structurally conserved and rigid residues) in blue, type II residues (structurally conserved and flexible residues) in cyan, type III residues (structurally variable and rigid residues) in orange, and type IV residues (structurally variable and flexible) in red. Light blue nodes correspond to residues 1, 2, and 99 of both chains, for which structural letter has not been defined. Node size is proportional to the number of intraproteic H-bonds established by the corresponding residue. Edge thickness and color are proportional to the number of structures exhibiting the interactions represented by the edge.

Figure 5 :Figure 6 :

 56 Figure 5: Structural-letter map of pocket residues in the 18 PR2 structures. In this structural-letter map, the structural-letter sequences of each pocket are presented in rows, and positions are presented in columns. Positions are colored according to the 27 structural letters.

Figure 7 :

 7 Figure 7: A) Description of the 10 communities extracted from the PR2-ligand interaction network using the multi-level modularity optimization algorithm (Blondel et al., 2008). B) Representation of the consensus PR2 pocket colored according to the communities from the network of the PR2-ligand interactions. PR2 protein (PDB code: 3S45) is displayed in cartoons, the bound ligand (APV) in sticks, and the pocket in surface mode.

  Table1: Classification of PR2 residues according to their structural variability quantified by the neq SL parameter and their flexibility quantified by the B norm parameter.

Table 2 :

 2 Link between residue types and ligand structures and PR2-ligand interactions presented in Figure6. PR2-ligand interactions. Standard deviation values of average values were reported in brackets. The "*" symbol indicates the significant p-value, i.e.

	higher than 0.05.
				Type I	Type II	Type III	Type IV
			p-value
				residues	residues	residues	residues
	Number of positions in the PR2-
				11	1	17	4
	ligand interaction network
	Link between residue types and the capacity to establish	Total number of residue-atom interactions established by each residue type Average number of residue-atom	9e-04* 2e-04* 0.91 M 432 3.66 a n u s c r i p t 28 808 183 460 991 3.11 4. 01 3.39
	interaction with ligands Link between residue types A c c e p t e d interactions established by each residue type 0.637 Average size of ligand-atom clusters 0.35	(4.64) 3.62 (4.51) (2.20) 4.25 (3.62) 3.11 (2.15)	(6.82) 3.88 (6.24) (3.28) 4.11 (3.63) 4.24 (2.70)
	and ligand	involved linked
	structure	to residues of	0.94	4.17 (3.54)	4.14 (3.45)

Acknowledgments

We thank Yasaman Karami and Natacha Cerisier for proofreading the manuscript.

Funding

This work was supported by an ANRS Grant to B.V., D.D., A.C.C. and L.R. D.T. was supported by an ANRS fellowship.

A c c e p t e d M a n u s c r i p t mechanism of resistance to non-nucleoside inhibitors. Proceedings of the National Academy of Sciences USA, 99, 14410-14415. Rodés, B.;Sheldon, J., Toro, C., Jiménez, V., Alvarez, M.A., & Soriano V. (2006).

Susceptibility to protease inhibitors in HIV-2 primary isolates from patients failing antiretroviral therapy. Antimicrobial Agents and Chemotherapy, 57, 709-713. Sadiq, S.K., & de Fabritiis, G. (2010). Explicit solvent dynamics and energetics of HIV-1 protease flap opening and closing. Proteins, 78, 2873-2885. Thaisrivongs, S., Watenpaugh, K.D., Howe, W.J., Tomich, P.K., Dolak, L.A. et al. Mining the protein data bank to differentiate error from structural variation in clustered static structures: an examination of HIV protease. Viruses, 4,48-62. Visseaux, B., Damond, F., Matheron, S., Descamps, D., & Charpentier, C. (2016). Hiv-2 molecular epidemiology. Infection, Genetics and Evolution, 46, 233-240. Wallace, A.C., Laskowski, R.A., & Thornton, J.M. (1996)