Carlo Comin
email: carlo.comin@unitn.it

Anthony Labarre
email: anthony.labarre@u-pem.fr

Romeo Rizzi
email: romeo.rizzi@univr.it

Stéphane Vialette
email: stephane.vialette@u-pem.fr

Sorting With Forbidden Intermediates

A wide range of applications, most notably in comparative genomics, involve the computation of a shortest sorting sequence of operations for a given permutation, where the set of allowed operations is fixed beforehand. Such sequences are useful for instance when reconstructing potential scenarios of evolution between species, or when trying to assess their similarity. We revisit those problems by adding a new constraint on the sequences to be computed: they must avoid a given set of forbidden intermediates, which correspond to species that cannot exist because the mutations that would be involved in their creation are lethal. We initiate this study by focusing on the case where the only mutations that can occur are exchanges of any two elements in the permutations, and give a polynomial time algorithm for solving that problem when the permutation to sort is an involution.

Introduction

Computing distances between permutations, or sequences of operations that transform them into one another, are two generic problems that arise in a wide range of applications, including comparative genomics [START_REF] Fertin | Combinatorics of Genome Rearrangements[END_REF], ranking [START_REF] Deza | Metrics on permutations, a survey[END_REF], and interconnection network design [START_REF] Lakshmivarahan | Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey[END_REF]. Those problems are well-known to reduce to constrained sorting problems of the following form: given a permutation π and a set S of allowed operations, find a sequence of elements from S that sorts π and is as short as possible. In the context of comparative genomics, the sequence to be reconstructed yields a possible scenario of evolution between the genomes represented by π and the target identity permutation ι, where all permutations obtained inbetween are successive descendants of π (and ancestors of ι). The many possible choices that exist for S, as well as other constraints or cost functions with which they can be combined, have given rise to a tremendous number of variants whose algorithmic and mathematical aspects have now been studied for decades [START_REF] Fertin | Combinatorics of Genome Rearrangements[END_REF]. Specific issues that biologists feel need to be addressed to improve the applicability of these results in a biological context include: 1) the oversimplicity of the model (permutations do not take duplications into account), 2) the rigid definition of allowed operations, which fails to capture the complexity of evolution, and 3) the complexity of the resulting problems, where algorithmic hardness results abound even for deceivingly simple problems. A large body of work has been devoted to addressing those issues, namely by proposing richer models for genomes, encompassing several operations with different weights [START_REF] Fertin | Combinatorics of Genome Rearrangements[END_REF]. Some approaches for increasing the reliability of rearrangement methods by adding additional biologically motivated constraints have been investigated (see for example [START_REF] Bergeron | Reconstructing ancestral gene orders using conserved intervals[END_REF] for conserved intervals, [START_REF] Figeac | Sorting by reversals with common intervals[END_REF] for restricting the set of allowed inversions and [START_REF] Bérard | Conservation of combinatorial structures in evolution scenarios[END_REF] for preserving the number of inversions in the scenario which commute with all common intervals). However, another critical issue has apparently been overlooked: to the best of our knowledge, no model takes into account the fact that the solutions it produces may involve allele mutations that are lethal to the organism on which they act. Lethals are usually a result of mutations in genes that are essential to growth or development [START_REF] Gluecksohn-Waelsch | Lethal genes and analysis of differentiation[END_REF]; they have been known to occur for more than a century [START_REF] Cuénot | Les races pures et leurs combinaisons chez les souris[END_REF], as they were first discovered by Cuénot in 1905 while studying the inheritance of coat colour in mice. As a consequence, solutions that may be perfectly valid from a mathematical point of view should nonetheless be rejected on the grounds that some of the intermediate ancestors they produce are nonviable and can therefore not have had any descendants. We revisit the family of problems mentioned above by adding a natural constraint which, as far as we know, has not been previously considered in this form (see e.g. [START_REF] Bergeron | Reconstructing ancestral gene orders using conserved intervals[END_REF][START_REF] Figeac | Sorting by reversals with common intervals[END_REF][START_REF] Bérard | Conservation of combinatorial structures in evolution scenarios[END_REF] for connected attempts): namely, the presence of a set of forbidden intermediate permutations, which the sorting sequence that we seek must avoid. We refer to this family of problems as guided sorting problems, since they take additional guidance into account. In this paper we focus our study on the case where only exchanges (i.e., algebraic transpositions) are allowed; furthermore, we simplify the problem by demanding that the solutions we seek be optimal in the sense that no shorter sorting sequence of exchanges exists even when no intermediate permutation is forbidden. We choose to focus on exchanges because of their connection to the underlying disjoint cycle structure of permutations, which plays an important role in many related sorting problems where a similar cycle-based approach, using this time the ubiquitous breakpoint graph, has proved extremely fruitful [START_REF] Labarre | Lower bounding edit distances between permutations[END_REF]. Therefore, we believe that progress on this particular variant will be helpful when attempting to solve related variants based on more complex operations. Our main contribution in this work is a polynomial time algorithm for solving guided sorting by exchanges when the permutation to sort is an involution. We show that, in that specific case, the space of all feasible sorting sequences admits a suitable description in terms of directed (s, t)-paths in hypercube graphs. We achieve this result by reducing guided sorting to the problem of finding directed (s, t)-paths that avoid a prescribed set F ⊆ V of forbidden vertices. Our main contribution, therefore, consists in solving this latter problem in time polynomial in just the encoding of F if G is constrained to be a hypercube graph, which is a novel algorithmic result that may be of independent interest. Specific properties that will be described later on [START_REF] Goldreich | Testing monotonicity[END_REF][START_REF] Lehman | On disjoint chains of subsets[END_REF] allow us to avoid the full construction of that graph, which would lead to an exponential time algorithm. We should mention that constrained variants of the (s, t)-connectivity problem have been studied already to some extent. For instance, already in the '70s, motivated by some problems in the field of automatic software testing and validation, Krause et al. [START_REF] Krause | Optimal software test planning through automated network analysis[END_REF] introduced the path avoiding forbidden pairs problem, namely, that of finding a directed (s, t)-path in a graph G = (V, E) that contains at most one vertex from each pair in a prescribed set F ⊆ V × V of forbidden pairs of vertices. Gabow et al. [START_REF] Gabow | On two problems in the generation of program test paths[END_REF] proved that the problem is NP-complete on DAGs. A number of special cases were shown to admit polynomial time algorithms, e.g. Yinnone [START_REF] Yinnone | On path avoiding forbidden pairs of vertices in a graph[END_REF] studied the problem in directed graphs under a skew-symmetry condition. However, the involved techniques and the related results do not extend to our problem, for which we are aware of no previously known algorithm that runs in time polynomial in just the encoding of F .

Background and Notation

Our aim is to sort a given permutation π using a predefined set of allowed operations, specified as a generating set S of the symmetric group S n . We seek a sorting sequence that uses only elements from S and: 1) avoids a given set F of forbidden permutations, i.e. no intermediary permutation produced by applying the operations specified by the sorting sequence belongs to F , and 2) is optimal, i.e. no shorter sorting sequence exists for π even if F = ∅. We refer to the general problem of finding a sorting sequence under these constraints as guided sorting, and restrict in this paper the allowed operations to exchanges of any two elements (i.e. algebraic transpositions). For instance, let π = 2 3 1 4 and F = { 1 3 2 4 , 3 2 1 4 }. Then 2 3 1 4 → 2 1 3 4 → 1 2 3 4 is a valid solution since it is optimal and avoids F , but neither 2 3 1 4 → 4 3 1 2 → 4 3 2 1 → 4 2 3 1 → 1 2 3 4 nor 2 3 1 4 → 1 3 2 4 → 1 2 3 4 can be accepted: the former is too long, and the latter does not avoid F .

We use standard notions and notation from graph theory (see e.g. [START_REF] Diestel | Graph Theory[END_REF] for undefined concepts), using {u, v} (resp. (u, v)) to denote the edge (resp. arc) between vertices u and v of an undirected (resp. directed) graph G = (V, E). All graphs we consider are simple: they contain neither loops nor parallel edges. If F ⊆ V , a directed path p = v 0 v 1 • • • v n avoids F when v i ∈ F for every i. If S ⊆ V and T ⊆ V , we say that a directed path p goes from S to T in G when p starts from some s in S and ends at some t in T . When G is directed, we partition the neighbourhood N (u) of a vertex u into the sets

N out (u) = {v ∈ V | (u, v) ∈ E} and N in (u) = {v ∈ V | (v, u) ∈ E}.
Some of our graphs may be vertex-labelled, using any injective mapping ℓ : V → N. For any n ∈ N, ℘ n = ℘([n]) denotes the power set of [n]. The hypercube graph on ground set [n], denoted by H n , is the graph with vertex set ℘ n and in which the arc (U, V ) connects vertices U, V ⊆ [n] if there exists some q ∈

[n] such that U = V \{q}. If S, T ∈ ℘ n and |S| ≤ |T |, then d S,T = |T |-|S| is the distance between S and T . Finally, H (i)
n denotes the family of all subsets of ℘ n of size i.

