Spyros Angelopoulos

Christoph Dürr

Thomas Lidbetter

The expanding search ratio of a graph

We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. A sequence of edges is chosen starting from a given root vertex such that each edge is adjacent to a previously chosen edge. This search paradigm, known as expanding search was recently introduced by Alpern and Lidbetter (2013) for modeling problems such as searching for coal or minesweeping in which the cost of re-exploration is negligible. It can also be used to model a team of searchers successively splitting up in the search for a hidden adversary or explosive device, for example. We define the search ratio of an expanding search as the maximum over all vertices of the ratio of the time taken to reach the vertex and the shortestpath cost to it from the root. This can be interpreted as a measure of the multiplicative regret incurred in searching, and similar objectives have previously been studied in the context of conventional (pathwise) search. In this paper we address algorithmic and computational issues of minimizing the search ratio over all expanding searches, for a variety of search environments, including general graphs, trees and star-like graphs. Our main results focus on the problem of finding the randomized expanding search with minimum expected search ratio, which is equivalent to solving a zero-sum game between a Searcher and a Hider. We solve these problems for certain classes of graphs, and obtain constant-factor approximations for others.

Introduction

We consider the problem faced by a Searcher of locating a stationary target or Hider located at a vertex of a connected edge-weighted graph G. We interpret the weight of an edge as the time taken to search that edge. The search must start at a given vertex O called the root and consists of a sequence of edges chosen in such a way that every edge must be adjacent to some previous edge, so that the set of edges that have been searched at any point forms a connected subgraph of G. For a given search and a given vertex v at which the Hider is located, the search time of v is the time taken to search all the edges up to and including the first edge that is incident to v.

This paradigm of search, recently introduced by [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF] is known as expanding search, in contrast to the more usual search paradigm, referred to here as pathwise search in which a search corresponds to a walk in a graph. The expanding search paradigm is an appropriate model for situations in which the cost of "re-exploration" is negligible compared to the cost of searching, for example when mining coal: here digging into a new site is far more costly than moving the drill through an area that has already been dug. Another situation to which this principle applies is securing a dangerous area from hidden explosives; once the area is deemed clear, the searchers can navigate through it at a much lower cost. An alternative interpretation, described in detail in [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF], is that of a team of searchers splitting up in the search for a target. We illustrate the concept of expanding search on a graph with an example. Consider the graph G depicted in Figure 1 with root O; vertices A, B, C and D; and edges OA, OB, BC and BD of lengths 3, 2, 2 and 1, respectively. An example of an expanding search on G, which we will denote by S, is the sequence of edges, OB, OA, BD, BC. Under S, the search time of vertex D is 2 + 3 + 1 = 6. [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF] take the approach of seeking randomized search strategies that minimize the expected search time in the worst case: that is, the maximum expected search time over all vertices. They also consider the problem of determining the search that minimizes some weighted average of the search times of the vertices. In this paper, we take an alternative approach by considering a normalized version of the search time obtained by dividing the search time of a vertex v by the length of the shortest path from O to v. For example, in the graph G depicted in Figure 1, the normalized search time under S of vertex D is 6/3 = 2 since D is at a distance of 2 + 1 = 3 from the root. The maximum the normalized search time takes over all vertices of the graph is called the search ratio. In G, the normalized search time of S is maximized at B, where it is equal to (3 + 2)/2 = 2.5, so this is the search ratio of S. This paper studies the problem of finding an expanding search with minimum search ratio.

Our choice of the search ratio as the objective for expanding search is motivated by earlier work by [START_REF] Koutsoupias | Searching a fixed graph[END_REF], who introduced this objective in the context of pathwise search. Their approach is analogous to the competitive analysis of online algorithms, in which the performance of an online algorithm is measured against the performance of an optimal offline algorithm; more precisely, the optimal offline algorithm corresponds to simply taking the shortest path to the target. As in [START_REF] Koutsoupias | Searching a fixed graph[END_REF], we consider not only deterministic searches, but also randomized searches, with the aim of finding the randomized expanding search that minimizes the expected value of the normalized search time in the worst case. Equivalently, we view this problem as a zero-sum game between a Hider who chooses a vertex of the graph and a Searcher who chooses an expanding search. The payoff, which the Hider seeks to maximize and the Searcher to minimize, is the normalized search time. This puts our work in the broader category of search games, a more general framework for games played between a Hider who chooses a point in some search space and a Searcher who makes some choice of how to navigate through the space with the aim of minimizing a given cost function.

It is worth mentioning that normalized cost formulations very similar to the search ratio have also been previously studied in the context of searching in unbounded domains (see, e.g., the early work of [START_REF] Beck | Yet more on the linear search problem[END_REF] on the linear search problem as well as the work of [START_REF] Gal | A general search game[END_REF] in the context of star search). In such domains, the Hider can ensure the search time is arbitrarily large by choosing positions arbitrarily far from the root. This observation motivates the need for normalizing the search cost, which is accomplished by dividing this cost by the shortest-path cost from the root to the Hider.

In the spirit of the work of [START_REF] Koutsoupias | Searching a fixed graph[END_REF], in this paper we focus on computational and algorithmic issues of expanding search. We note that [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF] follow a purely mathematical approach to analyzing expanding search, with an emphasis on evaluating the value of the corresponding zero-sum games; computational and algorithmic issues are not considered. Table 1 illustrates the context of our work with respect to previous work. We note that the problem of minimizing the average search time of the vertices of a graph assuming the pathwise search formulation is precisely the well-known problem of minimizing the latency of a graph, also known as the Traveling Repairman problem (see [START_REF] Blum | The minimum latency problem[END_REF], [START_REF] Goemans | An improved approximation ratio for the minimum latency problem[END_REF], [START_REF] Arora | Approximation schemes for minimum latency problems[END_REF], [START_REF] Sitters | The minimum latency problem is NP-hard for weighted trees[END_REF] for some representative results on this problem). The problem of choosing the randomized (pathwise) search that minimizes the maximum expected search time of points of a network was formalized by [START_REF] Gal | Search games with mobile and immobile hider[END_REF], and has been extensively studied, as discussed in Subsection 1.1. Gal's search game [START_REF] Gal | Search games with mobile and immobile hider[END_REF])

Searching a fixed graph [START_REF] Koutsoupias | Searching a fixed graph[END_REF])

Expanding

Expanding search [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF])

Expanding search [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF])

This work

Related Work

Search theory (and its computational counterpart) has a very rich history of research. We give a summary of some results that are pertinent to this work. Following the formalization of network search games by [START_REF] Gal | Search games with mobile and immobile hider[END_REF] in the framework of pathwise search with un-normalized search time, the problem has had considerable attention, for example in [START_REF] Reijnierse | Search games with immobile hider[END_REF], [START_REF] Pavlovic | A search game on the union of graphs with immobile hider[END_REF] and [START_REF] Gal | On the optimality of a simple strategy for searching graphs[END_REF]. In the latter work the solution of the game was found for all weakly Eulerian networks. Recent variations on Gal's original game include a setting in which the Searcher chooses his own starting point in [START_REF] Dagan | Network search games, with arbitrary searcher starting point[END_REF] and [START_REF] Alpern | Network search games with immobile hider, without a designated searcher starting point[END_REF], and the setting in which the Hider is restricted to choosing vertices that have search costs in [START_REF] Baston | Search games on networks with travelling and search costs and with arbitrary searcher starting points[END_REF] and [START_REF] Baston | Search games on a network with travelling and search costs[END_REF].

Expanding search was introduced by [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF] in the setting in which the payoff is the total (un-normalized) cost of finding the Hider. Among other results, Alpern and Lidbetter solved the game in the case that the network is either a tree or 2-edge-connected. This model was extended by [START_REF] Lidbetter | Search games with multiple hidden objects[END_REF] to a setting in which the Searcher must locate multiple hidden objects.

Much of the search games literature been purely mathematical, with less emphasis on issues of complexity, a notable exception being the work of von [START_REF] Stengel | Complexity of searching an immobile hider in a graph[END_REF]. The search ratio of pathwise search was studied in [START_REF] Koutsoupias | Searching a fixed graph[END_REF], who showed that the problem of computing the optimal search ratio in a given undirected graph is NP-complete (and MAX-SNP hard to approximate). They also gave a search strategy based on repeated executions of depth-first searches with geometrically increasing depths that achieves a constant approximation of the (deterministic) competitive ratio. Similar results can be obtained concerning the randomized competitive ratio (assuming that the Searcher randomizes over its strategy space). Connections between graph searching and other classic optimization problems such as the Traveling Salesman problem and the Minimum Latency problem were shown by [START_REF] Ausiello | On salesmen, repairmen, spiders, and other traveling agents[END_REF]. The setting in which the search graph is revealed as the search progresses was studied by [START_REF] Fleischer | Competitive online approximation of the optimal search ratio[END_REF]. The latter also addressed connections between searching and exploring an environment, where the latter operation is defined as moving around the environment until all possible hiding positions are "visible" (the formal definition of visibility depends on the particular environment).

A specific search environment that has attracted considerable attention in the search literature is the star-like environment. More specifically, in the unbounded variant, the search domain consists of a set of infinite lines which have a common intersection point (the root of the Searcher); this problem is also known as ray searching. Ray searching is a natural generalization of the well-known linear search problem introduced independently by [START_REF] Beck | On the linear search problem[END_REF] and [START_REF] Bellman | An optimal search problem[END_REF] (informally called the "cow-path problem"). Optimal strategies for linear search under the (deterministic) competitive ratio were first given by [START_REF] Beck | Yet more on the linear search problem[END_REF]. [START_REF] Gal | Minimax solutions for linear search problems[END_REF] gave optimal strategies for the generalized problem of ray searching, a result that was rediscovered later by computer scientists (see [START_REF] Baeza-Yates | Searching in the plane[END_REF]). Other related work includes the study of randomization by [START_REF] Schuierer | A lower bound for randomized searching on m rays[END_REF] and [START_REF] Kao | Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem[END_REF]; multi-Searcher strategies by López-Ortiz and [START_REF] López-Ortiz | On-line parallel heuristics, processor scheduling and robot searching under the competitive framework[END_REF]; searching with turn cost by [START_REF] Demaine | Online searching with turn cost[END_REF]; the variant in which some probabilistic information on target placement is known by [START_REF] Jaillet | Online searching[END_REF] and [START_REF] Kao | Algorithms for informed cows[END_REF]; and the related problem of designing hybrid algorithms by [START_REF] Kao | Optimal constructions of hybrid algorithms[END_REF].

Bounded star search, namely the case in which an upper bound is known on the distance of the target from the root was studied in López-Ortiz and Schierer (2001) and [START_REF] Bose | Searching on a line: A complete characterization of the optimal solution[END_REF]. New performance measures that are applicable in the context of multi-target searching were introduced by [START_REF] Kirkpatrick | Hyperbolic dovetailing[END_REF] and [START_REF] Mcgregor | The oil searching problem[END_REF] (i.e., the setting in which there are more than one Hider and the Searcher must locate one of them). The problem of locating a certain number among the many Hiders was studied by [START_REF] Angelopoulos | Multi-target ray searching problems[END_REF].