Solving guided sorting For Involutions

The Cayley graph Γ(S n , S) of S n for a given generating set S of S n contains a vertex for each permutation in S n and an edge between any two permutations that can be obtained from one another using one element from S. A naïve approach for solving any variant of the guided sorting problem would build the part of Γ(S n , S) that is needed (i.e. without the elements of F ), then run a shortest path algorithm to compute an optimal sequence that avoids all elements of F . This is highly impractical, since the size of Γ is exponential in n.

We describe in this section a polynomial time algorithm in the case of exchanges if π is an involution, i.e. a permutation such that for each 1 ≤ i ≤ n, either π i = i or there exists an index j such that π i = j and π j = i. From our point of view, involutions reduce to collections of disjoint pairs of elements that each need to be swapped by an exchange until we obtain the identity permutation, and the only forbidden permutations that could be produced by an optimal sorting sequence are involutions whose pairs of unsorted elements all appear in π. Therefore, we can reformulate our guided sorting problem in that setting as that of finding a directed (π, ι)-path in H n that avoids all vertices in F , where the permutation to sort π corresponds to the bottom vertex ∅ of H n and the identity permutation ι corresponds to the top vertex [n] of H n . We shall focus on the following problem from here on.

Problem: Hy-stCon.

Input: the size n ∈ N of the underlying ground set [n], a family of forbidden vertices F ⊆ ℘ n , a source set S ∈ ℘ n and a target set T ∈ ℘ n . Decision-Task: Decide whether there exists a directed path p in H n that goes from source S to target T avoiding F ; Search-Task: Compute a directed path p in H n that goes from source S to target T avoiding F , provided that at least one such path exists.

We will show how to solve Hy-stCon in time polynomial in |F | and n. The algorithm mainly consists in the continuous iteration of two phases:

1. Double-BFS. This phase explores the outgoing neighbourhood of the source S by a breadth-first search denoted by BFS ↑ going from lower to higher levels of H n while avoiding the vertices in F . BFS ↑ collects a certain (polynomially bounded) amount of visited vertices. Symmetrically, the incoming neighbourhood of the target vertex T is also explored by another breadth-first search BFS ↓ going from higher to lower levels of H n while avoiding the vertices in F , also collecting a certain (polynomially bounded) amount of visited vertices.

Compression. If a valid solution

has not yet been determined, then a compression technique is devised in order to shrink the size of the remaining search space. This is possible thanks to some nice regularities of the search space and to certain connectivity properties of hypercube graphs [START_REF] Goldreich | Testing monotonicity[END_REF][START_REF] Lehman | On disjoint chains of subsets[END_REF]. This allows us to reduce the search space in a suitable way and, therefore, to continue with the Double-BFS phase in order to keep the search towards valid solutions going.

Our main contribution is summarized in the following theorem. We devote the rest of this section to an in-depth description of the algorithms it mentions1 . Theorem 1. Concerning the Hy-stCon problem, the following propositions hold on any input S, T, F , n , where d S,T is the distance between S and T .

On Vertex-Disjoint Paths in Hypercube Graphs

The proof of Theorem 1 relies on connectivity properties of hypercube graphs [START_REF] Goldreich | Testing monotonicity[END_REF].

The next result, which proves the existence of a family of certain vertex-disjoint paths in H n that are called Lehman-Ron paths, will be particularly useful.

Theorem 2 (Lehman, Ron [START_REF] Lehman | On disjoint chains of subsets[END_REF]). Given n, m ∈ N, let R ⊆ H n with |R| = |S| = m and 0 ≤ r < s ≤ n. Assume there exists a bijection ϕ : S → R such that ϕ(S) ⊂ S for every S ∈ S. Then there exist m vertex-disjoint directed paths in H n whose union contains all the subsets in S and R.

We call tuples R, S, ϕ, n that satisfy the hypotheses of Theorem 2 Lehman-Ron tuples, and we refer to the quantity d = sr as the distance between R ⊆ H (r) n and S ⊆ H (s) n . Lehman and Ron [START_REF] Lehman | On disjoint chains of subsets[END_REF] give an elementary inductive proof of Theorem 2. A careful and in-depth analysis of their proof, from the algorithmic perspective, yields a polynomial time algorithm for computing all the Lehman-Ron paths. In an extended version2 we provide all the details of the above mentioned algorithm as well as a proof of the time complexity stated in Theorem 3, in which Menger's vertex-connectivity theorem [START_REF] Diestel | Graph Theory[END_REF] and Hopcroft-Karp's algorithm [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF] for maximum cardinality matching in undirected bipartite graphs play a major role.

A Polynomial Time Algorithm For Solving Hy-stCon

We now describe a polynomial time algorithm for solving Hy-stCon, called solve Hy-stCon(), which takes as input an instance S, T, F , n of Hy-stCon, and returns a pair YES, p where p is a directed path in H n that goes from source S to target T avoiding F if such a path exists (otherwise, the algorithm simply returns NO). Algorithm 1 shows the pseudocode for that procedure. The rationale at the base of solve Hy-stCon() consists in the continuous iteration of two major phases: double-bfs phase() (line 5) and compression phase() (line 11). Throughout computation, both phases alternate repeatedly until a final state of termination is eventually reached (either at line 7, line 10 or line 12). At that point, the algorithm either returns a pair YES, p where p is the sought directed path, or a negative response NO instead3 . We now describe both phases in more detail, and give the corresponding pseudocode.

Algorithm 1: solving the Hy-stCon problem.

Procedure solve Hy-stCon(S, T, F , n)

Input: an instance S, T, F , n of Hy-stCon.

Output: a pair YES, p where the path p is a solution to Hy-stCon if such a path exists, NO otherwise. Algorithm 2: Breadth-First-Search phases of solve Hy-stCon().

Procedure double-bfs phase(S, T ,

F , ℓ ↑ , ℓ ↓ , d S,T , n) 1 S * , ℓ * ↑ ← bfs phase(S, F , ℓ ↑ , ℓ ↓ , out, d S,T , n); // BFS ↑ phase 2 T * , ℓ * ↓ ← bfs phase(T , F , ℓ ↓ , ℓ * ↑ , in, d S,T , n); // BFS ↓ phase 3 return S * , T * , ℓ * ↑ , ℓ * ↓ ; SubProcedure bfs phase(X , F , ℓx, ℓy, drt, d S,T , n) 1 while 1 ≤ |X | ≤ |F | d S,T AND ℓx + ℓy < d S,T do 2 X ← next step bfs(X , F , drt, n); 3 ℓx ← ℓx + 1; 4 return X , ℓx ; SubProcedure next step bfs(X , F , drt, n) 1 X ′ ← ∅; 2 foreach v ∈ X do 3 X ′ ← X ′ ∪ N drt (v) \ F ; // N drt is N in if drt = in, otherwise it is N out 4 return X ′ ;
Breadth-First Search phases. The first search BFS ↑ starts from the source vertex S and moves upward, from lower to higher levels of H n . Meanwhile, it collects a certain (polynomially bounded) amount of vertices that do not lie in F . In particular, at the end of any BFS ↑ phase, the number of collected vertices will always lie between |F | d S,T + 1 and |F | d S,T n (see line 1 of bfs phase()).

The set S of vertices collected at the end of BFS ↑ is called the (source) frontier of BFS ↑ . All vertices within S have the same cardinality, i.e.

|X 1 | = |X 2 | for every X 1 , X 2 ∈ S.
Also, the procedure keeps track of the highest level of depth ℓ ↑ that is reached during BFS ↑ . Thus, ℓ ↑ corresponds to the distance between the source vertex S and the current frontier S, formally, ℓ ↑ = |X| -|S| for every X ∈ S.

Since at the beginning of the computation BFS ↑ starts from the source vertex S, solve Hy-stCon() initializes S to {S} and ℓ ↑ to 0 at line 2.

Similarly, the second search BFS ↓ starts from the target vertex T and moves downward, from higher to lower levels of H n , also collecting a certain (polynomially bounded) amount of vertices that do not lie in F . As in the previous case, this amount will always lie between |F | d S,T + 1 and |F | d S,T n. The set T of vertices collected at the end of BFS ↓ is called the (target) frontier of BFS ↓ . All vertices within T have the same cardinality. Also, the procedure keeps track of the lowest level of depth ℓ ↓ that BFS ↓ has reached. Thus, ℓ ↓ corresponds to the distance between the target vertex T and the frontier T , so that ℓ ↓ = |T | -|X| for every X ∈ T . Since at the beginning of the computation, BFS ↓ starts from the target vertex T , solve Hy-stCon() initializes T = {T } and ℓ ↓ = 0 at line 3. Fig. 1 provides an illustration of double-bfs phase().