It must be emphasized that star search has applications that are not necessarily confined to the concept of locating a target (which explains its significance and popularity). Indeed star search offers an abstraction that applies naturally in settings in which we seek an intelligent allocation of resources to tasks. More precisely, it captures decision-making aspects when the objective is to successfully complete at least one task, without knowing in advance the completion time of each task. Some concrete applications include: drilling for oil in a number of different locations in [START_REF] Mcgregor | The oil searching problem[END_REF]; the design of efficient interruptible algorithms, i.e., algorithms that return acceptable solutions even if interrupted during their execution in [START_REF] Bernstein | Scheduling contract algorithms on multiple processors[END_REF] and [START_REF] Angelopoulos | Further connections between contract-scheduling and ray-searching problems[END_REF]; and database query optimization (in particular, pipelined filter ordering in [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF]). We discuss the latter work in more detail in Section 5.

Contribution

In this work we study expanding search under the search-ratio measure, assuming a variety of search spaces such as stars, trees, and general edge-weighted, undirected graphs. Our main motivation is to explore how the transition from pathwise to expanding search affects the deterministic and the randomized search ratios.

We begin in Section 2 with the definitions of the (expanding) search ratio and randomized search ratio. In Section 3 we show that the problem of finding the optimal (deterministic) search ratio is NP-hard (using a substantially more complicated reduction than for pathwise search in [START_REF] Koutsoupias | Searching a fixed graph[END_REF]). Applying well-known iterative deepening techniques, we obtain a 4 ln(4) ≈ 5.55 approximation.

Our main technical results, presented in Section 4, apply to the setting where the graph is an unweighted graph or a weighted tree. Here, it is easy to show that an optimal deterministic search strategy searches the vertices in non-decreasing order of distance from the root (and chooses the corresponding edges accordingly). This strategy is also a 2-approximation of the randomized search ratio. To see why the randomized search ratio might as little as half of the deterministic search ratio, suppose two vertices are at approximately the same distance from the root. Then it is possible that by using randomization, the expected search times of the vertices can be "smoothed out", which may decrease the randomized search ratio. Therefore, we define a randomized search strategy that approximates the randomized search ratio within a factor of 5/4, representing a significant improvement over the aforementioned 2-approximation. The idea of the strategy is to choose a subtree containing nodes within some randomly chosen radius of the root, search it, contract this subtree to the root, and repeat. The method of searching each of these subtrees is by what we call a Random Depth-First Search, which is an equiprobable choice of a depth-first search S and the depth-first search that arrives at the leaves of the trees in the reverse order to S. Thus vertices of the graph at a similar distance to each other are reached at roughly the same time, on average. Improved approximations via randomization are usually not easy to achieve (see, e.g. [START_REF] Koutsoupias | Searching a fixed graph[END_REF]). Our result confirms the intuitive expectation that randomization has significant benefits.

In Section 5 we study the problem of bounding the randomized search ratio of a weighted graph, as function of the number of its vertices. First, we argue that in the case of a star graph, the setting is equivalent to a problem considered by [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF] in the context of pipelined filter ordering in database query optimization (though their problem is not explicitly described as a search game). For this special case, they presented an algorithm for constructing the optimal randomized search strategy and an expression for the randomized search ratio. We show that the results of [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF] imply that the randomized search ratio of a star of n vertices plus the root cannot exceed (n + 1)/2; furthermore, we show that the same result applies to general weighted graphs. We note, however, that the result of [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF] follows from a complicated flow-based algorithm, which does not readily offer intuition about why the uniform star has the maximum randomized search ratio. For this reason, we provide an alternative proof of the upper bound in star graphs (which we obtained independently in the conference version of the paper [START_REF] Angelopoulos | The expanding search ratio of a graph[END_REF]), and which is based on the analysis of a simple, intuitive search strategy using game-theoretic techniques.

As argued earlier, star-search problems have applications that transcend searching. This is indeed the case in expanding search. Consider the following problem: we are given a collection of n boxes, among which only one contains a prize. We can open a box i at cost d i . We seek a (randomized) strategy for locating the prize, and the randomized search ratio of the strategy is the total expected cost of all opened boxes, divided by the cost of the box that holds the prize. This problem is equivalent to the problem of finding the (randomized) search ratio of a star graph.

We may also interpret expanding search on a tree as the scheduling of jobs with precedence constraints, where each vertex v of the tree corresponds to a job whose processing time is the length of the edge immediately preceding v, and all jobs on the path from v to the root must be executed before v can be executed. An expanding search corresponds to a feasible schedule, and the distance of v from the root corresponds to the minimum possible completion time of v over all choices of schedule, which we can interpret as the offline cost of completing v. We can then consider the problem of choosing a schedule to minimize the maximum ratio of the completion time of a job to its "offline cost". This is exactly our expanding search problem.

Since our main objective is to study the algorithmic and computational impact of re-exploration due to the transition from pathwise search to expanding search, it is important to compare our results to the best-known bounds in the context of pathwise search. More precisely, for unweighted graphs, [START_REF] Koutsoupias | Searching a fixed graph[END_REF] gives asymptotic approximations of the deterministic and randomized search ratios equal to 6 and 8.98, respectively, but its techniques appear to be applicable also to general graphs, at the expense of somewhat larger, but nevertheless constant approximations. Furthermore, [START_REF] Koutsoupias | Searching a fixed graph[END_REF] note that the problems of computing the search ratios of trees are "surprisingly hard". In contrast, for expanding search of unweighted graphs and (weighted) trees we obtain optimal algorithms and a 5/4 (asymptotic) approximation of the deterministic and randomized search ratios, respectively. We thus demonstrate that the transition from pathwise to expanding search can yield dramatic improvements in terms of the approximability of the search ratios. For general graphs, we note that our 5.55 approximation is strict, and not asymptotic. As a last observation, we note that the pathwise and expanding search algorithms appear to depend crucially on the approximability of the Traveling Salesman problem and the Steiner Tree problem, respectively.

Preliminaries

Let G = (E, V) be an undirected, connected, edge-weighted graph with |V| = n + 1, and a distinguished root vertex O ∈ V. The weight or length of edge e ∈ E, denoted by λ(e), represents the time required to search that edge (we assume, via normalization, that λ(e) ≥ 1 for all edges e). For subgraphs or subsets of edges X, we write λ(X) for the sum of the lengths of all the edges in X. We will call a graph of unit edge weights unweighted, otherwise it is weighted.

An expanding search, or simply search strategy on G is a sequence of edges, starting from the root, chosen so that the set of edges that have been searched at any given point in the sequence is a connected, increasing set. More precisely:

Definition 1 An expanding search S on a graph G with root vertex O is a sequence of edges (e 1 , . . . , e n ) such that every prefix {e 1 , . . . , e k }, k = 1, . . . , n is a subtree of G rooted at O. We denote the set of all expanding searches on (G, O) by S = S(G, O).

We note that if we wished, we could define search strategies less restrictively so that every prefix is simply a connected subgraph rather than a tree, but it will soon be clear that strategies fulfilling Definition 1 are dominant.

For a given vertex v ∈ V and a given search strategy S = (e 1 , . . . , e n ), denote by S v the first prefix {e 1 , . . . , e k } that covers v. The search time, T (S, v) of v is the total time λ(S v ) taken to search all the edges before v is discovered. Let d(v) denote the length of the shortest path from O to v, which is the minimum time for the Searcher to discover v.

For v = O the normalized search time is denoted by T (S, v) = T (S, v)/d(v). Definition 2 The (deterministic) search ratio σ S = σ S (G) of a search strategy S for the graph G is defined as σ S (G) = max v∈V-{O} T (S, v). The (deterministic) search ratio, σ = σ(G) of G is defined as σ(G) = min S∈S σ S (G).
If σ S = σ we say S is optimal.

We will also consider randomized search strategies, that is some probabilistic choice of search strategies. Following the standard notation, we denote randomized strategies by lower case letters, and for a randomized search strategy s and a vertex v, we extend the notation T (s, v) to denote the expected search time of v. Similarly we write T (s, v) for the expected normalized search time T (s, v)/d(v).

Definition 3 The randomized search ratio ρ s = ρ s (G) of a randomized search strategy s for the graph G is given by

ρ s (G) = max v∈V-{O} T (s, v).
The randomized search ratio, ρ = ρ(G) of G is given by

ρ(G) = inf s ρ s (G),
where the infinum is taken over all possible randomized search strategies s. If ρ s = ρ we say s is optimal.

We will view the randomized search ratio ρ through the lens of a finite zero-sum game between a Searcher and a malevolent Hider. The Searcher's pure strategy set is the set S of expanding searches and the Hider's pure strategy set is the set V -{O} of non-root vertices of G. For a Hider strategy v ∈ V -{O} and a Searcher strategy S ∈ S, the payoff of the game is T (S, v), which the Hider wishes to maximize and the Searcher wishes to minimize. Since the strategy sets are finite, the game has a value and optimal mixed strategies for both players. By the standard minimax theorem for zero-sum games, the value of the game is equal to the randomized search ratio and an optimal randomized search strategy is an optimal mixed strategy for the Searcher in the game. It follows that the infinum in Definition 3 is in fact a minimum. A mixed strategy for the Hider is a probability distribution h over the vertices V -{O}, and for mixed strategies h and s of the Hider and Searcher respectively, we write T (s, h) and T (s, h) for the corresponding expected search time and expected normalized search time.

We will obtain lower bounds for ρ(G) by giving explicit Hider strategies. More precisely, if h is a given mixed Hider strategy, the minimax theorem implies that ρ(G) ≥ min S∈S T (S, h).

The search ratio of weighted graphs

In this section we show that the problem of computing the (deterministic) search ratio is NP-hard. We also give a search strategy that achieves a 4 ln(4) ≈ 5.55 approximation ratio.

Theorem 1 Given a graph G with root O and a constant R ≥ 0, it is NP-Complete to decide whether σ(G) ≤ R.

Proof: The proof is based on a reduction from 3-SAT. Given a 3-SAT instance consisting of n variables and m clauses with m ≥ n, we construct an instance of our problem.

We construct the graph G consisting of vertices O, P , a vertex C j for every clause (the clause vertices), vertices X i (the variable vertices) and vertices X 0 i , X 1 i (the literal vertices) for every variable. For every i = 1, . . . , n there are unit length edges of the form (X i , X 0 i ), (X i , X 1 i ), (P, X 0 i ), (P, X 1 i ). For every variable x i appearing positively in the j-th clause there is an edge (C j , X 1 i ) of length 2 and for every variable x i appearing negatively in the j-th clause there is an edge (C j , X 0 i ) of length 2. For every j = 1, . . . , m there is an edge (O, C j ) of length 3 and for every i = 1, . . . , n there is an edge (O, X i ) of length 3. Finally, there is an edge (O, P ) of length 3. We fix R = 1 + 2 3 (n + m). The construction is shown in Figure 2. Note that the vertices can be partitioned according to their distance from O. In particular, vertex P , as well as variable and clause vertices have distances 3, whereas literal vertices have distance 4.