In summary, after any round of double-bfs phase(), we are left with two (possibly empty) frontier sets S and T . In Algorithm 1, whenever S = ∅ or T = ∅ holds at line 6, then at least one frontier set could not proceed one level further in H n while avoiding F , and thus the procedure halts by returning NO at line 7. Similarly, whenever ℓ ↑ + ℓ ↓ = d S,T and S ∩ T = ∅ holds at line 6, the computation halts by returning NO at line 7 -the underlying intuition being that S and T have finally reached one another's level of depth without intersecting each other, which means that H n contains no directed path from S to T that avoids

F 4 . 1, 2, 3 1,2 1, 3 2,3 1 2 3
∅ On the other hand, if both ℓ ↑ + ℓ ↓ = d S,T and S ∩ T = ∅ hold at line 8, then we can prove that for every S ′ ∈ S, there exists at least one directed path in H n that goes from the source S to S ′ avoiding F . Similarly, for every T ′ ∈ T , there exists at least one directed path in H n that goes from T ′ to target T avoiding F . Therefore, whenever S ∩ T = ∅, the algorithm is in the right position to reconstruct a directed path p in H n that goes from source S to S ∩ T and from S ∩ T to target T avoiding Algorithm 3: Compression phase of solve Hy-stCon().

Procedure compression phase(S, T , F , ℓ ↑ , ℓ ↓ , d S,T , n) 1 T ′ ← ∅; 2 while TRUE do 3 G ← construct bipartite graph(S, T , n); 4 M ← compute max matching(G, |F | + 1); 5 if |M| > |F | then 6 M S ← {X ∈ S | ∃ Y ∈ T s.t (X, Y ) ∈ M}; 7 M T ← {Y ∈ T | ∃ X ∈ S s.t. (X, Y ) ∈ M}; 8 {p 1 , . . . , p |M| } ← compute Lehman-Ron paths(M S , M T , M, n); 9 p ← reconstruct path(S, T , {p i } |M| i=1 , n); 10 return YES, p ; 11 X ← compute min vertex cover(G, M); 12 X S ← X ∩ S; X T ← X ∩ T ; 13 T ′ ← T ′ ∪ X T ; 14 S, T , ℓ ↑ , ℓ ↓ ← double-bfs phase(X S , T , F , ℓ ↑ , ℓ ↓ , d S,T , n); 15 if S = ∅ OR (ℓ ↓ + ℓ ↑ = d S,T AND S ∩ T = ∅ ) then 16 return T ′ ; 17 if ℓ ↑ + ℓ ↓ = d S,T AND S ∩ T = ∅ then 18 p ← reconstruct path(S, T , n); 19 return YES, p ;
F (line 9). In practice, the reconstruction can be implemented by maintaining a map throughout the computation, which associates to every vertex v (possibly visited during the BFSs) the parent vertex, parent(v), which led to discover v first. As soon as p gets constructed, solve Hy-stCon() returns YES, p at line 10, and the computation halts.

Compression Phase. After double-bfs phase() has completed, the procedure solve Hy-stCon() also needs to handle the case where S, T = ∅ and ℓ ↓ + ℓ ↑ < d S,T . The phase that starts at that point is named compression phase() (see Algorithm 3).

This procedure takes as input a tuple S, T , F , ℓ ↑ , ℓ ↓ , d S,T , n , where S and T are the current frontier sets. Recall that |T | > |F | d S,T holds due to line 1 of bfs phase(). Also, F ⊆ ℘ n is the set of forbidden vertices; ℓ ↑ is the level counter of S and ℓ ↓ is that of T ; finally d S,T is the distance between the source S and the target T , and n is the size of the ground set. The output returned by compression phase() is either a path p that goes from the source S to the target T avoiding F or a subset T ′ ⊂ T such that the following two basic properties hold:

(1) |T ′ | ≤ |F | d S,T , and (2) if p is any directed path in H n that goes from S to T avoiding F , then p goes from S to T ′ . This frontier set T ′ is dubbed the compression of T . The underlying rationale goes as follows. On one hand, because of (1), it is possible to keep the search going on by applying yet another round of double-bfs phase() on input S and T ′ (in fact, the size of T has been compressed down to

|T ′ | ≤ |F | d S,T , thus matching the threshold condition "|X | ≤ |F | d S,
T " checked at line 1 of bfs phase()). On the other hand, because of (2), it is indeed sufficient to seek for a directed path in H n that goes from S to T ′ avoiding F , namely, the search can actually forget about T \ T ′ because it leads to a dead end. We now describe compression phase() in more details, and give a graphical summary in Fig. 2. The procedure repeatedly builds an undirected bipartite graph G = (V G , E G ), where V G = S ∪ T and every vertex U ∈ S is adjacent to a vertex V ∈ T if and only if U ⊂ V . It then uses the procedure compute max matching() to find a matching M of size |M| = min(m * , |F | + 1), where m * denotes the size of a maximum cardinality matching of G. In practice, this step can be implemented in the same manner as a maximum cardinality matching procedure, e.g. as Hopcroft-Karp's algorithm [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF], although with the following basic variation: if the size of the augmenting matching M eventually reaches the cut-off value |F | + 1, then compute max matching() returns M and halts (i.e. even if m * > |F | + 1). The next course of action depends on |M|:

(S, T ) (S, X (1) T ) (X (1) S , T ) (S (1) , T ) (S (1) , X (2) T ) (X (2) S , T ) (S (2) , T ) (S (2) , X (3) T ) (X (3) S , T ) (S (maxi -1) , T ) (S (maxi -1) , X (maxi) T ) (X (maxi) S , T ) . . .
1. If |M| = |F | + 1,
p i = v 0 v 1 • • • v k by direct inspection.
At that point, it is possible to reconstruct a path p going from S to v 0 (because v 0 ∈ S), as well as a path going from v k to T (because v k ∈ T ). As already mentioned, in practice, the reconstruction can be implemented by maintaining a map that associates to every vertex v (eventually visited during the BFSs) the parent vertex that had led to discover v first. Then, YES, p is returned at line 10.

If

(i+1) = ∅ or both ℓ (i+1) ↑ +ℓ ↓ = d S,T and S (i+1) ∩T = ∅ at line 15, then T ′ is returned at line 16 of compression phase(). Otherwise, if ℓ (i+1) ↑ + ℓ ↓ = d S,
T and S (i+1) ∩ T = ∅ at line 17, the sought directed path p in H n that goes from source S to target T avoiding F can be reconstructed from S (i+1) and T at line 18, so that compression phase() returns YES, p and halts soon after at line 19.

Otherwise, if S (i+1) = ∅ and ℓ (i+1) ↑ + ℓ ↓ < d S,T , the next iteration will run on the novel frontier set S (i+1) and its updated level counter ℓ (i+1) ↑

. It is not difficult to prove5 that each iteration increases ℓ ↑ by at least one unit, so that the while-loop at line 2 of compression phase() can be iterated at most d S,T times overall. In particular, this fact implies that |T ′ | ≤ |F | d S,T always holds at line 16 of compression phase(). Fig. 2 illustrates the family of all frontier sets considered throughout compression phase(), where the following notation is assumed: max i is the total number of iterations of the while-loop at line 2 of compression phase(), X (i) is the vertexcover computed at the i th iteration of line 11, X (i)

S and X (i)

T are the sets computed at the i th iteration of line 12, and S (i) is the frontier set computed at the i th iteration of line 14. The compression of T (possibly returned at line 16

) is T ′ = maxi i=1 X (i) T .

A Remark On Decision Versus Search

Algorithm 1 tackles the Search-Task of Hy-stCon. If we merely want to answer the Decision-Task instead, we can simplify the algorithm by immediately returning YES if |M| > |F | at line 5 of compression phase(). This is because in that case, Theorem 2 guarantees the existence of a family of |M| > |F | vertex-disjoint paths in H n that go from the current source frontier S to the target frontier T , which suffices to conclude that at least one of those paths avoids F . This simplification improves the time complexity of our algorithm for solving the Decision-Task by a polynomial factor over that for the Search-Task.

Conclusion

With the intention of integrating more biologically relevant constraints into classical genome rearrangement problems, we introduced in this paper the guided sorting problem. We broadly define it as the problem of transforming two genomes into one another using as few operations as possible from a given fixed set of allowed operations while avoiding a set of nonviable genomes. We gave a polynomial time algorithm for solving this problem in the case where genomes are represented by permutations, under the assumptions that 1) permutations can only be modified by exchanging any two elements, 2) the sequence to seek must be optimal, and 3) the permutation to sort is an involution.

Many questions remain open, most notably that of the computational complexity of the guided sorting problem, whether under assumptions (1) and ( 2) or in a more general setting (i.e., using structures other than permutations, operations other than exchanges, or allowing sequences to be "as short as possible" instead of optimal). One could also investigate "implicit" representations for the set of forbidden intermediate permutations, e.g. all permutations that avoid a given (set of) pattern(s), or that belong to a specific conjugacy class. Aside from complexity issues, future work shall also focus on extending the approach we proposed to other families of instances of the guided sorting problem, and identifying other tractable (or intractable) cases or variants of it; for instance, we plan to extend our algorithmic results to the family of graphs satisfying the shadow-matching [START_REF] Logan | A new matching property for posets and existence of disjoint chains[END_REF] condition.

A Appendix: Instances of guided sorting that Reduce to Hy-stCon

We examine in this section specific instances of guided sorting which can be solved through a reduction to Hy-stCon. We say that permutations that may occur in an optimal sorting sequence for a given permutation π are relevant, and all others are irrelevant. The distinction will matter when sorting a particular permutation since, as we shall see, the structure of π (however it is measured) will have implications on that of relevant permutations and will allow us to simplify the set of forbidden permutations by discarding irrelevant ones. For a fixed set S of operations, we let R S (π) denote the set of permutations that are relevant to π.

Undefined terms and unproven properties of permutations below are well-known, and details can be found in standard references such as [START_REF] Knuth | The Art of Computer Programming, Volume III: Sorting and Searching[END_REF].

A.1 guided sorting For Exchanges

Recall that every permutation π in S n decomposes in a single way into disjoint cycles (up to the ordering of cycles and of elements within each cycle). This decomposition corresponds to the cycle decomposition of the directed graph

G(π) = (V, A), where V = [n] and A = {(i, π i ) | 1 ≤ i ≤ n}.
The length of a cycle of π is then simply the number of elements it contains, and the number of cycles of π is denoted by c(π).

The Cayley distance of a permutation π is the length of an optimal sorting sequence of exchanges for π, and its value is nc(π). Therefore, when searching for an optimal sorting sequence, we may restrict our attention to exchanges that split a particular cycle into two smaller ones.

Let (π, F , S, K) be an instance of guided sorting such that S is the set of all exchangess and where the permutation π to sort is an involution, i.e. a permutation whose cycles have length at most two. It is customary to omit cycles of length 1, and to write a permutation π = π 1 π 2 • • • π n with k cycles of length 2 as c 1 c 2 • • • c k . Since we are looking for an optimal sorting sequence, we may assume that all permutations in F are relevant, which in this case means that every permutation φ in F is an involution and its 2-cycles form a proper subset of those of π. Our instance of guided sorting then translates to the following instance of Hy-stCon:

• π → [k] in the following way: c i → i for 1 ≤ i ≤ k;
• each permutation φ in F is mapped onto a subset of [k] by replacing its cycles with the indices obtained in the first step; we let F ′ denote the collection of subsets of [k] obtained by applying that mapping to each φ in F .

The resulting Hy-stCon instance is then [k], ∅, F ′ , k , and a solution to instance (π, F , S, K) of guided sorting exists if and only if a solution to instance [k], ∅, F ′ , k of Hy-stCon exists; the translation of the solution from the latter formulation to the former is straightforward.

A.2 guided sorting For Adjacent Exchanges

Recall that an inversion in a permutation π in S n is a pair (π i , π j ) with 1 ≤ i < j ≤ n and π i > π j . Let (π, F , S, K) be an instance of guided sorting where S is the set of all adjacent exchanges, i.e. exchanges that act on consecutive positions. It is well-known that in this case, any optimal sorting sequence for π has length equal to the number of inversions of π, which means that in the search for an optimal sorting sequence, we may restrict our attention to adjacent exchanges that act on inversions that consist of adjacent elements and disregard fixed points (i.e. positions i such that π i = i, which correspond to elements that are already where they should be in ι).

Let us now assume that all k inversions of π are made of adjacent elements, and denote π = i 1 i 2 • • • i k , where each i j is an inversion. Since we are looking for an optimal sorting sequence, we may assume that all permutations in F are relevant, which in this case means that all inversions of any permutation φ in F form a proper subset of those of π. The reduction to Hy-stCon in that setting is very similar to that given in the case of exchanges:

• π → [k]
in the following way: i j → j for 1 ≤ j ≤ k;

• each permutation φ in F is mapped onto a subset of [k] by replacing its inversions with the indices obtained in the first step; we let F ′ denote the collection of subsets of [k] obtained by applying that mapping to each φ in F .

The resulting Hy-stCon instance is then [k], ∅, F ′ , k , and a solution to instance (π, F , S, K) of guided sorting exists if and only if a solution to instance [k], ∅, F ′ , k of Hy-stCon exists; the translation of the solution from the latter formulation to the former is straightforward.

B Appendix: Omitted Proofs B.1 The Proof of Theorem 1

Our proof of Theorem 1 relies on certain connectivity properties of hypercube graphs, and in particular the existence of a family of certain vertex-disjoint paths in H n that we call "Lehman-Ron paths", which is guaranteed by Theorem 2.

Although Theorem 2 was initially proved and applied in the specific area of testing monotonicity [START_REF] Goldreich | Testing monotonicity[END_REF], it is of independent interest and related results could be useful in the context of packet routing on the hypercube network. Lehman and Ron provided an elegant inductive proof of that result [START_REF] Lehman | On disjoint chains of subsets[END_REF]. In the present work, we point out that a careful analysis of their proof allows us to "extract" a simple recursive algorithm for computing all Lehman-Ron paths in polynomial time. We now describe that algorithm, whose correctness follows from the arguments used by Lehman and Ron in their original proof of Theorem 2 (see [START_REF] Lehman | On disjoint chains of subsets[END_REF] for more details). Its time complexity can be derived by taking into account Hopcroft-Karp's algorithm for computing maximum cardinality matchings in bipartite graphs [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF], and will be analyzed in details at the end of this section.

The algorithm we describe is named compute Lehman-Ron paths(). The intuition underlying it is simply to follow the structure of Lehman and Ron's proof of Theorem 2 and to analyze it from the algorithmic standpoint. Its pseudocode is given below. The algorithm takes as input a Lehman-Ron tuple R, S, ϕ, n , and outputs a family p 1 , p 2 , . . . , p m of Lehman-Ron paths joining R to S. Recall that Lehman-Ron tuples satisfy the following properties:

1. the families of sets R ⊆ H As a base case of the algorithm, if s = r + 1 (line 1), then the sought family of directed paths p 1 , p 2 , . . . , p m is simply a set of m pairwise vertex-disjoint arcs oriented from S to R, which are already given by the input bijection ϕ (line 2).

We now focus on the general case s > r + 1. To begin with, we introduce the following proposition, which was already implicit in [START_REF] Lehman | On disjoint chains of subsets[END_REF] and which is actually a straightforward consequence of Theorem 2. Proposition 1. [START_REF] Lehman | On disjoint chains of subsets[END_REF] Given n, m ∈ N, consider two families of sets R ⊆ H ) that lie on any directed path from some vertex in R to some vertex in S. Then, |Q| ≥ m and |P| ≥ m.

The algorithm first computes the set Q of all vertices in H (s-1) n that lie on any directed path from some vertex in R to some vertex in S. This step is encoded by compute Q() (line 4). The algorithm then invokes (at line 5) a procedure called compute auxiliary network(), which constructs a directed auxiliary network K = (V K , A K ) which will be useful in the following steps and is defined by:

• V K = {s, t} ∪ R ∪ S ∪ Q, where s (resp. t) is an auxiliary source (resp. target) vertex, i.e. {s, t} ∩ (R ∪ Q ∪ S) = ∅;
• A K is defined as follows:

the source vertex s is joined to every vertex in R;

-for each R ∈ R and Q ∈ Q, R is joined to Q if and only if R ⊂ Q; -similarly, for each Q ∈ Q and S ∈ S, Q is joined to S if and only if Q ⊂ S;
finally, every vertex in S is joined to t.

We remark that, as shown in [START_REF] Lehman | On disjoint chains of subsets[END_REF], the following proposition holds on K.

Proposition 2.

[16] The minimum (s, t)-vertex-separator of K has size m.

As a corollary, and by applying Menger's vertex-connectivity theorem (which is recalled below), the existence of m internally-vertex-disjoint directed (s, t)-paths, denoted p ′ 1 , p ′ 2 , . . . , p ′ m , is thus guaranteed. Theorem 4 (Menger [START_REF] Diestel | Graph Theory[END_REF]). Let G = (V, A) be a directed graph, and let u and v be nonadjacent vertices in V . Then the maximum number of internally-vertex-disjoint directed (u, v)-paths in G equals the minimum number of vertices from V \ {u, v} whose deletion destroys all directed (u, v)-paths in G.

B.1.1 How to compute p ′

1 , p ′ 2 , . . . , p ′ m . We argue that it is possible to compute efficiently the family of directed paths p ′ 1 , p ′ 2 , . . . , p ′ m in K by finding a maximum cardinality matching in an auxiliary, undirected bipartite graph K ′ . This reduction is performed by compute vertex disjoint paths() at line 6. The undirected graph K ′ = (V K ′ , E K ′ ) is obtained from the directed graph K as follows: first, the set family Q gets split into two (disjoint) twin set families