We must show that there exists a boolean assignment to the variables satisfying all clauses if and only if the search ratio of G is at most R.

For the easy direction of the proof, consider a boolean assignment b ∈ {0, 1} n satisfying all clauses. We will show that there is a search strategy with search ratio at most R. First we construct a tree covering all distance 3 vertices with total length 3R. The first edge is (O, P ), followed by the edges (P, X b i i ) for every i. Then for every j, there is an edge (X b i i , C j ) where X b i i corresponds to an arbitrary literal satisfying the j-th clause. Finally the tree also contains the edges (X b i i , X i ) for all i. We denote the tree constructed from b by H b . The total length of H b is 3 + 2n + 2m which is exactly 3R by the choice of R. To turn the tree into a search strategy S we order the edges from H b as enumerated above and complete them with the edges (P, X 1-b i i ) for all i. We have σ S (P ) = 1, σ S (C j ) ≤ 3R/3, σ S (X i ) ≤ 3R/3 and σ(X x i ) ≤ (3R + n)/4 ≤ R for every i, j, x, which shows that the search ratio of G is at most R.

For the hard direction, assume that there is a search strategy with search ratio at most R. Let H be its shortest prefix covering all distance 3 vertices. By the definition of the search ratio we know that λ(H) ≤ 3R. Through a sequence of transformations we turn H into a tree of the form H b with λ(H b ) ≤ λ(H). This will show that b is a satisfying assignment for the formula and complete the proof of the theorem.

• If (O, P ) does not belong to H we add it. This must create a cycle, containing an edge of the form (O, v) with v = P . Now we remove this edge, and obtain a tree of the same length.

• If there is an edge (O, C j ) in H for some j, then we replace this edge by the edges (C j , v), (v, P ), where v is a vertex corresponding to a literal from the j-th clause. Some of the added edges might already have been present. The result is a tree of no greater length.

• If there is an edge of the form (O, X i ) in H for some i, then we replace this edge by the edges (X i , X 0 i ), (X 0 i , P ). As a result the length of the tree decreased by 1.

• At this stage we know that O is only connected to P in the tree.

• If there is a vertex C j connected to several vertices v 1 , . . . , v k for k ≥ 2, then we remove the edges (C j , v 1 ), . . . , (C j , v k ). Hence, the tree now contains k + 1 components, the isolated vertex C j itself and k components containing each some distinct vertex v i . Only one of them also contains P . Without loss of generality suppose that v 1 and P are in the same component.

Then we add (C j , v 1 ) back to H and add edges (v i , P ) for each i = 2, . . . , k. This way we maintain a tree, and its length decreases by k -1.

• At this stage we know that every C j vertex is incident to exactly one length 2 edge. Also for every i = 1, . . . , n, among the vertices {X i , X 0 i , X 1 i , P } there are at least two edges, one adjacent to X i and one adjacent to P . The last edge is necessary since otherwise there would be no connection from the vertices {X i , X 0 i , X 1 i } to P , since by the previous point we know that such a path could not go through a clause vertex. Let k be the total number of additional edges that exist among the vertex sets {X i , X 0 i , X 1 i , P } over all i = 1, . . . , n. Then the total length of H is 3 + 2m + 2n + k, which by assumption is at most 3R. By the choice of R we have equality and thus k = 0. This shows that H is a tree of the form H b for some b ∈ {0, 1} n , which is a satisfying assignment.

Using an approach similar to the doubling heuristic of [START_REF] Koutsoupias | Searching a fixed graph[END_REF], we obtain a constant-approximation algorithm for computing the search ratio. It is worth pointing out that the algorithm doubles the radius, and explores the resulting graph by computing a Steiner tree of the corresponding vertex set (in contrast to pathwise search, in which the resulting graph is simply explored depth-first).

Theorem 2 There is a polynomial-time search algorithm that approximates σ(G) within a factor of 4 ln(4) + < 5.55. We can view the problem of computing G d as the problem of finding a minimum-cost Steiner tree for the set of vertices V d . The best known polynomial time algorithm that approximates the problem within a constant factor is that of [START_REF] Byrka | An improved LP-based approximation for steiner tree[END_REF], which has approximation ratio ln(4) + . Let Ĝd be a subtree of G with total length no greater than ln(4)λ(G d ) that contains all the vertices in V d .

Consider the following family of search strategies S, for fixed 1 = d 0 , d 1 , . . . , d k , where d k is the radius of G. In increasing order of j ≥ 1, search all the edges of Ĝd j in an arbitrary order (omitting those edges that have already been searched). Suppose the Hider is at some vertex v reached in the jth phase of the algorithm. Then d(v) must be at least d j-1 , and

T (S, v) ≤ j i=1 λ( Ĝd i ) d j-1 ≤ ln(4) j i=1 λ(G d i ) d j-1 ≤ ln(4)σ j i=1 d i d j-1
.

It is optimal to choose d i = 2 i (for a proof of this, see [START_REF] Koutsoupias | Searching a fixed graph[END_REF]). So we obtain T (S, v) ≤ 4 ln(4)σ < 5.55σ.

Trees and Unweighted Graphs

In this section we present our main technical results that apply to unweighted graphs and (weighted) trees. For both classes of graph it is easy to show that it is optimal, in the deterministic setting, to search the vertices in non-decreasing order of their distance from the root.

If G is a graph with root O, for any r > 0 let V r be the set of vertices in G at distance no more than r from the root O and let G r be the induced subgraph of G with vertex set V r .

Proposition 1 Let G be a rooted graph and suppose that G is a tree or an unweighted graph. Then an optimal search strategy is to search the vertices in non-decreasing order of their distance from the root. The search ratio σ is given by

(i) σ = sup r>0 λ(Gr) r
if G is a tree and

(ii) σ = sup r>0 |Vr|-1 r if G is an unweighted graph.
Proof: Suppose a search S visits the vertices in some order v 1 , . . . , v n which is not non-decreasing in order of distance from O and let v 0 = O. Let i ≥ 1 be minimal such that d(v i-1 ) < d(v i ) but there exists some j > i such that d(v j ) < d(v i ). (Such an i must exist.) We may assume that j is chosen so that d(v j ) is minimal. Define a new search S that is the same as S except the portion of the search that visits the vertices v i , v i+1 , . . . , v j now visits them in the order v j , v i , v i+1 , . . . , v j-1 . By the minimality of d(v j ), there must be a path from j to O contained in {v 1 , . . . , v i-1 }, so S is a feasible search.

As long as G is a tree or it is unweighted, the new search time of v j under S is smaller, so the new normalized search time is also smaller. The new search times of the vertices v i , . . . , v j-1 are larger, but no greater than the search time of v j under S; also they are further from O than v j , so their new normalized search times are no larger than that of v j under S. The normalized search time of every other vertex is the same under S and S . Thus σ S ≤ σ S .

Repeating this process a finite number of times results in a search that visits the vertices in non-decreasing order of distance from O and has a search ratio at most that of S, so is therefore optimal.

The two expressions for the search ratio of G in the statement of the proposition follow immediately.

Note that the above argument does not work for weighted graphs (as we should expect) since in general, swapping the order in which adjacent vertices are visited changes the search times of the other vertices.

In the randomized setting for trees and unweighted graphs we first show that the optimal deterministic search approximates the optimal randomized search by a factor of 2. To prove this, we use the following collection of lower bounds for ρ. For each non-root vertex v of G, let λ v denote the length of the unique edge incident to v on some shortest path between O and v (so if G is an unweighted graph then λ v = 1) and let λ O = 0. For a set A of vertices, let λ(A) = v∈A λ v and let ∆(A) = v∈A λ v d(v).

Lemma 1 Suppose A = {v 1 , . . . , v m } is a set of non-root vertices of G, and suppose the Hider chooses each v i ∈ A with probability p i = λ v i d(v i )/∆(A). Then the normalized search time T (S, p) of any search S against the Hider strategy p satisfies

T (S, p) ≥ i≤j λ v i λ v j ∆(A) ≥ λ(A) 2 2∆(A) .
Proof: Suppose, without loss of generality, that S is the search strategy that visits the vertices of A in the order v 1 , . . . , v m . Then clearly T (S, v i ) ≥ j≤i λ v j for all v i so the expected value of the search ratio of S, under p is

m i=1 p i T (S, v i ) d(v i ) ≥ m i=1 λ v i d(v i ) d(v i )∆(A) j≤i λ v j = i≤j λ v i λ v j ∆(A) .
The second inequality is trivial. The next proposition follows directly from Lemma 1.

Proposition 2 The randomized search ratio ρ of a tree or unweighted graph satisfies σ/2 ≤ ρ ≤ σ.

Hence the optimal deterministic search is a 2-approximation of the optimal randomized search.

Proof: Let S * be the optimal deterministic search strategy that searches the vertices in nondecreasing order of their distance from the root, and suppose v is a vertex such that σ = σ S * = T (S * , v). If A is the set of non-root vertices at distance no more than d(v), then we must have T (S * , v) = λ(A), so by Lemma 1,

σ ρ ≤ λ(A)/d(v) λ(A) 2 /(2∆(A)) = 2∆(A) d(v)λ(A) ≤ 2, since ∆(A) ≤ λ(A)d(v).
We will show next that we can obtain improved approximations; more precisely we will present and analyze a randomized search for trees or unweighted graphs with approximation ratio asymptotically equal to 5/4. In the case that G is an unweighted graph, we will define the search on some shortest path tree (that is, a spanning tree of G comprising shortest paths from O to each vertex); if G is a weighted tree then we define the search on the whole of G. The idea of the strategy is to partition the vertices of the tree into subsets V 0 , V 1 , . . ., each of which contains vertices whose distances from O are within some interval [x i , x i+1 ], where the x i are chosen randomly according to the method described later in Definition 4. The subsets are then searched one at a time, in increasing order of distance from O. Note that after visiting all the vertices in V 1 ∪ . . . ∪ V j we can contract all the edges searched so far to the root vertex O and consider the problem of how to search the induced subtree G i+1 with vertex set V j+1 ∪ O.

The method of searching each of these subtrees is according to a random depth-first search (or RDFS), which we define as follows. Given a set of vertices H and a depth-first search S of H starting at the root, consider the search S -1 which is the depth-first search of H that arrives at the leaf vertices of H in the reverse order to S. An equiprobable choice of S and S -1 is a RDFS of H. It is straightforward to calculate the maximum expected search time of a RDFS.

Lemma 2 Under any RDFS of a rooted tree H, a vertex v is found in expected time (λ(H) + d(v))/2.

Proof: Suppose S is some depth-first search of H. Let A be the subset of edges searched by S up to and including when v is reached and let B be the subset of edges searched by S -1 up to and including when v is reached. It is easy to see that A ∩ B is the unique path from v to the root. If s is the RDFS that chooses S and S -1 equiprobably, then the expected time T (s, v) of s to reach v is

T (s, v) = (λ(A) + λ(B))/2 = (λ(A ∪ B) + λ(A ∩ B))/2 = (λ(H) + d(v)/2.
We can now define the randomized deepening strategy. Let t be the smallest integer such that every vertex of G is at distance less than 2 t from O.

Definition 4 (Randomized deepening strategy) Suppose G is a tree with root O. For i = 1, . . . , t, choose some x i uniformly at random from the interval [2 i-1 , 2 i ] and let x 0 = 1 and x t+1 = 2 t . For i = 0, . . . , t, let V i be the set of vertices of G whose distance from O lies in the interval [x i , x i+1 ). We call V 0 , . . . , V t the levels of the search, so that V i is level i of the search. Let G 0 be the induced subtree of G with vertex set V 0 ∪ O and we define G i , i > 0 recursively as the induced subtree with vertex set V i ∪ O of the graph obtained by contracting G 0 ∪ . . . ∪ G i-1 to the root O. The randomized deepening strategy performs a RDFS of each of the trees G i in the order G 0 , . . . , G t .

We need two straight-forward results before stating and proving the main theorem in this section, that the random deepening strategy has approximation ratio 5/4. Let A i be set of vertices of G whose distance from O is in the interval [2 i-1 , 2 i ), and let A i = ∪ j≤i A j . (For the purposes of writing the proof of Theorem 3 we allow i to take any integer value, but note that A i is only non-empty for i = 1, . . . , t.)

Lemma 3 The expected sum over all vertices v ∈ A i ∩ V i-1 of edge lengths λ v is 2λ(A i ) - ∆(A i )/2 i-1 . Proof: The probability that the distance d(v) from O of a vertex v in A i is less than x i is (2 i -d(v))/2 i-1 . So the expected sum over all vertices v ∈ A i ∩ V i-1 of lengths λ v is v∈A i 2 i -d(v) 2 i-1 λ(v) = 2λ(A i ) -∆(A i )/2 i-1 .
We also make two simple observations about the parameters ∆(A i ).

Lemma 4 For any i = 1, . . . , t we have

(i) ∆(A i ) ≤ 2 i λ(A i ) and (ii) λ(A i )-∆(A i )/2 i ρ ≤ 2 i-1 .
Proof: Item (i) follows from the fact that every vertex in A i is at distance no further than 2 i from O.

For item (ii), we use Lemma 1 to bound ρ, giving

λ(A i ) -∆(A i )/2 i ρ ≤ λ(A i ) -∆(A i )/2 i λ(A i ) 2 /(2∆(A i )) = 2 ∆(A i ) λ(A i ) -2 1-i ∆(A i ) λ(A i ) 2 .
The right-hand side of the expression above is a quadratic in ∆(A i )/λ(A i ), which is easily shown to be maximized at ∆(A i )/λ(A i ) = 2 i-1 , where it takes a value of 2 i-1 .

Theorem 3 Let G be a weighted tree or an unweighted graph. Let s be the randomized deepening strategy on G if G is a tree, or on some shortest path tree of G if G is an unweighted graph. Then the approximation ratio of s is asymptotically 5/4. In particular, ρ s ≤ (5/4)ρ + 1/2.

Proof: First suppose G is a tree. Let v be a vertex that maximizes the randomized search ratio of s and suppose v is at distance d from O. Let L be the expected sum over all vertices u in previous levels from v of the lengths λ u plus half the expected sum over all vertices u in the same level as v of the lengths λ u . By Lemma 2, the expected search time of v is at most L + d/2. Hence

ρ s ρ ≤ (L + d/2)/d ρ ≤ L/d ρ + 1/(2ρ).
We just have to show that L/(dρ) ≤ 5/4. Suppose v ∈ A k for some k and let L 1 , L 2 , L 3 be the contributions to L from vertices in A k-1 , A k , A k+1 , respectively, so that L = λ(A k-2 )+L 1 +L 2 +L 3 . We calculate L 1 , L 2 and L 3 separately.

For L 1 , observe that with probability (d -2 k-1 )/2 k-1 the vertex v is in level k, which does not intersect with any vertices in A k-1 . Otherwise, v is in level k -1 which contains some vertices of A k-1 and by Lemma 3,

L 1 = d -2 k-1 2 k-1 λ(A k-1 ) + 2 k -d 2 k-1 (λ(A k-1 )/2 + (2λ(A k-1 ) -∆(A k-1 )/2 k-2 ))/2 = 2 - d 2 k λ(A k-1 ) -2 - d 2 k-1 ∆(A k-1 ) 2 k-1 .
Similarly, for L 3 , if v is in level k -1 then all vertices of A k+1 are in levels after the level of v.

Otherwise v is in level k which contains some vertices of A k+1 . Again applying Lemma 3,

L 3 = d 2 k-1 -1 λ(A k+1 ) - ∆(A k+1 ) 2 k+1 .
Lastly, for L 2 , observe that a vertex u in

A k at distance d(u) ≤ d is in the level before v if d(u) ≤ x k < d, otherwise it is in the same level as v. So the contribution u makes to L 2 is d -d(u) 2 k-1 • λ u + 2 k-1 -(d -d(u)) 2 k-1 • λ u 2 = (d -d(u) + 2 k-1 )λ u 2 k . Similarly, if d(u) > d, then u is in the level after v if d ≤ x k < d(u), otherwise u is in the same level as v, so the contribution u makes to L 2 is d(u) -d 2 k-1 • 0 + 2 k-1 -(d(u) -d) 2 k-1 • λ 2 = (d -d(u) + 2 k-1 )λ u 2 k ,
which is the same. Hence L 2 is given by

L 2 = u∈A k (d -d(u) + 2 k-1 )λ u 2 k = d 2 k + 1 2 λ(A k ) - ∆(A k ) 2 k .
Using L = λ(A k-2 ) + L 1 + L 2 + L 3 , combining our expressions for L 1 , L 2 and L 3 and rearranging, we obtain

L = 1 - d 2 k ∆(A k-2 ) 2 k-2 -λ(A k-2 ) + 3 2 - d 2 k-1 λ(A k-1 ) - ∆(A k-1 ) 2 k-1 + 3 2 - d 2 k λ(A k ) - ∆(A k ) 2 k + d 2 k-1 -1 λ(A k+1 ) - ∆(A k+1 ) 2 k+1 .
The first term in the expression on the right-hand side above is non-positive, since d ≤ 2 k and ∆(A k-2 ) ≤ 2 k-2 λ(A k-2 ), by Lemma 4(i). So, dividing by d, we obtain

L d ≤ 3 2d - 1 2 k-1 λ(A k-1 ) - ∆(A k-1 ) 2 k-1 + 3 2d - 1 2 k λ(A k ) - ∆(A k ) 2 k + 1 2 k-1 - 1 d λ(A k+1 ) - ∆(A k+1 ) 2 k+1 . (1) If 2 k-1 ≤ d ≤ 3 • 2 k-2
then it follows from Lemma 4(i) that all three of the terms on the right-hand side of (1) are non-negative. Hence by Lemma 4(ii),

L dρ ≤ 3 2d - 1 2 k-1 2 k-2 + 3 2d - 1 2 k 2 k-1 + 1 2 k-1 - 1 d 2 k = 1 + 2 k-3 /d ≤ 5/4 (maximized when d = 2 k-1 ). If 2 k ≥ d > 3 • 2 k-2
then the first term on the right-hand side of ( 1) is negative but the other two terms are non-negative by Lemma 4(i), so by Lemma 4(ii),

L dρ ≤ 3 2d - 1 2 k 2 k-1 + 1 2 k-1 - 1 d 2 k = 3/2 -2 k-2 /d ≤ 5/4 (maximized when d = 2 k ).
This completes the proof in the case that G is a tree. If G is not a tree, then we remove edges from G until obtaining a shortest path tree. Note that removing these edges has no effect on λ(v) and d(v) for vertices v, so the lower bounds given by Lemma 1 remain unchanged. Hence we can apply the same argument as above, implementing the randomized deepening strategy on the shortest path tree of G, to obtain an approximation ratio asymptotically equal to 5/4.

We observe that the ratio 5/4 could be improved slightly by introducing some randomization into the definition of A 1 , . . . , A t : that is, we could define A i as the set of all edges whose length d satisfies 2 i-1-θ ≤ d < 2 i-θ , where θ is chosen according to some probability distribution on [0, 1]. This would improve the approximation ratio from 5/4, but only marginally.

We may compare this result with analogous results from [START_REF] Koutsoupias | Searching a fixed graph[END_REF] in the context of pathwise search: for unweighted graphs they obtain algorithms that approximate the deterministic and randomized search ratio within a factor of 6 and 8.98 respectively. For expanding search, we easily obtain the optimal strategy in the deterministic case, and we obtain a 5/4approximate strategy in the randomized case. Although our randomized strategy is somewhat more sophisticated, the difference must be in part due to the fact that expanding search is more straightforward to deal with than pathwise search.

Bounding the Randomized Search Ratio

In this section we ask how large the randomized search ratio can be for a graph with n vertices plus the root. First note that the equivalent question for the (deterministic) search ratio is easily settled. Indeed, for an arbitrary weighted graph with minimum edge length normalized to 1, consider the search strategy that visits the vertices in non-decreasing order of their distance from the root. The normalized search time of the jth vertex to be visited is at most j ≤ n, so σ ≤ n. This is tight for a uniform star, that is a star with edges of equal length.

In contrast, it is not as easy to bound the randomized search ratio of an arbitrary weighted graph. Note that the randomized search ratio of a uniform star is (n + 1)/2, since an optimal Searcher strategy is to search the edges in a uniformly random order and an optimal Hider strategy is to choose one of the n vertices uniformly at random. In this section we will show that the uniform star is, in fact, the weighted graph with the largest randomized search ratio.

The remainder of this section is structured as follows. We first prove the result for unweighted graphs using a simple, intuitive argument (see Proposition 3). To obtain the result for general, weighted graphs, one needs to resort to some heavier machinery. This can be accomplished in two different ways, and we include both for completeness. First, we argue how the main result of [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF] on the seemingly unrelated problem of pipelined filter ordering can yield the desired upper bound (see Proposition 4). However, the resulting optimal strategy cannot be described succinctly, since [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF] applies an involved, flow-based approach. We give an alternative proof of Proposition 4 that uses a much simpler and intuitive strategy (based from intuition obtained from the unweighted case), and a game-theoretic approach (this proof was obtained independently in the conference version of this paper [START_REF] Angelopoulos | The expanding search ratio of a graph[END_REF]). Last, based on Proposition 4, we show our main result of the section, namely that every graph has randomized search ratio that does not exceed that of a uniform star on the same number of vertices (see Theorem 5).

We begin by first proving the result for unweighted graphs, as it is relatively easy in this case.

Proposition 3 Let G be an unweighted graph with n vertices plus the root O. The randomized search ratio ρ of G satisfies ρ ≤ (n + 1)/2.

Proof: The proof is by induction (the case n = 1 is trivial). Assume it is true for graphs with n or fewer vertices plus the root, and suppose G has n+1 vertices. We must show that ρ(G) ≤ (n+2)/2. Let G be the subgraph of G formed by removing an arbitrary vertex v * of G at maximum distance from O and all the edges incident to v * , and let s be an optimal randomized search of G , so that T (s, v) ≤ (n + 1)/2 for any vertex v in G , by the induction hypothesis. Let s be the randomized search of G that follows a shortest path P to v * then follows s (omitting edges contained in P ). Let s be the search that, with probability p follows s and with probability 1 -p follows s then searches v * , where p = 1/(2d ) and

d = d(v ). Then for any vertex v of G , T (s , v) ≤ T (s, v) + pd d(v) ≤ n + 1 2 + d 2d = n + 2 2 . Also, T (s , v * ) = (1 -p)(n + 1) + pd d = n + 3 2 1 d - n + 1 2 1 d 2 .
It is easy to verify that the expression above is decreasing in d , and at d = 1 is equal to (n + 2)/2. Hence ρ ≤ ρ s (G) ≤ (n + 2)/2 and the proposition follows by induction.

To prove the analogous result for weighted graphs, we first need to prove it for stars. The general result then follows as a corollary. On stars, the problem of finding the randomized search ratio is related to a problem in pipelined filter ordering, which we discuss in more detail in the the following subsection.

Connection with pipelined filter ordering

In this section we discuss the connection between this work and a problem in pipelined filter ordering. As mentioned in the introduction, star search is connected to the work of [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF], who study an adversarial pipelined filter ordering problem. The model may be described as follows. An item, or tuple must be routed in some order through a set {O 1 , . . . , O n } of operators, each of which tests whether the tuple satisfies some predicate (or filter) of a conjunction. There is a known cost c i of each operator O i to process a tuple, and the tuple is routed through the operators until it fails one of the tests (and is eliminated) or it passes all of them. We may alternatively think of this as a product being subjected to several quality tests before being sent to the market.

In the problem of [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF], an adversary chooses the set of filters which will eliminate the tuple. The aim is to choose a randomized routing of the tuple to minimize the multiplicative regret: that is the expected ratio of the total cost of eliminating the tuple to the cost of eliminating the tuple if the adversary's choice were known a priori. The authors argue that we may as well assume the adversary chooses only one filter to eliminate the tuple, as he is not disadvantaged by this restriction. If the ordering chosen is (without loss of generality) O 1 , . . . , O n and the adversary chooses the filter corresponding to operator O j , then the multiplicative regret is (c

1 + • • • + c j )/c j .
It is easy to see that the problem is exactly equivalent to our problem of calculating the optimal randomized search for a star graph with edges of lengths c 1 , . . . , c n . [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF] find a polynomial time algorithm for their problem, and we summarize their result in the context of the randomized search ratio of a star graph.