Q (in) and Q (out) ,i.e. Q (in) = {Q (in) | Q ∈ Q} and Q (out) = {Q (out) | Q ∈ Q} where Q (in) ∩ Q (out) = ∅ and |Q (in) | = |Q (out) | = |Q|. Thus, the vertex set of K ′ is: V K ′ = R ∪ Q (in) ∪ Q (out) ∪ S.
The edge set E K ′ is obtained as follows:

• for each R ∈ R and Q ∈ Q, R is joined to Q (in) if and only if R ⊂ Q; • similarly, for each Q ∈ Q and S ∈ S, Q (out) is joined to S if and only if Q ⊂ S; • finally, Q (in) is joined to Q (out) for every Q ∈ Q.
In the next proposition we derive some useful properties of K ′ . Proposition 3. The graph K ′ = (V K ′ , E K ′ ), as defined above, is bipartite and it admits a perfect matching.

Proof. The bipartiteness of K ′ follows from the bipartition (R ∪ Q (out) , Q (in) ∪ S).

To see that K ′ admits a perfect matching, recall that, by Proposition 2 and by Theorem 4, there exist m internally-vertex-disjoint directed (s, t)-paths

p ′ 1 , p ′ 2 , . . . , p ′ m in K. Then, for every i ∈ [m], let p ′ i = sR i Q i S i t for some R i ∈ R, Q i ∈ Q, S i ∈ S. Finally, let us define Q = Q \ {Q | ∃ i ∈ [m] s.t. p ′ i = sR i QS i t}.
At this point, let us consider the following matching M of K ′ :