Theorem 4 (From Section 4 of [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF]) Let G be a star graph with root O and vertices v 1 , . . . , v n at distances c 1 , . . . , c n from O, where the c i are non-decreasing. There is a polynomial-time search algorithm that calculates the optimal randomized search of G. The randomized search ratio ρ(G) is given by

ρ(G) = max 1≤k≤n 1≤i≤j≤k c i c j k i=1 c 2 i .
(2)

Note that the right-hand side of (2) is the maximum over all choices of A = {v 1 , . . . , v k } of the value of the first lower bound in Lemma 1. It follows that the optimal strategy of the Hider is to choose such a set A which maximizes this bound and hide at vertex v i ∈ A with probability proportional to c 2 i . The optimal strategy for the Searcher cannot be described so succinctly, and we refer to [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF] for details of their algorithm.

The relation here to pipelined order filtering means that our results of Section 4 apply to the following generalization of the model in [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF]. Suppose the order that the tuple may be routed through the operators is subject to some precedence constraints. This is, there is a partial order ≺ on the set of operators such if O i ≺ O j then the tuple must be processed by O i before it can be processed by O j . The partial order defines a directed acyclic graph, and if that graph is a tree, then the problem of finding the randomized routing of the tuple to minimize the expected regret is equivalent to our problem of finding the optimal randomized search on a tree. By Theorem 3, the randomized deepening strategy has approximation ratio 5/4 for this problem.

Bounding the randomized search ratio for weighted graphs

We now show how to apply the results of the previous subsection so as to bound the randomized search ratio for weighted stars; we also show that the bound holds for arbitrary weighted graphs.

Proposition 4 Let G be a weighted star with n vertices plus the root. The randomized search ratio ρ of G satisfies ρ ≤ (n + 1)/2. Proof: By Theorem 4, the randomized search ratio is equal to the right-hand side of (2). Suppose this expression is maximized by k = k * and, without loss of generality, assume that k * i=1 c i = 1. Then

ρ = 1≤i≤j≤k * c i c j k * i=1 c 2 i = 1 2 k * i=1 c i 2 + 1 2 k * i=1 c 2 i k * i=1 c 2 i = 1 2 k * i=1 c 2 i + 1 2 . ( 3
)
The right-hand side of ( 3) is maximized when all the c i 's are equal to 1/k * , so that ρ ≤ (k * + 1)/2 ≤ (n + 1)/2.

Using Proposition 4, our main theorem of this section follows.

Theorem 5 Let G be a weighted graph with n vertices plus the root O. The randomized search ratio ρ of G satisfies ρ ≤ (n + 1)/2.

Proof: Let G be the star with the same vertex set as G, such that for any non-root vertex v in G , the length of the edge with endpoints O and v in G is equal to the distance of the shortest path from O to v in G. This ensures that the distance from the root to v is the same in G and G . By Proposition 4, there is a randomized search s of G with randomized search ratio no more than (n + 1)/2. We can then construct a randomized search of G such that the expected search time of every vertex in G under s is no more than its expected search time in G under s , which is sufficient to prove the theorem.

In order to construct s we will replace every deterministic search S given positive weight in s with a deterministic search S of G such that the search time of every vertex in G under S is no more than its search time in G under S . Indeed, suppose such a search S visits the vertices of G in some order v 1 , . . . , v n , and we construct S recursively as follows. Start by setting S to be empty, then while S has not yet visited all the nodes of G, we choose the minimal i such that v i has not yet been visited and add to the end of S a shortest path to v i from the region of G that S has already visited. It is easy to see that S has the desired property.

Proposition 4 can be proved in another more direct way, without resorting to the result of [START_REF] Condon | Algorithms for distributional and adversarial pipelined filter ordering problems[END_REF]. Namely, we can explicitly construct a randomized search strategy on a star that has search ratio at most (n + 1)/2. We include a description of this method of proving the proposition because it is based on an intuitive strategy which may be useful in future work.

For a given star graph G we inductively define a randomized search strategy s k on the star graph G k consisting of only the edges e 1 , . . . , e k with total length µ k . Having defined the strategy s k , we will define s k+1 as a randomized mix of two strategies, s + k+1 and s - k+1 , which we define in Definition 5. The former strategy, s + k+1 searches the new edge e k+1 after searching the other edges, and works well in the case that the length of e k+1 is a lot larger than the previous edges. If e k+1 is not too large, then it is better to search it at some random point in the middle of s k , which corresponds to the latter strategy, s - k+1 . Definition 5 Suppose s k has been defined for some k = 1, . . . , n -1. Let s + k+1 and s - k+1 be randomized search strategies on G k+1 defined by: (i)

v i is T (s k , v i ) + (T (s k , v i )/µ k )d k+1 . Hence T (s - k+1 , v i ) = T (s k , v i ) + (T (s k , v i )/µ k )d k+1 d i = T (s k , v i )(1 + d k+1 /µ k ) ≤ ρ s k (1 + d k+1 /µ k ).
Now suppose i = k+1. Under s + k+1 , the time taken to find the Hider is µ k +d k+1 , so T (s + k+1 , v k+1 ) = µ k /d k+1 + 1. Under s - k+1 , the expected search time is µ k /2 + d k+1 minus a random correction error which depends upon which edge e is being searched under s k at the random time t chosen uniformly in [0, µ k ]. The edge e is e i with probability d i /µ k , and in this case the expected value of the correction error is d i /2. Hence the expected value of this correction error is

k i=1 (d i /µ k ) • (d i /2) = D k /(2µ k ). So we have T (s - k+1 , v k+1 ) = µ k /2 + d k+1 -D k /(2µ k ) d k+1 = µ k /(2d k+1 ) + 1 -D k /(2µ k d k+1 ).
To sum up, the expected search ratio for each combination of strategies can be bounded above by the payoffs in Table 2. We can now proceed to define s n . Definition 6 Let s 1 be the only strategy available on G 1 . Suppose s k has already been defined on G k for some k = 1, . . . , n -1. The strategy s k+1 is an optimal mixture of s + k+1 and s - k+1 in the zero-sum game with payoff matrix given by Table 2.

The search ratio of s n can be calculated recursively, since the search ratio ρ s k+1 of s k+1 is at most the value of the game with payoff matrix given by Table 2, for each k = 1, . . . , n -1. We use this to show that ρ sn ≤ (n + 1)/2. Theorem 6 The randomized search ratio ρ of star graph G with n edges is at most (n + 1)/2, with equality if and only if all the edges have the same length.

Search

Vertex, v strategy, s v i for some

i ≤ k v k+1 s + k+1 ρ s k µ k /d k+1 + 1 s - k+1 ρ s k (1 + d k+1 /µ k ) µ k /(2d k+1 ) + 1 -D k /(2µ k d k+1 )
Proof: We have already pointed out that ρ = (n + 1)/2 for the star whose edges all have the same length. To show that ρ ≤ (n + 1)/2 we use induction on the number of edges to show that ρ sn ≤ (n + 1)/2. It is clear that for k = 1, we have ρ s k = 1 = (k + 1)/2, so assume that ρ(s k ) ≤ (k + 1)/2 for some k > 1 and we will show that ρ k+1 ≤ (k + 2)/2 = k/2 + 1.

First observe that if d k+1 ≥ 2µ k /k then the Searcher can ensure a payoff of no more than k/2+1 in the game in Table 2 just by using strategy s + k+1 . This is because the payoff ρ s k against a vertex v i with i ≤ k is no more than (k + 1)/2 by the induction hypothesis and the payoff against v k+1 is µ k /d k+1 + 1 ≤ k/2.

So assume that d k+1 ≤ 2µ k /k, and note also that d k+1 ≥ µ k /k, since the lengths of the edges are non-decreasing and d k+1 must be at least the average length of edges e 1 , . . . , e k .

By the induction hypothesis, ρ s k ≤ (k + 1)/2, so the value of the game with payoff matrix given by Table 2 cannot decrease if we replace ρ s k with (k + 1)/2 in the table. The value also does not decrease if we replace -D k by the maximum value it can take, which is -µ 2 k /k (that is, its value when d 1 , . . . , d k are all equal). In summary, ρ s k+1 is no more than the value of the game given in Table 3. By assumption, against strategy s + k+1 , the best response of the Hider (that is, the highest payoff) is given by choosing vertex v k+1 . We show that against strategy s - k+1 , the Hider's best response is to choose a vertex v i with i ≤ k. This follows from writing the difference, δ between the payoffs in entries (2, 1) and (2, 2) of Table 3 as

δ = (k -1) µ k 2d k+1 k + 1 k -1 d k+1 µ k 2 + d k+1 µ k -1/k .
The quadratic in (d k+1 /µ k ) inside the parentheses is increasing for positive values of d k+1 /µ k , and when d k+1 /µ k = 1/k the quadratic is positive. Since d k+1 /µ k ≥ 1/k, we must have δ ≥ 0. Hence the Hider does not have a dominating strategy in the game in Table 3. It is also clear that the Searcher does not have a dominating strategy, since it is better to search e k+1 last if and only if the Hider is at some v i with i ≤ k. Therefore the game in Table 3 has a unique equilibrium in proper mixed strategies (that is, the players both play each of their strategies with positive probability). The search ratio ρ s k+1 of s k+1 is bounded above by the value V of the game, which is easily verified to be

V = k/2 + 1 - k 2 (d k+1 /µ k -1/k) 2 (d k+1 /µ k ) 2 + 1/k .
This is clearly at most k/2 + 1, with equality if and only if µ k /d k+1 = k. The theorem follows by induction, and equality is only possible if d 1 = d 2 = . . . = d n .

Conclusion

We have undertaken an analysis of expanding search, as defined by [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF], focusing on the search ratio, as introduced by [START_REF] Koutsoupias | Searching a fixed graph[END_REF] in the context of pathwise search in bounded domains. In contrast to [START_REF] Alpern | Mining coal or finding terrorists: The expanding search paradigm[END_REF], we have focused on computational and algorithmic issues of expanding search, an angle that is often neglected in the analysis of search games. For general graphs, we showed that computing the search ratio is NP-hard, and we gave a 4 ln(4) approximation. Our main technical contribution is defining and analyzing explicit randomized search strategies that yield significant improvements to the approximation of the randomized search ratio of trees and unweighted graphs (namely, an approximation equal to 5/4). We believe that some of the techniques we introduced in this work can be applicable in the context of pathwise search. For instance, we believe that a variants of the randomized strategy presented in Section 4 will result in improved randomized search ratios for pathwise search in weighted trees.