M = {R i , Q (in) i }, {Q (out) i , S i } | ∃ i ∈ [m] s.t. p ′ i = sR i Q i S i t ∪ {Q (in) , Q (out) } | Q ∈ Q} . Since m = |R| = |S| and p ′ 1 , p ′ 2 , . . . , p ′ m are internally-vertex-disjoint, it follows that M is a perfect matching of K ′ .
We can now show how to compute p ′ 1 , p ′ 2 , . . . , p ′ m based on K. Firstly, the procedure compute vertex disjoint paths() constructs K ′ as explained above and computes a maximum cardinality matching M of K ′ (e.g. with Hopcroft-Karp's algorithm [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF]), which is perfect by Proposition 3. Therefore, the following property holds: for every Q ∈ Q, there exists R ∈ R such that {R, Q (in) } ∈ M if and only if there exists S ∈ S such that {Q (out) , S} ∈ M. We can then proceed as follows: for each R i ∈ R, the algorithm finds

Q i ∈ Q such that {R i , Q (in) i
} ∈ M and then it finds S i ∈ S such that {Q (out) i , S i } ∈ M. Then, compute vertex disjoint paths() returns the family of paths p ′ 1 , p ′ 2 , . . . , p ′ m defined as:

p ′ i = sR i Q i S i t for every i ∈ [m]. Since M is a perfect matching of K ′ , the paths p ′ 1 , p ′ 2 , . . . , p ′ m are internally-vertex- disjoint. Let Q ′ = {Q | ∃ i ∈ [m] s.t. p ′ i = sR i QS i t}.
Once we have computed p ′ 1 , p ′ 2 , . . ., p ′ m , we can deduce two bijections that will be helpful in obtaining the wanted paths:

ϕ ′ : R → Q ′ and ϕ ′′ : Q ′ → S.
The first bijection is defined for any R ∈ R as ϕ ′ (R) = Q (where Q ∈ Q ′ ) provided there exists some p ′ i joining R to Q; similarly, the second bijection is defined for any Q ∈ Q ′ as ϕ ′′ (Q) = S (where S ∈ S) provided there exists some p ′ i joining Q to S. These bijections are computed by compute auxiliary bijections() at line 7.

At this point, since the distance between R and Q ′ equals s -1, a recursive call to compute Lehman-Ron paths() on input R, Q ′ , (ϕ ′ ) -1 , n yields, at line 8, a family of Lehman-Ron paths p ′′ 1 , p ′′ 2 , . . . , p ′′ m joining R to Q ′ . Indeed, we argue that it is possible to construct, starting from p ′′ 1 , p ′′ 2 , . . . , p ′′ m , the sought family of Lehman-Ron paths p 1 , p 2 , . . . , p m that join R to S. Actually, this can be done just by taking into account the bijection ϕ ′′ : since ϕ ′′ joins Q ′ to S, it suffices to perform the following steps in practice:

1. consider the last vertex Q i of p ′′ i (i.e. the unique vertex

Q i ∈ Q ′ such that Q i ∈ p ′′ i ∩ Q ′ ); 2. let S i = ϕ ′′ (Q i );
3. concatenate S i at the end of p ′′ i (i.e. p i = p ′′ i S i ). This construction is performed by the extend paths() procedure at line 9. Since p ′′ 1 , p ′′ 2 , . . . , p ′′ m are vertex-disjoint and ϕ ′′ : Q ′ → S is a bijection, p 1 , p 2 , . . . , p m is the sought family of Lehman-Ron paths joining R to S.

B.1.2 Complexity Analysis (Proof of Theorem 3).

We now turn to the time complexity analysis of Algorithm 4, going through each line in details.

• line 2: compute paths from bijection() (line 2) takes time at most O(m), which corresponds to the time needed to inspect the input bijection ϕ.

• line 4: compute Q() takes time at most O(mn): for each S ∈ S, the procedure inspects the predecessors N in (S), and the time bound follows from the fact that |S| = m and |N in (S)| ≤ n.

• line 5: we argue that

|V K | = O(mn) and |A K | = O(m 2 n).
Indeed, recall that |R| = |S| = m by hypothesis; and since every vertex of S has at most n neighbours in Q, we have |Q| ≤ mn. This in turn implies that |V K | ≤ 2+2m+mn; moreover, each of the m vertices in R has at most mn neighbours, which all lie in Q. Therefore, |A K | ≤ 2m + m 2 n + mn, and the procedure compute auxiliary network()

takes time at most O(|V K |+|A K |) = O(m 2 n).
• line 6: compute vertex disjoint paths() takes time at most O m 5/2 n 3/2 . Indeed, let us consider the auxiliary (undirected) bipartite graph

K ′ = (V K ′ , E K ′ ) defined above. Since |V K | = O(mn) and |A K | = O(m 2 n), we have |V K ′ | = O(mn) and |E K ′ | = O(m 2
n) by construction. A maximum cardinality matching M of K ′ can be computed with the Hopcroft-Karp's algorithm [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF] within time

O( |V K ′ | |E K ′ |) = O(m 5/2 n 3/2
), which yields the claimed time bound.

• finally, lines 7 (compute auxiliary bijections()) and 9 (extend paths()) take time at most O(m).

To obtain the total time complexity of compute Lehman-Ron paths(), it is sufficient to observe that the depth of the recursion stack (originating from line 8) equals the distance d = sr between the families of sets that were originally given as input, R and S, and that the most expensive computation at each step of the recursion is clearly the maximum cardinality matching computation that is performed on the auxiliary bipartite graph K ′ . Therefore, we conclude that the worst-case time complexity of compute Lehman-Ron paths() is O m 5/2 n 3/2 d .

B.2 Correctness Analysis of Algorithm 1

The present subsection aims to show that the procedure solve Hy-stCon() is correct. A formal statement of that is provided in the next theorem. Theorem 5. Let I = S, T, F , n be any instance of Hy-stCon. Given I as input, the procedure solve Hy-stCon() halts within a finite number of steps. Moreover, it returns as output a directed path p in H n that goes from source S to target T avoiding F , provided that at least one such path exists; otherwise, the output is simply NO.

We are going to show a sequence of results that shall ultimately lead us to prove Theorem 5. Hereafter, it is assumed that S, T, F , n is an instance (of Hy-stCon) given as input to the solve Hy-stCon() procedure. Lemmas 1 to 3 below show that procedures double-bfs phase() and compression phase(), which are called by solve Hy-stCon(), halt within a finite number of steps.

Lemma 1. Any invocation of double-bfs phase() halts within a finite number of steps. In particular, the while-loop at line 1 of the bfs phase() iterates at most d S,T times.

Proof. Consider the while-loop at line 1 of bfs phase(). At each iteration of line 3, the level counter ℓ x gets incremented. Notice that this is the only line at which ℓ x may be modified, and also notice that ℓ y is never modified. Therefore, ℓ x + ℓ y can only increase and not decrease. Since the while-loop at line 1 of bfs phase() halts as soon as ℓ x + ℓ y = d S,T , the thesis follows. Let us analyze its behavior with respect to X S . If X S = ∅, then double-bfs phase() returns an empty frontier set S as output, which leads to the termination of compression phase() at line 16. Moreover, if ℓ ↑ + ℓ ↓ = d S,T , then compression phase() halts either at line 16 or at line 19. Otherwise, we must have 1 ≤ |X S | ≤ |F | and ℓ ↑ + ℓ ↓ < d S,T , in that case the condition for entering the while-loop at line 1 of the bfs phase() is satisfied; therefore, at line 3 of bfs phase(), the level counter ℓ ↑ incremented. This implies the thesis. Lemma 3. Any invocation of compression phase() halts within a finite number of steps. In particular, the while-loop at line 2 of the compression phase() iterates at most d S,T times.

Proof. Firstly, recall Lemma 2. Then, notice that as soon as ℓ ↑ + ℓ ↓ = d S,T the compression phase() then halts either at line 16 (if S ∩ T = ∅) or at line 19 (if S ∩ T = ∅). This implies that the while-loop at line 2 of compression phase() iterates at most d S,T times.

We now prove some useful properties of compression phase() and solve Hy-stCon(). Lemma 4. The following invariant is maintained at each line of solve Hy-stCon() and at each line of compression phase(). For every S ′ ∈ S there exists a directed path in H n that goes from S to S ′ avoiding F ; similarly, for every T ′ ∈ T there is a directed path in H n that goes from T ′ to T avoiding F .

Proof. At the beginning of the procedure S = {S} and T = {T }, so the thesis holds. At each subsequent step, the only way in which a novel vertex can be added either to S or T is by invoking the double bfs phase(), which preserves connectivity and avoids F by construction at line 3 of next step bfs().

p i = v 0 • • • v k -must avoid F .
By Proposition 4, the procedure reconstruct path() (invoked at line 9) is able to compute a directed path p S,v0 in H n that goes from S to v 0 avoiding F (because v 0 ∈ S, being the first step of p i ), and it is also able to compute a directed path p v k ,T that goes from v k to T avoiding F (because v k ∈ T , being the last step of p i ). Let p = p S,v0 p i p v k ,T be the directed path obtained by concatenation. compression phase() then returns p at line 10.

2. Assume that line 19 is reached at the last iteration. Then, at that iteration, the condition checked at line 17 of compression phase() must be satisfied; that is, we have ℓ ↑ +ℓ ↓ = d S,T and S ∩T = ∅. Let X be an arbitrary vertex in S ∩T . By Lemma 4, there exists at least one directed path p S,X in H n that goes from S to X avoiding F (because X ∈ S); similarly, there exists at least one directed path p X,T in H n that goes from X to T avoiding F (because X ∈ T ). Therefore, during that iteration, the procedure reconstruct path() (invoked at line 18) is able to compute a path p = p S,X p X,T that goes from S to X, and then from X to T , which is the result returned by compression phase() at line 19.

The following result shows two useful properties of the frontier set returned by compression phase(), for which we will need additional notation. Denote by max i be the number of times that the while-loop at line 2 gets iterated throughout the whole execution of the compression phase().

Also, let us introduce the following notation, for each index i ∈ [max i ]:

• let X (i) be the vertex cover that is computed during the i-th iteration of line 11;

• let X (i)

S and X

(i)

T be the sets computed during the i-th iteration of line 12; • let S (i) be the novel frontier set that is computed during the i-th iteration of line 14;

Moreover, we assume the notation S (0) = S, so that X (i)

S = S (i-1) ∩ X (i) holds for each iteration i ∈ [max i ]. Notice that, since |T | > |F | d S,
T holds by hypothesis, then T is not modified, at line 14, by the invocation of double-bfs phase(). Indeed, T is never modified throughout the compression phase(). Nevertheless, a novel set T ′ ⊂ T gets constructed and possibly returned. Proposition 4. Assume that the procedure compression phase() is invoked on input S, T , F , ℓ ↑ , ℓ ↓ , d S,T , n , where |T | > |F | d S,T is required to hold as a precondition. Also, assume that the procedure halts at line 16, returning a novel frontier set T ′ ⊂ T . Then, the following properties hold:

1. |T ′ | ≤ |F | d S,T ;
2. if p is any directed path in H n that goes from S to T avoiding F , then p goes from S to T ′ .

Proof. Firstly notice that, if an invocation of the compression phase() halts at line 16 by returning a novel frontier set T ′ ⊂ T , this means that neither line 10 nor line 19 are ever reached throughout that invocation. In particular this implies that, at each iteration i of the while-loop at line 2, the maximum matching M (i) (computed at line 4) has size |M (i) | ≤ |F |; this fact is assumed throughout the whole proof.

1. Proof of (1). At each iteration i ∈ [max i ], the minimum vertex cover X (i) has size:

|X (i) | = |M (i) | ≤ |F |. Since X (i) T = X (i) ∩ T at line 12, then |X (i) T | ≤ |X (i) | ≤ |F |.
Moreover, recall that T ′ gets enriched by X (i) at each iteration of line 13, so that the following holds at the termination of the compression phase():

T ′ = maxi i=1 X (i) T .
Also recall that, by Lemma 3, the while-loop at line 2 can be iterated at most d S,T times, so that max i ≤ d S,T . Therefore, when compression phase() terminates, we have

|T ′ | ≤ |F | d S,T . Proof. Induction on i ∈ [max i ].
-Base Case. If i = 1, recall that S (0) = S. Then, by Lemma 6, we have that p either goes from X

S to T or from S \ X

S to X

T . If p goes from S \ X

S to T avoiding F in H n , then p must go from S (i) to T : in fact, recall that S (i) is the frontier set that is returned by the invocation of double-bfs phase() on input X (i) S , at line 14 of the compression phase(). If p goes from S (i) to T then, by Lemma 6, we also have that p goes either from X

(i+1) S to T or from S (i) \ X (i+1) S to X (i+1) T in H n . If p goes from S (i) \ X (i+1) S to X (i+1) T
, then p goes from S to X We now have everything we need to prove (2). Let i = max i be the last iteration of the while-loop at line 2 of compression phase(). Moreover, assume that p is a directed path in H n that goes from S to T avoiding F . By Lemma 8, p either goes from X T . We argue that p cannot go from X (maxi) S to T in H n . In fact, any such path must first visit S (maxi) in order to reach T . Then, it is sufficient to show that there exists no path that goes from S (maxi) to T . Recall that max i is the last iteration of the while-loop at line 2, and by hypothesis the compression phase() halts by returning T ′ at line 16. Therefore, at line 15, it must hold that S (maxi) = ∅ or that both ℓ (maxi) ↓ + ℓ ↑ = d S,T and S (maxi) ∩ T = ∅. Thus, there exists no directed path in H n that goes from S (maxi) to T . Since p does not go from X

(maxi) S to T , it must go from S to maxi i=1 X (i) T instead; and since T ′ = maxi i=1 X (i)
T , p must therefore go from S to T ′ , which concludes the proof of (2). Now that we have established the correctness of the procedures it uses, we go back to establishing the correctness of solve Hy-stCon(). Lemma 9. Each iteration of the while-loop at line 4 of solve Hy-stCon() increases ℓ ↑ + ℓ ↓ by at least one unit; until ℓ ↑ + ℓ ↓ = d S,T or until the procedure halts by reaching either line 7, line 10 or line 12.

Proof. Induction on the index i of iteration of the while-loop at line 4.

• Base Case. Consider the first iteration of the while-loop at line 4. We have S = {S}, T = {T }, and ℓ ↑ = ℓ ↓ = 0. Therefore, if d S,T = 0, then the procedure halts immediately, either at line 7 (if S = T ) or at line 10 (if S = T ). If d S,T > 0, then a first execution of double-bfs phase() is invoked at line 5, which halts after a finite number of steps by Lemma 1. Notice that the condition for entering the while-loop at line 1 of bfs phase() is satisfied, so ℓ ↑ + ℓ ↓ gets incremented at line 3 of bfs phase().

• Inductive Step. Assume that at the i-th iteration of the while-loop at line 4, we have ℓ ↑ + ℓ ↓ < d S,T . Furthermore, assume that none of the conditions checked by solve Hy-stCon() at line 6, line 8 and line 12 are satisfied. Then, the procedure does not halt at i-th iteration. Recall that double-bfs phase(), which is invoked at line 5, halts within finite time by Lemma 1; also, recall that compression phase(), which is invoked at line 11, halts within finite time by Lemma 3. Thus, at the end of the i-th iteration, line 13 gets finally executed. At line 13, the current frontier T gets replaced by the value T ′ , previously returned by compression phase() at line 11. Notice that |T ′ | ≤ |F | d S,T holds by Proposition 4. The (i + 1)-th iteration of the while-loop at line 4 starts at this point. Then, at line 5, another round of double-bfs phase() is executed. If T = ∅ and ℓ ↑ + ℓ ↓ < d S,T , the condition for entering the while-loop at line 1 of bfs phase() is satisfied, so that ℓ ↑ + ℓ ↓ gets incremented at line 3. If T = ∅ or ℓ ↑ + ℓ ↓ = d S,T , then the procedure halts at line 7. This implies that the invariant is maintained for each iteration i.

Proposition 5. The procedure solve Hy-stCon() halts within a finite number of steps. In particular, the while-loop at line 4 iterates at most d S,T times.

Proof. Recall the statement of Lemma 9. As soon as ℓ ↑ +ℓ ↓ = d S,T , then solve Hy-stCon() halts either at line 7 (if S ∩ T = ∅) or at line 10 (if S ∩ T = ∅). In particular, this implies that the while-loop at line 4 of the solve Hy-stCon() can be iterated at most d S,T times.

Proposition 6. Assume that solve Hy-stCon() halts by returning the pair YES, p . Then p is a directed path in H n that goes from S to T avoiding F .

Proof. Observe that solve Hy-stCon() can return YES, p as output only at line 10 or at line 12. In the latter case, p gets constructed at line 11 by invoking compression phase(), so the thesis follows by Lemma 5. Otherwise, assume that p is returned at line 10. Therefore, at the last iteration of line 8, it must hold that S ∩ T = ∅. Then, let X ∈ S ∩ T . By Lemma 4 there exists a directed path p S,X in H n that goes from S to X avoiding F (because X ∈ S), and there exists another directed path p X,T in H n that goes from X to T avoiding F (because X ∈ T ). Therefore, reconstruct path() at line 9, is able to compute a directed path p = p S,X p X,T in H n that goes from S to T avoiding F , which gets returned at line 12.

Lemma 10. The following invariant is maintained at each line of solve Hy-stCon(). If p is any directed path in H n that goes from S to T avoiding F , then p goes from S to T .

Proof. Induction on the index i of iteration of the while-loop at line 2.

• Base Case. Before entering the first iteration, since S = {S} and T = {T }, the thesis holds.

• Inductive Step. Assume that the thesis holds at the end of the i-th iteration. So, let S (i) and T (i) be the frontier sets at the end of the i-th iteration. When i = 0, just recall that S (0) = {S} and T (0) = {T }. Now, at the beginning of the (i + 1)-th iteration, in particular at line 5 of solve Hy-stCon(), let S and T be the frontier sets returned by the invocation of double-bfs phase(). If p is any directed path in H n that goes from S to T avoiding F , then p goes from S (i) to T (i) by induction hypothesis. It is not difficult to see that if p goes from S (i) to T (i) avoiding F , then p must go from S to T as well: at this point, the reader can check that this is a direct consequence of double-bfs phase()'s construction. If the (i + 1)-th iteration doesn't halt, then the compression phase() at line 11 gets invoked. Then, let T ′ be the value returned by compression phase() at line 11. By Proposition 4, if p is a directed path in H n that goes from S to T avoiding F , then p goes from S to T ′ . Thus, it is indeed correct to update T by T ′ at line 13 of solve Hy-stCon(). This implies that the thesis holds for each iteration of the while-loop at line 2, until termination.

Proposition 7. Assume that solve Hy-stCon() halts by returning NO. Then there is no directed path in H n that goes from S to T avoiding F .

Proof. Since solve Hy-stCon() returns NO, the condition checked at line 6 must be satisfied: if S = ∅ or T = ∅, then there exists no directed path in H n that goes from S to T ; similarly, if ℓ ↑ + ℓ ↓ = d S,T and S ∩ T = ∅, then there exists no directed path in H n that goes from S to T . By Lemma 10, there exists no directed path in H n that goes from S to T avoiding F .

Theorem 5 follows, at this point, from Propositions 5 to 7.

B.3 Complexity Analysis

We now analyze the time complexity of solve Hy-stCon(), starting with that of the procedures it relies on.

1. In the case where compute Lehman-Ron paths() never gets executed, recall that, at line 4, the compression phase() computes a matching M of G such that |M| = min(m * , |F | + 1), where m * is the size of a maximum cardinality matching of G. The Hopcroft-Karp algorithm [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF] performs that task within the following time bound t M : Notice that the time complexity of compute min vertex cover(), which is invoked at line 11 of compression phase(), is bounded above by the time complexity of computing M at line 4. Also, by Lemma 11, the time complexity of the double-bfs phase(), which is invoked at line 14 of compression phase(), is bounded above by the same quantity.

If compute Lehman-Ron paths() never gets executed at line 8, then during each iteration of the while-loop at line 2 of compression phase(), the most expensive task is that of computing the matching M at line 4. Recall that, according to Lemma 3, the while-loop at line 2 iterates at most d S,T times. We conclude that, in this case, the compression phase() halts within the following time bound:

1 . 2 .

 12 There exists an algorithm for solving the Decision-Task of Hy-stCon within O(min( |F | d S,T n, |F |) |F | 2 d 4 S,T n 2 ) time. There exists an algorithm for solving the Search-Task of Hy-stCon within O(min( |F | d S,T n, |F |) |F | 2 d 4 S,T n 2 + |F | 5/2 n 3/2 d S,T ) time.

Theorem 3 .

 3 There exists an algorithm for computing all Lehman-Ron paths within time O m 5/2 n 3/2 d on any Lehman-Ron input R, S, ϕ, n with |R| = |S| = m, where d is the distance between R and S and n is the size of the underlying ground set.

Figure 1 :

 1 Figure 1: A double bfs phase() on H 3 that starts from S = ∅ and T = {1, 2, 3}. The forbidden vertices are F = {{2}, {3}, {1, 2}, {2, 3}}, while the edges explored by BFS ↑ and BFS ↓ are (∅, {1}) and ({1, 2, 3}, {1, 3}) (respectively).

Figure 2 :

 2 Figure 2: The frontier sets considered during the compression phase().

Algorithm 4 : 1 if s = r + 1 then 2 return 3 m 4 Q 5 K

 412345 computing Lehman-Ron's paths. Procedure compute Lehman-Ron paths(R, S, ϕ, n) Input: a Lehman-Ron tuple R, S, ϕ, n . Output: a family of m vertex-disjoint directed paths p1, . . . , pm in Hn such that R ∪ S ⊆ m i=1 pi. compute paths from bijection(S, ϕ, n); ← |S|; // assume |S| = |R| ← compute Q(S); ← compute auxiliary network(R, Q, S);

n

  are such that |S| = |R| = m, 2. r, s and n ∈ N are such that 0 ≤ r < s ≤ n, and 3. ϕ : S → R is a bijection such that ∀ S ∈ S : ϕ(S) ⊂ S.

n

  where |R| = |S| = m and 0 ≤ r < s ≤ n. Let Q (resp. P) be the set of vertices in H

Lemma 2 .

 2 Each iteration of the while-loop at line 2 of compression phase() increases ℓ ↑ +ℓ ↓ by at least one unit, either until ℓ ↑ +ℓ ↓ = d S,T or until the procedure halts by reaching either line 10, line 16 or line 19. Proof. Consider any iteration of the while-loop at line 2 of compression phase(). Let G be the bipartite graph computed at line 3, and let M be the matching of G computed at line 4. If |M| > |F |, then line 10 gets executed, so the procedure halts within a finite number of steps by virtue of our discussion in Appendix B.1. Otherwise |M| ≤ |F |. Recall that, since |M| ≤ |F |, then M a maximum matching of G; also recall that X S = X ∩ S where X is a minimum vertex cover of G (line 12). Since |X | = |M|, then |X S | ≤ |X | = |M| ≤ |F |. Moreover, since |M| ≤ |F |, double-bfs phase() gets invoked at line 14 on input X S , T , F , ℓ ↓ , ℓ ↑ , d S,T , n and halts within a finite number of steps by Lemma 1.

Lemma 5 .

 5 Assume that any invocation of compression phase() halts by returning YES, p . Then p is a directed path in H n that goes from source S to target T avoiding F .Proof. If compression phase() returns p as output, then the last iteration of the while-loop at line 2 must reach either line 10 or line 19:1. Assume that line 10 is reached at the last iteration. Then, during that iteration, the matching M (computed at line 4 on input G) has size |M| > |F |.Recall that G is a bipartite graph on bipartition (S, T ). Let M S (resp. M T be the subset of all vertices in S (resp. T ) that belong to some edge in M. Then, by Theorem 2, there exist |M| vertex-disjoint directed paths in H n , say p 1 , p 2 , . . . , p |M| , whose union contains all the vertices in M S and M T . Since |M| > |F |, at least one of those paths -say,

T

  , then clearly p goes from S to X (1) T . This implies the base case. -Inductive Step. Let us assume, by induction hypothesis, that the claim holds for some i ∈ [max i -1], and let us prove it for i + 1. By induction hypothesis, p either goes from X (i) S to T or from S to i j=1 X (j) T in H n . If p goes from X

  Since p either goes fromX (i+1) S to T , or from S to X (i+1) T , or from S to i j=1 X (j) Tin H n , we have that p either goes from X in H n , thus concluding the induction and the proof of Lemma 8.

t

  M = O min( |V G |, |F |) |E G | = O min |F | d S,T n, |F | |F | 2 d 2 S,T n 2 .

t 3 S,T n 2 . 2 .

 322 M d S,T = O min |F | d S,T n, |F | |F | 2 d In the case where compute Lehman-Ron paths() gets executed, which happens whenever |M| = |F | + 1, we must now take its time complexity into account, which we analyze below. First, consider the set M S computed at line 6 of compression phase(). The following bound holds on its size: |M S | = |M| = |F | + 1. The same bound holds for the set M T ⊆ T which is computed at line 7namely: |M T | = |M| = |F | + 1. By Theorem 3, provided that we consider the parameter m = |M| = O(|F |), invoking compute Lehman-Ron paths() on input M S , M T , M, n takes time at most t LR , where:t LR = O m 5/2 n 3/2 d S,T = O |F | 5/2 n 3/2 d S,T .Recall that, by Lemma 3, the while-loop at line 2 iterates at most d S,T times. At each of such iterations, a brand new matching M gets computed at line 4. Finally, at the very last of such iterations, provided that |M| > |F |, then the procedure compute Lehman-Ron paths() is invoked at line 8. Therefore, we conclude that whenever compression phase() executes compute Lehman-Ron paths() at line 8, then it halts within the following time bound: t M d S,T + t LR = O min |F | d S,T n, |F | |F | 2 d 3 S,T n 2 + |F | 5/2 n 3/2 d S,T .

  then the procedure relies on Theorem 3 to compute a family p

1 , p 2 , . . . , p |M| of |M| vertex-disjoint directed paths in H n that go from S to T . In order to do that, the procedure considers the subset M S ⊆ S (resp. M T ⊆ T ) of all vertices in S (resp. in T ) that are incident to some edge in M (lines 6 and 7). Notice that the matching M can be viewed as a bijection between M S and M T . Then, the algorithm underlying Theorem 3 gets invoked on input M S , M T , M, n (line 8). Once all the Lehman-Ron paths p 1 , p 2 , . . . , p |M| have been found, it is then possible to reconstruct the sought directed path p in H n that goes from source S to target T avoiding F (line 9). In fact, since |M| > |F | by hypothesis, and since p 1 , p 2 , . . . , p |M| are distinct and pairwise vertex-disjoint, there must exist at least one path p i that goes from S to T avoiding F . It is therefore sufficient to find such a path

  |M| ≤ |F |, then the compression phase() aims to compress the size of T down to |T ′ | ≤ |F | d S,T as follows.Notice that in this case M is a maximum cardinality matching of G, because |M| ≤ |F |. So, the algorithm computes a minimum cardinality vertex-cover X of G at line 11, whose size is |M| by König's theorem[START_REF] Diestel | Graph Theory[END_REF]. The algorithm then proceeds at line 12 by considering the set X S = X ∩ S (resp. X T = X ∩ T ) of all vertices that lie both in the vertex-cover X and in the frontier set S (resp. T ). Here, it is crucial to notice that both|X S | ≤ |F | and |X T | ≤ |F | hold, because |X | = |M| ≤ |F |.The fact that, since X is a vertex-cover of G, any directed path in H n that goes from S to T must go either from X S to T or from S \ X S to X T plays a pivotal role. Stated otherwise, there exists no directed path in H n that goes from S \ X S to T \ X T , simply because X is a vertex cover of G. At that point, the compression T ′ gets enriched with X T at line 13.Then, compression phase() seeks a directed path in H n that eventually goes from X S to T . This is done at line 14 by running double-bfs phase() on X S , T , F , ℓ ↑ , ℓ ↓ , d S,T , n . Since |X S | ≤ |F |, that execution results into an update of both the frontier set S and of its level counter ℓ ↑ . Let S (i+1) be the updated value of S and let ℓ be that of ℓ ↑ . Note that, since |T | > |F | d S,T holds as a pre-condition of compression phase(), neither T nor ℓ ↓ are ever updated at line 14. Upon completion of this supplementary double-bfs phase(), if S

	(i+1)
	↑

Dear reviewers: see Appendix B.2 for correctness and Appendix B.3 for complexity.

See Appendix B.1 for all the technical details.

See Appendix B.2-B.3 for details on correctness and complexity.

See Appendix B.2

See Appendix B.2

2. Proof of [START_REF] Bergeron | Reconstructing ancestral gene orders using conserved intervals[END_REF]. In order to prove [START_REF] Bergeron | Reconstructing ancestral gene orders using conserved intervals[END_REF], we exhibit a number of invariants which hold for each iteration of the while-loop at line 2 of compression phase().

In what follows, we assume that the procedure compression phase() gets invoked on input S, T , F , ℓ ↑ , ℓ ↓ , d S,T , n , and that S (0) = S holds by notational convention.

Lemma 6. Let i ∈ [max i ] be any iteration of the while-loop at line 2 of compression phase(). Let p be any directed path in H n that goes from S (i-1) to T . Then p goes either from X (i)

S to T or from S (i-1) \ X (i)

S to X (i)

T . In other words, there exists no directed path in H n that goes from

Proof. Recall that X (i) is a vertex cover of the bipartite graph defined as G (i) = ((S (i-1) , T ), ⊂), which is constructed during the i-th iteration of line 3 within the procedure compression phase(). Also,

T would imply the existence of some edge of G (i) that would be uncovered by X (i) , contradicting the fact that

Lemma 7. Let i ∈ [max i ] be any iteration of the while-loop at line 2 of compression phase(). Let U be any subset of S (i-1) and let V be any subset of T . Let p be any directed path in H n that goes from U to V . Then p goes from S to V in H n .

Proof. Induction on i ∈ [max i ].

-Base Case. If i = 1, recall that S (0) = S. Then U ⊆ S, which implies the base case. -Inductive Step. Let us assume, by induction hypothesis, that the claim holds for some i ∈ [max i -1] and let us prove it for i + 1. So, let U ⊆ S (i) , and let p by any directed path in H n that goes from U to V . Recall that S (i) is the frontier set that is returned by an invocation of double-bfs phase() on input X (i) S , at the i-th iteration of line 14, within compression phase(). This amounts to saying that all vertices in S (i) have been discovered by a BFS starting from 1) . Therefore, p is indeed a directed path in H n that goes from S (i-1) to V in H n . By induction hypothesis, the thesis follows.

Lemma 8. Let i ∈ [max i ] be any index of iteration of the while-loop at line 2 of compression phase(). Let p be a directed path in H n that goes from S to T avoiding F . Then, p goes either from

Proof. It is sufficient to prove that bfs phase() always halts within O(|F | d 2 S,T n) time. Recall that, by Lemma 1, the while-loop at line 1 of bfs phase() iterates at most d S,T times. At each iteration, next step bfs() gets invoked on some input set X ∈ ℘ n and flag variable drt ∈ {in, out} (see line 2 of bfs phase()).

We argue that each of these invocations takes at most O(|F | d S,T n) time. Assume that N drt is N in when drt = in, and that it is N out otherwise. Then, each invocation of next step bfs() takes O(|X | max v∈X {|N drt (v)|}) time, because it involves visiting N drt (v) for each v ∈ X ; still, in order to enter the while-loop at line 1 of bfs phase(), we must have |X | ≤ |F | d S,T , and moreover we have

Since the total number of iterations is bounded above by d S,T , the bound follows.

Lemma 12. Assume that compression phase() gets invoked at line 11 of the procedure solve Hy-stCon(). If compression phase() halts without ever executing the procedure compute Lehman-Ron paths() at line 8, then it halts within the following time bound:

Otherwise, if compression phase() executes compute Lehman-Ron paths() at line 8, then it halts within the following time bound:

Proof. We start with some preliminary observations that will be useful in proving time bounds (1) and ( 2). Let us assume that compression phase() is invoked on the following input S, T , F , ℓ ↑ , ℓ ↓ , d S,T , n at line 11 of solve Hy-stCon(). We argue that the following bounds hold on the size of S and T :

In fact, notice that S and T were computed during a previous invocation of double-bfs phase(), at line 5 of solve Hy-stCon(). Therefore, it suffices to consider the set X which is computed by passing through the while-loop at line 1 of bfs phase(). The condition for entering that while-loop requires |X | ≤ |F | d S,T . Therefore, as soon as bfs phase() exits that while-loop, we must have |X | ≤ |F | d S,T n. This implies the bounds specified by [START_REF] Cuénot | Les races pures et leurs combinaisons chez les souris[END_REF].

Let us now consider the bipartite graph G = (V G , E G ) = ((S, T ), ⊂), which is constructed at line 3 of compression phase(). Since

we also have the following bound on the size of its edge set:

We can now proceed with the proof of the two time bounds.

Proposition 8. The Decision-Task of Hy-stCon can be solved within the following time bound on any input S, T, F , n :

Proof. Let us consider the procedure solve Hy-stCon() of Algorithm 1. By Proposition 5, the while-loop at line 4 iterates at most d S,T times. At each iteration, double-bfs phase() is invoked at line 5, and compression phase() is invoked soon after at line 11. By Lemma 11, the most expensive one between the two procedures is clearly compression phase(). Recall that, if we are content with solving the Decision-Task of Hy-stCon, then the compression phase() can be implemented so that it always halts without ever executing the procedure compute Lehman-Ron paths() at line 8. Therefore, by Lemma 12, each invocation of compression phase() takes time at most

Since we have at most d S,T of such invocations, then the thesis follows. Since there are at most d S,T invocations of the compression phase(), the thesis follows.