We leave some open questions which we would like to see addressed by future work. Although we have showed that computing the search ratio of a graph is NP-hard, we do not have an equivalent result for computing the randomized search ratio (though we suspect such a result holds). It would be very interesting to improve upon the approximations of the search ratio and randomized search ratio for general weighted graphs; the latter, in particular, appears to be quite a difficult problem that we believe will require the introduction of new techniques and approaches. Another direction for future work is related to the continuous model. In this model, the Hider may be located not only on a graph vertex, but on any given point across an edge. Optimal strategies that minimize the deterministic search ratio are relatively easy to obtain (see [START_REF] Angelopoulos | The expanding search ratio of a graph[END_REF]; in contrast, it is quite challenging to obtain strategies that improve upon the straightforward approximations of the randomized search ratio in this model.

Last, we note that the work that introduced the expanding search paradigm (Alpern and Lidbetter ( 2013)) raises several interesting optimization problems concerning the average search time of vertices of a graph (assuming expanding search). In particular, one can define the expanding minimum latency problem, as the problem of minimizing the total latency of a graph, assuming an expanding search of the graph. Is this problem NP-hard in general graphs? If yes, can one obtain constant-factor approximations? Is the general problem in the setting in which the search time of a vertex is weighted as hard as the unweighted variant? Answers to the above questions will help provide an almost-complete picture of the computability and approximability of expanding search across a variety of performance measures.

Figure 1 :

 1 Figure 1: The graph G.

Figure 2 :

 2 Figure 2: A schematic view of the graph G used in the reduction of Theorem 1.

Proof:

  For any d ≥ 1, let V d be the set of vertices of G at distance no more than d from the root O. Let G d be the subtree of minimal length in G that contains all the vertices in V d . It is easy to see that σ is at least λ(G d )/d, since the time taken by any search to reach the last vertex v visited in V d is at least λ(G d ), and d(v) ≤ d.

Table 1 :

 1 Previous work and relations between search paradigms and objectives.

	Objective

[START_REF] Blum | The minimum latency problem[END_REF]

  s + k+1 : follow the strategy s k on G k and then search edge e k+1 . (ii) s - k+1 : choose a time t uniformly at random in [0, µ k ] and denote the edge that is being searched at time t by e. Follow the strategy s k , but search edge e k+1 immediately before searching e. Before giving the precise definition of s k , we estimate the normalized expected search times T (s + k+1 , v i ) and T (s - k+1 , v i ) in terms of ρ s k for the vertices v i with i = 1, . . . , k + 1. First suppose i ≤ k. Then clearly T (s + k+1 , v i ) ≤ ρ s k (with equality for some i ≤ k) by definition of ρ s k . Under s - k+1 , with probability T (s k , v i )/µ k edge e k+1 is searched before e i , so the expected search time of

Table 2 :

 2 Maximum value of T (s, v).

Table 3 :

 3 Upper bounds for T (s, v).)(1 + d k+1 /µ k )/2 µ k /(2d k+1 ) + 1 -µ k /(2kd k+1 )

	Search		Vertex, v
	strategy, s	v i for some i ≤ k	v k+1
	s + k+1 s -k+1	(k + 1	(k + 1)/2	µ k /d k+1 + 1

Acknowledgements

The authors would like to thank Lisa Hellerstein for pointing out the connection between this work and the work in Condon et al. (2009) on pipelined filter ordering.

Research supported in part by project ANR-11-BS02-0015 "New Techniques in Online Computation-NeTOC", and by the FMJH program Gaspard Monge in optimization and operations research and by EDF.


PhD Gaëlle Dzangué-Tchoupou

PhD Kuberaka Mariampillai

Loïs Bolko

MSc Damien Amelin

MD MSc Wladimir Mauhin

Aurélien Corneau

PhD Catherine Blanc

MD Yves Allenbach

Olivier Benveniste

Aurélien Corneau Msc

MD ¶ Olivier Benveniste

Gaëlle Dzangué
email: gaelle.dzangue@gmail.com

CD8+T-bet+ cells as a predominant biomarker for inclusion body myositis

Keywords: inclusion body myositis, deep immune profiling, physiopathology, CD8+ T-bet+ cells, biomarkers, myositis CART: classification and regression trees CI: confidence interval CTL: cytotoxic T lymphocytes CyTOF: cytometry by time of flight (mass cytometry) HD: healthy donors HLADR: human leukocyte antigen-DR HMGCR: 3-Hydroxyl-3-MethylGlutaryl CoA Reductase IdU: iododeoxyuridine IFN-γ: interferon-gamma IMNM: immune mediated necrotizing myopathies MMI: median mass intensity PBMC: peripheral blood mononuclear cells ROC: receiver operating characteristics sIBM: sporadic Inclusion body myositis terminally differentiated memory cells viSNE: stochastic neighbor embedding

Introduction

Myositis comprises a heterogeneous group of diseases with variable clinical, pathological and serological features, involving both muscular and extra-muscular tissues [START_REF] Gao | Using multi-omics methods to understand dermatomyositis/polymyositis[END_REF][START_REF] Suzuki | Integrated Diagnosis Project for Inflammatory Myopathies: An association between autoantibodies and muscle pathology[END_REF]. At present, sporadic inclusion body myositis (sIBM) is the only group bereft of treatment options since there is no evidence of efficacy for corticosteroids and/or immunosuppressive therapies in the long term [START_REF] Dalakas | Sporadic inclusion body myositis--diagnosis, pathogenesis and therapeutic strategies[END_REF][START_REF] Needham | Sporadic inclusion body myositis: A review of recent clinical advances and current approaches to diagnosis and treatment[END_REF][START_REF] Keller | Immune and myodegenerative pathomechanisms in inclusion body myositis[END_REF][START_REF] Cavagna | How I treat idiopathic patients with inflammatory myopathies in the clinical practice[END_REF]. sIBM is the most common myositis subtype after age 50. Disease onset is slow and progressive, gradually leading to muscle atrophy and a reduced quality of life. Diagnosis at sIBM onset could be misleading, potentially involving administration of a treatment that causes detrimental effects [START_REF] Benveniste | Long-term observational study of sporadic inclusion body myositis[END_REF]. CD8+ T cells have been implicated in the physiopathology of sIBM because of their aggressive and infiltrative presence within muscle fibres overexpressing major histocompatibility type 1 molecules [START_REF] Benveniste | Amyloid deposits and inflammatory infiltrates in sporadic inclusion body myositis: the inflammatory egg comes before the degenerative chicken[END_REF][START_REF] Müntzing | Inclusion body myositis: clonal expansions of muscle-infiltrating T cells persist over time[END_REF][START_REF] Salajegheh | T cell receptor profiling in muscle and blood lymphocytes in sporadic inclusion body myositis[END_REF][START_REF] Day | Dysregulated innate immune function in the aetiopathogenesis of idiopathic inflammatory myopathies[END_REF][START_REF] Afzali | Skeletal muscle cells actively shape (auto)immune responses[END_REF]. Various studies have observed a diverse repertoire of CD8+ T cells in the peripheral blood of sIBM patients, suggesting the presence of antigen-driven CD8+ T cell responses [START_REF] Allenbach | Th1 response and systemic treg deficiency in inclusion body myositis[END_REF][START_REF] Greenberg | Association of inclusion body myositis with T cell large granular lymphocytic leukaemia[END_REF][START_REF] Pandya | Expanded T cell receptor Vβ-restricted T cells from patients with sporadic inclusion body myositis are proinflammatory and cytotoxic CD28null T cells[END_REF].

Two major T-box transcription factors drive differentiation of naïve CD8+ T cells into cytolytic T lymphocytes (CTL): T-bet (T-box expressed in T cells) and eomesodermin

(eomes) [START_REF] Mclane | Differential localization of T-bet and Eomes in CD8 T cell memory populations[END_REF][START_REF] Knox | Characterization of T-Bet and Eomes in Peripheral Human Immune Cells[END_REF]. High levels of T-bet expression in CD8+ T cells are required for antigenspecific CD8+ response, cytotoxic function and maintenance of memory subsets [START_REF] Wherry | Molecular and cellular insights into T cell exhaustion[END_REF][START_REF] Paley | Progenitor and terminal subsets of CD8+ T cells cooperate to contain chronic viral infection[END_REF][START_REF] Blackburn | Selective expansion of a subset of exhausted CD8 T cells by alphaPD-L1 blockade[END_REF][START_REF] Kao | Transcription factor T-bet represses expression of the inhibitory receptor PD-1 and sustains virus-specific CD8+ T cell responses during chronic infection[END_REF].

Repeated and prolonged stimulation of T cells leads to progressive loss of costimulatory markers, such as CD28 and CD27. Downregulation of the interleukin-7 alpha receptor (CD127) is also observed following chronic antigen stimulation [START_REF] Xu | CD127 Expression in Naive and Memory T Cells in HIV Patients Who Have Undergone Long-Term HAART[END_REF][START_REF] Kared | CD127 expression, exhaustion status and antigen specific proliferation predict sustained virologic response to IFN in HCV/HIV co-infected individuals[END_REF]. In addition to this immune profile, expression of CD57 defines a state of replicative senescence [START_REF] Brenchley | Expression of CD57 defines replicative senescence and antigen-induced apoptotic death of CD8+ T cells[END_REF][START_REF] Appay | Memory CD8+ T cells vary in differentiation phenotype in different persistent virus infections[END_REF][START_REF] Olson | Effector-like CD8 + T cells in the memory population mediate potent protective immunity[END_REF][START_REF] Hendriks | CD27 promotes survival of activated T cells and complements CD28 in generation and establishment of the effector T cell pool[END_REF].

B cell implication in the pathogenicity of sIBM has been suggested by the identification of anti-cytosolic 5'-nucleotidase 1A antibodies present in ~ 30% of patients [START_REF] Pluk | Autoantibodies to cytosolic 5'-nucleotidase 1A in inclusion body myositis[END_REF][START_REF] Larman | Cytosolic 5'nucleotidase 1A autoimmunity in sporadic inclusion body myositis[END_REF][START_REF] Benveniste | Advances in serological diagnostics of inflammatory myopathies[END_REF]. Plasma cells are also observed in muscle inflammatory infiltrates of sIBM [START_REF] Greenberg | Plasma cells in muscle in inclusion body myositis and polymyositis[END_REF].

Finally, muscle biopsies from sIBM patients also reveal the presence of macrophages infiltrating non-necrotic muscle fibres [START_REF] Rygiel | Mitochondrial and inflammatory changes in sporadic inclusion body myositis[END_REF], suggesting the involvement of innate immune defence mechanisms that are still poorly investigated.

Cytometry by time of flight (CyTOF), also known as mass cytometry, is an innovative cell profiling tool based on antigen detection using metal-conjugated antibodies. CyTOF allows simultaneous screening of more than 38 markers at the single cell level [START_REF] Bendall | Single-cell mass cytometry of differential immune and drug responses across a human hematopoietic continuum[END_REF][START_REF] Behbehani | Mass Cytometric Functional Profiling of Acute Myeloid Leukemia Defines Cell-Cycle and Immunophenotypic Properties That Correlate with Known Responses to Therapy[END_REF].

CyTOF is of particular interest in applications of deep immune profiling and biomarker discovery. When using CyTOF, intra-assay variations can be reduced by barcoding cells prior to staining for markers [START_REF] Zunder | Palladium-based mass tag cell barcoding with a doublet-filtering scheme and single-cell deconvolution algorithm[END_REF][START_REF] Dzangué-Tchoupou | Analysis of cell surface and intranuclear markers on non-stimulated human PBMC using mass cytometry[END_REF][START_REF] Behbehani | Transient partial permeabilization with saponin enables cellular barcoding prior to surface marker staining[END_REF].

Considering the detrimental effects of immunosuppressants prescribed due to misdiagnosis, there is a need to identify novel diagnostic biomarkers for sIBM and to better understand the pathogenic mechanisms involved in this disease. The aim of this study was to better characterize the phenotype of peripheral blood mononuclear cells (PBMCs) from sIBM patients, to identify cells potentially involved in the pathophysiology of the disease and to identify a biomarker that can aid in the rapid diagnosis of sIBM from other types of myositis.

Material and methods

Patients and samples:

Approval for this study was obtained from the Comité Consultatif sur le Traitement de l'Information en matière de la Recherche dans le domaine de la Santé (CCTIRS), France.

Written informed consent was signed by all patients and age-matched healthy donors (HD) according to the declaration of Helsinki. Untreated sIBM patients (cohort 1, n=10 and cohort 2, n=8) were defined based on the Lloyd diagnosis criteria [START_REF] Lloyd | Evaluation and construction of diagnostic criteria for inclusion body myositis[END_REF]. Control groups of active myositis patients included untreated myositis patients suffering from anti-synthetase syndrome with anti-Jo1 positive antibodies (anti-Jo1, n=10), anti-3-hydroxyl-3-methylglutaryl CoA reductase positive immune mediated necrotizing myopathy (anti-HMGCR IMNM, n=9) and anti-signal recognition particle positive IMNM (anti-SRP IMNM, n=7) defined based on published ENMC criteria [START_REF] Hoogendijk | 119th ENMC international workshop: trial design in adult idiopathic inflammatory myopathies, with the exception of inclusion body myositis, 10-12 October 2003[END_REF][START_REF] Allenbach | Immune-Mediated Necrotizing Myopathies Working Group. 224th ENMC International Workshop:: Clinico-sero-pathological classification of immune-mediated necrotizing myopathies Zandvoort, The Netherlands, 14-16 October 2016[END_REF]. Main characteristics of patients are described in Supplementary Table 1. Detection of myositis-specific antibodies was performed by immunoassays as previously described [START_REF] Arouche-Delaperche | Pathogenic role of anti-signal recognition protein and anti-3-Hydroxy-3-methylglutaryl-CoA reductase antibodies in necrotizing myopathies: Myofiber atrophy and impairment of muscle regeneration in necrotizing autoimmune myopathies[END_REF]. Healthy control blood samples were obtained from the Etablissement Français du sang (EFS, Pitié-Salpêtrière-France) donated by healthy adults age-matched with sIBM patients (cohort 1, n=8 and cohort 2, n=8).

Upon reception of blood samples, peripheral blood mononuclear cells (PBMCs) were isolated and stored at -80°C in foetal bovine serum (Life Technologies, Saint-Aubin, France, Catalogue # 10270106) supplemented with 10% dimethyl sulfoxide. Twenty-four hours later, the cells were transferred to liquid nitrogen until use.

Mass cytometry experiments:

Thirty-six metal-conjugated antibodies, viability staining, and Iododeoxyuridine (IdU) were obtained from Fluidigm (Les Ulis, France) (Supplementary Table 2). Immunostaining and data acquisition were performed as previously described in a technical research article [START_REF] Dzangué-Tchoupou | Analysis of cell surface and intranuclear markers on non-stimulated human PBMC using mass cytometry[END_REF]. Briefly, PBMCs were incubated with IdU and then stained with cisplatin. Next, cells were incubated with CCR7 and CXCR5, followed by incubation with a mix containing all other cell surface markers. Next, samples were barcoded using BD CyTOFix/Cytoperm and BD wash/perm buffer (BD, France, Catalogue # 554715). All cells from different samples were washed and pooled together in a single tube. Fixation of pooled cells was performed using BD CyTOFix/Cytoperm buffer followed by incubation with antibodies targeting intranuclear markers in BD wash/perm buffer. Finally, DNA within cells was labelled using Cell ID Intercalator-Ir (Fluidigm, les Ulis, France, Catalogue # 201192A). Cellular events were acquired the following day on the Helios available at the "Plateforme de Cytométrie de la Pitié-Salpêtrière".

Data files were obtained in the FCS file format and analysed using different algorithms available on the Cytobank cloud based platform, R software version 3.4.0 and GraphPad Prism version 6.

Data analysis:

Beads were gated out using the following: 140/142Ce, 151/153Eu, 165Ho and 175/176 Lu. Cisplatin-positive dead cells were gated out, and automated identification of stratifying signatures in cellular populations was performed using the Citrus algorithm to identify differences between sIBM patients and healthy donors. We performed Citrus analyses using the median mass intensities (MMI) of various markers. The settings used for Citrus were as follows: population (all CD45+ cells), groups (Healthy donors and sIBM patients), clustering channels (CD19, CD56, CD11b, CD14, CD3, CD4, CD8, CD25, CD45RA, CCR7), statistics channels (HLA-DR, IgD, CD28, CD127, CD27, T-bet, FoxP3, CD38, CD57), equal event sampling (20000 each), minimum cluster size (5%), cross validation fold ( 5) and false discovery rate (1%).

Next, using the cytobank cloud based platform, automated cell clustering using spanning-tree progression analysis of density-normalized events (SPADE) was performed on CD45+ events. This is to allow a non-biased and uniform gating strategy of the main cell populations in our study. The SPADE tree was generated based on main phenotypic markers such as: CD3, CD4, CD8, CD14, CD11b, CD56, CD16 and CD19, with 20 nodes and a down-sampling of 10 percent. Nodes corresponding to homogenous cell populations were each exported to a new experiment.

Next, we used stochastic neighbour embedding (viSNE) to explore detail populations of interest with an unbiased approach. The settings used for the viSNE run on CD8+ T cells are as follows: equal event sampling (3615 each), channels (CD28, CD127, CD27, T-bet and CD57), iterations (1000), perplexity (50) and theta (0.3). Furthermore, we analysed the frequency of various cell populations and the MMI of various markers on the subsets obtained from the viSNE run.

Histograms and dot plots were used to confirm all results obtained from unsupervised analyses.

For identification of biomarkers specific to sIBM patients (cohort 1 and 2, n=18) compared to control myositis patients (anti-Jo1, anti-SRP and anti-HMGCR, n=26), we constructed a decisional tree using classification and regression trees (CART) with R software. As a result, new subjects from different subgroups can be predicted using a ranking algorithm. We included in the CART "potential predictors" based on our previous Using GraphPad Prism, we performed receiver operating characteristic (ROC) curves to better describe the biomarkers identified. Altogether, we chose a prediction value associated with the best cross-validation prediction rate on the test set using CART and with the best sensitivity, specificity, confidence interval (CI), and area under the curve (AUC) and a p-value < 0.0001 with ROC curves.

We used Shapiro-Wilk normality test to verify the distribution of quantitative data among the groups compared. For comparison of two groups, we used either the Mann-Whitney test or the t-test. When comparing MMI of expression for a marker within a population, we used the t-test. For multiple comparisons, we used the Kruskal-Wallis test using the Geisser-Greenhouse correction. We describe in-text data values using mean ± SD.

Results

Increased frequency of CD8+ T cells in sIBM patients expressing high levels of T-bet and presenting a senescent immune profile (CD8T-bet+ CD57+):

Mean age of sIBM patients was 63.8±2 and 61±1 for healthy donors (p=0.152). To identify biomarkers specific to sIBM, we performed automated identification of stratifying signatures in CD45+ cellular populations using the Citrus algorithm. This analysis aimed to identify markers that vary significantly between sIBM patients (cohort 1, n=10) and healthy donors (cohort 1, n=8). Citrus did not identify any significant differences in activation or differentiation markers within B cells, CD16±CD56 bright NK cells, CD16+CD56 dim NK cells, monocytes, CD4+ T cells or CD38+ cells (Fig. 1). These observations were confirmed by classical gating of individual populations. Interestingly, significant differences were observed only within CD8+ T cell populations regarding the expression of CD27, CD57, CD127, CD28, T-bet and CD38. We next decided to characterize in detail CD8+ T cells in sIBM patients.

CD3+ CD8+ events corresponding to CD8+ T cells from the SPADE run on all CD45+ events were exported for further analysis (Supplementary Fig. 1). First, we observed a significant increase in the frequency of CD8+ T-bet+ T cells (CD8T-bet+) in sIBM patients compared to healthy donors [sIBM=75.5%±13.2, HD=57.4%±15.2, p=0.02]. Further analysis revealed a remarkable increase in the frequency of CD8+ terminally differentiated memory T cells (TEMRA): CD8+ CD45RA+ CCR7-in patients [sIBM=51.9%±13.6, HD=19.1%±9.9, p<0.0001] (Fig. 2). Interestingly CD8T-bet+ cells contain mainly both effector memory (EM) and TEMRA cells [% EM: sIBM=27%±16.4, HD=56%±12.1, p=0.0008 and % TEMRA: sIBM=66.1%±16.8, HD=30.4%±13.3, p=0.0002] (Supplementary Fig. 2). Next, we compared the expression of the senescence marker CD57 within CD8T-bet+ cells and CD8+ Tbet-events (CD8T-bet-cells). We observed a marked increase in the expression of CD57 within CD8T-bet+ cells in sIBM patients, while healthy donors had very low expression of CD57 in both CD8T-bet+ cells and CD8T-bet-cells [MMI of CD57 in CD8T-bet+ cells: sIBM=188, HD=6, p=0.01 and MMI of CD57 in CD8T-bet-cells: sIBM=0.4, HD=0.08, p=0.09] (Supplementary Fig. 3).

Selective loss of CD28, CD27 and CD127 in non-senescent CD8+ T cells

(CD8T-bet+ CD57-) in sIBM patients compared to healthy donors:

Results

Next, we focused on three main subsets of CD8+ T cells of interest: senescent CD8T-bet+ CD57+ cells, non-senescent CD8T-bet+ CD57-cells and Naive CD8T-bet-cells. We compared expression of the co-stimulatory markers CD28 and CD27 and the functional marker CD127 within these three subsets. As expected, senescent CD8T-bet+ CD57+ cells are CD28null CD27null CD127null in both patients and healthy donors (Supplementary Fig. 4).

Unexpectedly, we observed a decrease in expression of CD28, CD27 and CD127 in nonsenescent CD8T-bet+ CD57-cells of sIBM patients compared to healthy donors. Loss of CD28, CD27 and CD127 was not observed in CD8T-bet-cells of either patients or healthy donors (Fig. 3).

Non-senescent CD8T-bet+ CD57-cells in sIBM patients are activated, but do not spontaneously secrete greater amounts of IFN-γ:

Observation of this particular memory immune profile in non-senescent CD8T-bet+ CD57- cells in sIBM patients prompted us to explore their activation states in comparison to other subsets we had examined. We compared the frequency of our populations of interest expressing activation markers CD38 and HLA-DR (Human Leucocyte Antigen-DR).

Spontaneous interferon-gamma (IFN-γ) was also quantified. Interestingly, we observed higher frequencies of non-senescent CD8T-bet+ CD57-cells expressing CD38 and HLADR in sIBM patients compared to healthy donors [HLADR+ cells: sIBM=9.9%±6.2, HD=4.6%±2.2, p=0.04 and CD38+ cells: sIBM=24.5%±17.3, HD=9%±5, p=0.02]. An increase in the frequency of senescent CD8T-bet+ CD57+ cells expressing CD38 was also observed in patients [CD38+ cells: sIBM=34.4%±9, HD=4%±1.1, p=0.0005]. We did not observe changes in spontaneous IFN-γ secretion between sIBM patients and healthy donors (Fig. 4). Low percentages of CD8T-bet-cells expressing CD8 and HLADR were similarly observed in both patients and healthy donors (Supplementary Fig. 5)

Confirmation of observed characteristics in a second independent cohort of sIBM patients:

In an attempt to validate the immune profiles we observed in the first cohort of sIBM patients (n=10), we stained PBMCs from a second independent cohort with a minimal set of markers using an independent experiment (cohort 2: sIBM=8 and healthy donors=8). We confirmed increased frequencies of TEMRA CD8+ T cells, CD8T-bet+ cells and activated nonsenescent CD8T-bet+ CD57-cells in sIBM patients from cohort 2 in comparison to healthy

Results

donors. A non-significant tendency towards higher frequencies of CD38+ senescent CD8T-bet+ CD57+ cells was observed. We also confirmed lower expression of CD27, CD127 and CD28 by non-senescent CD8T-bet+ CD57-cells in sIBM patients (Fig. 5). Values between sIBM patients of cohort 1 and 2 were not significantly different with respect to immune profile (Supplementary Fig. 6).

Taken together, these observations describe a novel increase in the frequency of senescent CD8T-bet+ CD57+ cells in sIBM patients compared to healthy donors. Further, sIBM patients exhibit an activated non-senescent CD8+T-bet+ CD57-cell population characterized by lower expression of CD28, CD27 and CD127, and higher expression of CD38 and HLADR compared to healthy donors.

Identification of biomarkers specific to sIBM patients:

. Next, we aimed to identify a minimal set of biomarkers that can be used as diagnostic criteria for sIBM patients (cohort 1 and 2, n=18). Other myositis patients presenting either anti-Jo1 auto-antibodies, anti-SRP auto-antibodies or anti-HMGCR auto-antibodies were used as controls. After multiple CART runs using different predictors, such as the frequency of CD8T-bet+, senescent CD8T-bet+ CD57+ and CD8T-bet+ CD27+ cells, the best predictor of classification was always the frequency of CD8T-bet+ cells. Given that the cut-off prediction frequency of CD8T-bet+ cells could vary between different CART runs, we used ROC curves to help choose the best predictive value. Altogether, using CART and ROC curves, we identified and validated a frequency of CD8T-bet+ cells > 51.51% as the best predictor to distinguish sIBM patients from other myositis patients (n=26), with a sensitivity of 94.4%, a specificity of 88.5%, a confidence interval of [69.9-97.6%], an area under curve of 0.97 and a p-value < 0.0001 (Fig. 6).

Using CyTOF, we simultaneously analysed thirty-six markers on non-stimulated PBMCs from sIBM patients and healthy donors. Unsupervised analysis revealed significant changes only within CD8+ T cells. CD8+ T cells from sIBM patients overexpress T-bet. Loss of CD28, CD27 and CD127 in senescent CD8T-bet+ CD57+ cells in both sIBM patients and healthy donors was expected. Unexpectedly, we observed specific loss of CD28, CD27 and CD127 in non-senescent CD8T-bet+ CD57-cells from sIBM patients but not from healthy subjects.

Previous studies have demonstrated that during chronic antigen stimulation, overexpression of T-bet on CD8+ T cells represses expression of inhibitory receptors,

defining a subset of exhausted CD8+ T cells with proliferative capacity and effector functions [START_REF] Kao | Transcription factor T-bet represses expression of the inhibitory receptor PD-1 and sustains virus-specific CD8+ T cell responses during chronic infection[END_REF]]. In this study we identified a subset of activated non-senescent CD8+ T-be+ cells defined by low levels of expression of CD57 and higher levels of expression of CD38 and HLA-DR in sIBM patients compared to healthy donors. This activated and non-senescent immune profile suggests continuous proliferative capacity and effector functions of these cells in sIBM patients, which could explain the progressive and destructive nature of sIBM. This suggestion is supported by the presence of not only TEMRA, but also EM cells within T-bet+ cells of sIBM patients.

Our results are in line with previous studies that observed increased frequencies of CD8+ CD28null T cells in PBMCs from sIBM patients compared to healthy individuals (15).

More recently, CD8+ CD57+ large granular lymphocytes were observed in blood and muscle of sIBM patients [START_REF] Greenberg | Association of inclusion body myositis with T cell large granular lymphocytic leukaemia[END_REF]]. Here, we present a more detailed and precise phenotype of peripheral blood CD8+ T cells in sIBM patients, thus enhancing understanding of this disease.

In this study, we did not observe an increase in spontaneous IFN-γ secretion by CD8T-bet+ cells from sIBM patients. This could be because cells were not stimulated, since our aim was to gain insight into the immune profile of PBMCs from sIBM patients without stimulation. We previously showed an increase in IFN-γ secretion by PBMC in sIBM patients after stimulation [START_REF] Allenbach | Th1 response and systemic treg deficiency in inclusion body myositis[END_REF]].

In this study, we were also able to identify a novel diagnostic biomarker for IBM.

Various diagnostic criteria for sIBM have been described, with sensitivities ranging from 11% to 90% and specificities above 96% [START_REF] Lloyd | Evaluation and construction of diagnostic criteria for inclusion body myositis[END_REF]]. Compared to other myositis subtypes (anti-Jo1 positive antibodies, IMNM with anti-HMGCR positive and anti-SRP positive antibodies), we

Discussion

obtained the highest sensitivity described thus far (sensitivity of 94.4%), and 88.5% specificity. All previous diagnostic criteria combined clinical and pathological analyses, both of which require specific expertise. The biomarker we present herein is based on two biological markers (CD8 and T-bet), and could be complementary to the actual diagnostic approaches used for sIBM patients. This biomarker could aid in categorizing patients for clinical trials and research, especially when diagnosis remains uncertain. Further prospective analyses are needed to compare this novel biological biomarker to pathological criteria in patients with IBM suspicion.

Funding source

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Competing interests

All the authors have no conflicts of interest to disclose.

  observations: frequencies of CD8+ T-bet+ T cells, CD8+ T-bet+ CD57+ T cells, CD8+ T-bet+ CD27+ T cells, CD8+ T-bet+ CD57+ CD27+ T cells and CD8+ T-bet+ CD57-CD27+ T cells. The validity of our classification tree model and the predictors (biomarkers) were validated by cross validation on a test set.

Fig 1 :

 1 Fig 1: Automated identification of stratifying signatures in cellular populations between patients and healthy donors (use of median mass intensities)

Fig 2 :

 2 Fig 2: Increase frequency of CD8+ T cells in sIBM patients expressing high levels of Tbet and presenting a senescent immune profile (T-bet+ CD57+)

Fig 3 :

 3 Fig 3: Selective loss of CD28, CD27 and CD127 in non-senescent CD8+ T cells (CD8T-bet+ CD57-) in sIBM patients compared to healthy donors

Fig 4 :

 4 Fig 4: Non-senescent CD8+ cells in sIBM patients show an activated immune profile; nevertheless they do not spontaneously secrete greater amounts of IFN-γ

Fig 5 :

 5 Fig 5: Confirmation of the immune profile identified using an independent cohort of sIBM patients and healthy donors

Fig 6 :

 6 Fig 6: Identification of biomarkers specific to sIBM patients in comparison to control myositis patients

Supplementary material Supplementary Table 1: Clinical characteristics of active sIBM and myositis control patients

Supplementary Table 2: List of antibodies

Supplementary