Keywords: cops and robbers, dynamic graphs, offline, online, sparse

We examine the classic game of Cops and Robbers played on dynamic graphs, that is, graphs evolving over discrete time steps. At each time step, a graph instance is generated as a subgraph of the (static) underlying graph. The cops and the robber take their turns on the current graph instance. The cops win if they can capture the robber at some point in time. Otherwise, the robber wins.

In the offline case, the players are fully aware of the evolution sequence, up to some finite time horizon T . We provide a O(n 2k+1 T ) algorithm to decide whether a given evolution sequence for an underlying graph with n vertices is k-cop-win via a reduction to a reachability game.

In the online case, there is no knowledge of the evolution sequence, and the game might go on forever. Also, each generated instance is required to be connected. We provide a nearly tight characterization for sparse underlying graphs with at most a linear number of edges. We prove λ + 1 cops suffice to capture the robber in any underlying graph with n -1 + λ edges. Furthermore, we define a family of underlying graphs with n -1 + λ edges where λ -1 cops are necessary (and sufficient) for capture.

Introduction

Cops and robbers is a classic pursuit-evasion combinatorial game played on a graph. There are two opposing players aiming at winning the game: a cop player controlling k cop tokens and a robber player controlling one robber token. Initially, the k cops are placed at vertices of the graph. Subsequently, the robber is also placed at a graph vertex. The two players proceed (possibly ad infinitum) by taking turns alternately commencing with the cops. During a cops' turn, each cop may move to a vertex adjacent to its current one; note that cops are presumed to move simultaneously. Similarly, during a robber's turn, the robber may move to a vertex adjacent to its current placement. The cops win, if at least one of them manages to eventually lie at the same vertex as the robber, i.e., captures the robber. Otherwise, the robber wins if it can indefinitely avoid capture.

Cops and robbers applications are found in many fields, for example in motion planning [START_REF] Sugihara | On a pursuit-evasion problem related to motion coordination of mobile robots[END_REF], routing [START_REF] Kosowski | k-chordal graphs: From cops and robber to compact routing via treewidth[END_REF], network security [START_REF] Bonato | Pursuit-evasion in models of complex networks[END_REF], and distributed computing [START_REF] Blin | Distributed chasing of network intruders[END_REF].

Thus far, Cops and Robbers literature has focused on (several variations of) the game taking place on static graphs. Little is known with respect to Cops and Robbers games played on dynamic graphs. Dynamic graphs, sometimes called temporal networks [START_REF] Michail | An introduction to temporal graphs: An algorithmic perspective[END_REF] or time-varying graphs [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF], have received a lot of attention as they capture realistic scenarios where a graph evolves over time periodically or intermittently. Several models have been considered, for example see (12; 19; 29). In this paper, we introduce Cops and Robbers taking place on dynamic graphs in the following setting. A dynamic graph is represented by a (possibly infinite) sequence of subgraphs of the same static graph, which is the underlying graph. In other words, the (connected) underlying graph evolves over a series of discrete time steps under a set of evolution rules. We consider an offline and an online case. In the latter, in order to avoid trivial cases, we impose the natural constraint that the graph produced at each time step has to be connected. Related Work. The preliminary question in mind is to compute the minimum number of cops needed to capture the robber on some (static) graph family.

Definition 1. The cop number of a graph G, denoted c(G), is the minimum number of cops needed to ensure that the robber is eventually captured, regardless of the robber's strategy.

Problems related to the cop number have been studied heavily over the last four decades. Originally, Quillot [START_REF] Quillot | Études de quelques problèmes sur les graphes et hypergraphes et applications à la théorie des jeux à information complète[END_REF], and independently Nowakowski and Winkler [START_REF] Nowakowski | Vertex-to-vertex pursuit in a graph[END_REF], characterized graphs with cop number equal to 1, otherwise referred to as cop-win graphs. The set of (di)graphs with cop number equal to k > 1 was characterized in (14; 18). Building on these notions, a general framework for characterizing discrete-time pursuit-evasion games was developed in [START_REF] Bonato | Characterizations and algorithms for generalized cops and robbers games[END_REF].

There is a lot of literature regarding the cop number of specific graph classes. Aigner and Fromme (2) proved c(G) ≤ 3 for any planar graph G. Frankl [START_REF] Frankl | Cops and robbers in graphs with large girth and cayley graphs[END_REF] proved a lower bound for graphs of large girth. Other works include (3; 16; 26).

Moving onto general graphs, Meyniel conjectured √ n cops are always sufficient to capture the robber in any graph. The current state of the art is O(n/2 (1-o(1)) √ log n ) proved independently in (24; 35). Yet, the conjecture remains unresolved. On the contrary, the conjecture was proved positive for binomial random graphs [START_REF] Prałat | Meyniel's conjecture holds for random graphs[END_REF]; relevant works include (7; 11; 25). The cop number is also related to various width parameters, for example see [START_REF] Adler | Hypertree width and related hypergraph invariants[END_REF]. Finally, there is a book [START_REF] Bonato | The game of cops and robbers on graphs[END_REF] capturing recent activity on Cops & Robbers.

The computational complexity of the corresponding decision problem is also worth a note. Given a graph G and an integer k, does c(G) ≤ k hold? Recently, Kinnersley [START_REF] William | Cops and robbers is exptime-complete[END_REF] answered the question by proving EXPTIME-completeness. With respect to algorithmic results, for a fixed constant k, there is a polynomial time algorithm to determine whether c(G) ≤ k (4). Other algorithmic results include [START_REF] Bonato | Cops and robbers from a distance[END_REF] (capture from a distance), and (10) (generalized Cops and Robbers).

With respect to Cops and Robbers games played on dynamic graphs, there is preliminary work by Erlebach and Spooner [START_REF] Erlebach | A game of cops and robbers on graphs with periodic edgeconnectivity[END_REF]. They examine the game on edge-periodic graphs, where each edge e is present at time steps indicated by a bit-pattern of length l e used periodically and ad infinitum as evolution rule. Let LCM(L) denote the least common multiple for input lengths l e . The paper presents a O(LCM(L) • n 3 ) algorithm to determine whether the graph is 1-cop-win as well as some other results on cycle graphs. Later on, in [START_REF] Morawietz | A Timecop's Work Is Harder Than You Think[END_REF], NP-and W [START_REF] Adler | Hypertree width and related hypergraph invariants[END_REF]-hardness results are provided for (parametrizations of) Cops and Robbers played on temporal edge-periodic graphs. Further bounds and hardness results for cycle graphs in this model are given in [START_REF] Morawietz | A Timecop's Chase Around the Table[END_REF].

Our Results. We consider two dynamic graph scenarios and present preliminary results for a (classicstyle) Cops and Robbers game taking place in them. At each discrete time step of evolution, the current graph instance is fixed, then the cops take their turn, and finally the robber takes its turn. Note that movement may be restricted due to the possibly limited topology of each instance.

In the offline case, the cop and the robber know the whole evolution sequence (up to some finite time horizon T ) a priori. For an underlying graph on n vertices, we prove that deciding whether it is 1-cop-win can be done in time complexity O(n 3 T ); see Theorem 3. To do so, we employ a reduction to another game, a reachability game, played now on the configuration graph (Lemma 1). Our results extend to deciding k-cop-win graphs (Corollary 1), and an exponential time algorithm for determining the exact value of the cop-number (Corollary 2).

In the online case, no knowledge is given to the players regarding graph dynamics. The only restriction imposed is that, at each time step, the realized graph instance needs to be connected. We consider sparse graphs and show that the cop number is at most λ + 1 for underlying graphs with n -1 + λ edges; see Theorem 4. Moreover, we demonstrate a (nearly tight) graph family where λ -1 cops are necessary (and sufficient) to ensure cop victory; see Theorem 5.

Outline. In Section 2, we present introductory notions and notation on the dynamic graphs used and on the game of Cops and Robbers played on them. In Sections 3 and 4, we formalize our definitions for the respective scenario: In Section 3, we consider the offline case, whereas in Section 4, we consider the online case. In Section 5, we make concluding remarks.

Preliminaries

Dynamic Graphs. Let G = (V, E) stand for a (static) graph to which we refer to as the underlying graph of the model. We assume G is simple, i.e., not containing loops or multi-edges, and connected, i.e., there exists a path between any two vertices in G. No further assumptions are made on the topology of G. An edge from vertex v ∈ V to vertex u ∈ V is denoted as (v, u) ∈ E, or equivalently (u, v) ∈ E. We refer to the edges of the underlying graph as the possible edges of our model. We denote the number of vertices of G by n = |V | and the number of its edges by m = |E|. For any vertex v ∈ V , we denote its open neighborhood by N (v) = {u : (v, u) ∈ E} and its closed neighborhood by N

[v] = N (v) ∪ {v}. The (static) degree of v ∈ V in G is given by d(v) = |N (v)|.
The dynamic graph evolves over a sequence of discrete time steps t ∈ N. We consider two cases with respect to time evolution. First, t = 1, 2, 3, . . . , T , that is, t takes consecutive values starting from time 1 up to a time horizon T ∈ N given as part of the input. In this case, we define a dynamic graph G with a time horizon T as G = (G 1 , G 2 , . . . , G T ) (Section 3). Second, t = 1, 2, 3, . . ., that is, we consider the sequence of time steps t evolving ad infinitum (Section 4).

For any t, let G t = (V t , E t ) be the graph instance realized at time step t, where V t = V and E t ⊆ E: all vertices of the underlying graph G are present at each time step, whereas a possible edge e ∈ E may either be present/alive, i.e., e ∈ E t , or absent/dead, i.e., e / ∈ E t at time t. For any vertex v ∈ V , we denote by N t (v) = {u : (v, u) ∈ E t } its available neighborhood at time t. Similarly, let N t [v] = N t (v) ∪ {v} refer to the available closed neighborhood at time t.

Stefan Balev, Juan Luis Jiménez Laredo, Ioannis Lamprou, Yoann Pigné, Eric Sanlaville

Cops and Robber on Dynamic Graphs. We play a game of Cops and Robbers on a dynamic graph evolving under the general model defined above. There are two players: C controlling k ≥ 1 (k ∈ N) cop tokens and R controlling one robber token. Initially, C places its k tokens on the vertices of the underlying graph. Notice that we allow multiple cops to lie on the same vertex. Afterward, R chooses an initial placement for the robber. Round 0 is over. From now on, for every t ≥ 1, first, the current graph instance G t is fixed and, second, a round of the game takes place. A round consists of two turns, one for C and one for R, in this order of play. C may move any of its cops lying on a vertex v to any vertex in N t [v]. Note that all cops controlled by C move simultaneously during C's turn. After C's turn is over, R may move the robber lying on a vertex u to any vertex in N t [u]. C wins the game if, after any player's turn, the robber lies on the same vertex as a cop. R wins if it can perpetually prevent this from happening.

A cop-strategy, respectively a robber-strategy, is a set of movement decisions for the cops, respectively the robber. Having knowledge of the current positions, and the current graph instance G t (as well as all future graph instances only in the offline case), the cops/robber decide on a move for round t according to the rules of the game. A dynamic graph is called k-cop-win, if there exists a cop-strategy such that k cops win the game against any robber-strategy. For k = 1, we say that such a dynamic graph is cop-win.

Offline Case

In the offline case, we are given a dynamic graph G with a time horizon T , namely G = (G 1 , G 2 , . . . , G T ), where both C and R have complete knowledge of the evolution sequence. That is, both players are aware of G t = (V, E t ), for all t = 1, 2, . . . , T , a priori. Let c off (G) stand for the temporal cop number (offline case), the worst-case minimum number of cops required to capture a robber when the whole sequence G = (G 1 , G 2 , . . . , G T ) is given as input to both players. If the robber is not captured within T rounds, for any cop strategy, then the dynamic graph is robber-win. Overall, this is a Cops and Robbers game on a dynamic graph with bounded time horizon. From now on, we refer to it as the offline case. The results presented in this section can be viewed by the reader as an extension/completion of the work in (15) on edge-periodic graphs.

Configuration Graph. The task we tackle in the offline case is to characterize the set of given inputs (G, T ), which are cop-win, i.e., one cop can always capture the robber within the T rounds of play. To do so, we first construct a directed configuration graph capturing the cop and robber motion on G. Then, we can play another game, a reachability game [START_REF] Khaliq | Reachability games revisited[END_REF] to be defined later, on the configuration graph which corresponds to the original cop and robber game played on G and derive our result this way. We define the directed configuration graph as P = (S, A), where S refers to configuration states (vertices) and A to arcs from one state to another state which is a feasible potential next state.

The vertex set S consists of all four-tuples of the form (c, r, p, t), where t ∈ {1, 2, . . . , T } indicates the time step or round of play t, p ∈ {C, R} indicates whether it is the cop's or the robber's turn to play, c ∈ V is the position of the cop just before p's turn takes place in round t, and r ∈ V is the position of the robber just before p's turn takes place in round t.

The arc set A contains the arcs below, for all x, y ∈ V and t ∈ {1, 2, . . . , T }, such that both the dynamics of the graph and the game moves are represented:

(1) if z ∈ N t [x] and t ∈ {1, 2, . . . , T }, then ((x, y, C, t), (z, y, R, t)) ∈ A, and

(2) if z ∈ N t [y] and t ∈ {1, 2, . . . , T -1}, then ((x, y, R, t), (x, z, C, t + 1)) ∈ A

Cops and Robbers on Dynamic Graphs 5 Case (1) arcs represent the cop's turn at round t, where the cop moves within its closed neighborhood available at time t, the robber retains its position, and, after the cop moves, it is the robber's turn at round t. Respectively, case (2) arcs represent the robber's turn at round t, where the robber moves within its closed neighborhood available at time t, the cop retains its position, and, after the robber moves, it is the cop's turn, but at the next round, namely round t + 1.

Let us now consider the size of P . By the definition of the states s ∈ S, it holds for the number of vertices |S| ∈ O(n 2 T ). Considering the set of arcs A, each vertex in S has at most n arcs leaving it, therefore we obtain |A| ∈ O(n 3 T ).

Before we proceed utilizing the configuration graph, let us add some auxiliary, yet necessary, states and arcs to capture the round of initial cop and robber placement, that is, round 0. This way, we ensure the full correspondence of the reachability game played on P to the cop and robber game played on G. Note that all state and arc additions discussed hereunder do not affect the order of magnitude of the size of P . Let S contain also the states (∅, ∅, C, 0), and (x, ∅, R, 0), for all x ∈ V . State (∅, ∅, C, 0) captures the situation at round 0 before the cop's turn: neither the cop nor the robber have been placed yet on V . States (x, ∅, R, 0) capture the situation at round 0 before the robber's turn: the cop has been placed and it is the robber's turn to be placed. Overall, we have added an extra n + 1 states in S. We now proceed adding the necessary arcs in A to make the transitions from one turn to the next. For each x ∈ V , we add an arc ((∅, ∅, C, 0), (x, ∅, R, 0)) ∈ A, that is, n extra arcs in total. For each x, y ∈ V , we add an arc

((x, ∅, R, 0), (x, y, C, 1)) ∈ A, that is, n 2 extra arcs in total.
Reachability. We now employ the configuration graph P constructed above by playing another twoplayer game on it referred to in literature as a reachability game (5; 21; 27). The goal is to define a reachability game, which corresponds exactly to the Cops and Robbers game (offline case), and so be able to utilize known results in this area to prove our cop-win characterization (Theorem 3). The connection of a (classic) Cops and Robbers game to a reachability game was first identified in [START_REF] Kehagias | Cops and robbers, game theory and Zermelo's early results[END_REF]. Other results, in (11; 18), on cop-win characterizations employ similar tools without explicitly stating the reduction to reachability.

A reachability game is played by two players, C and R, where we maintain the notation such that it corresponds to players in the game of Cops and Robbers. The two players play alternately on a directed graph D = (V D , A D ), where V D is partitioned into two player-respective subsets, that is,

V D = V C ∪ V R and V C ∩ V R = ∅. Moreover, V C , respectively V R , is a pairwise non-adjacent set of vertices, that is, for any x, y ∈ V C , respectively x, y ∈ V R , it holds (x, y) ∈ A D and (y, x) ∈ A D . A single token is initially placed on a vertex v ∈ V D . If v ∈ V C ,
then C plays and moves the token to a vertex u ∈ V R for which it holds (v, u) ∈ A D . Then, it is R's turn: R chooses to move the token to a vertex w ∈ V C for which it holds (u, w) ∈ A D . Note that either player has to move the token across an available arc in A D . The game proceeds in this fashion for an indefinite number of rounds. Player C wins, if the token eventually arrives to a designated target vertex set Tar ⊆ V D . Otherwise, if for any C-strategy a vertex in Tar can never be reached, then R wins. In a nutshell, the reachability game played on D = (V D , A D ) is defined by the tuple (V C , V R , Tar ). Theorem 1 demonstrates that, depending on the initial token placement, there exists a winning strategy for one of the two players for any input (V C , V R , Tar ) and D. Moreover, by Theorem 2, it can be decided in time linear to the size of the directed graph D.

Theorem 1 ((5; 27)). Consider a reachability game (V C , V R , Tar ) played on a directed graph D = (V D , A D ). V D can be partitioned into two sets W C and W R such that, if the token is initially placed on w ∈ W p , then there exists a winning strategy for player p ∈ {C, R}.

Theorem 2 ((5; 21)).

There exists an algorithm computing winning sets W C and W R for a reachability game

(V C , V R , Tar ) played on a directed graph D = (V D , A D ) in time O(|V D | + |A D |).
Let us now consider a reachability game taking place in our constructed configuration graph P : let D = P , V D = S, and A D = A. For any (c, r, p, t) ∈ S, let (c, r, p, t) ∈ V p where p ∈ {C, R}. Finally, let Tar = {(x, x, p, t) | x ∈ V, p ∈ {C, R}, t ∈ {1, . . . , T }}. We can now use the just defined sets V C , V R , Tar to prove Lemma 1 and then, as a consequence, our main result in Theorem 3.

Lemma 1. G = (G 1 , G 2 , . . . , G T ) is cop-win, if and only if, for a reachability game (V C , V R , Tar ) played on P = (S, A), where V p = {(c, r, p, t) ∈ S | c, r ∈ V, t ∈ {0, 1, . . . , T }}, for p ∈ {C, R}, and Tar = {(x, x, p, t) ∈ S | x ∈ V, p ∈ {C, R}, t ∈ {0, 1, . . . , T }}, it holds (∅, ∅, C, 0) ∈ W C .
Proof: If G is cop-win, the cop has a winning strategy s * , which for any input cop position c, robber position r, and time step of evolution t before the cop's turn, provides the next placement for the cop token, say c . Moreover, eventually, for some t ≤ T , the cop is guaranteed to lie at the same vertex as the robber. Using the above strategy, Player C playing the reachability game on P also has a winning strategy: If the token lies at state (c, r, C, t) ∈ S, then C moves the token to (c , r, R, t). Note that, since s * is a feasible (winning) strategy for the Cops and Robbers game, by construction of P it holds ((c, r, C, t)), (c , r, R, t)) ∈ A. Also, since in s * the cop eventually lies at the same vertex as the robber, the reachability token eventually reaches a vertex (x, x, p, t) ∈ Tar , for some x ∈ V , p ∈ {C, R}, and t ≤ T . Hence, C wins the reachability game.

On the other hand, if (∅, ∅, C, 0) ∈ W C , by Theorem 1, there exists a winning strategy for C when the token lies on (∅, ∅, C, 0). For any ((c, r, C, t)), (c , r, R, t)) ∈ A chosen by C as part of its winning strategy, by construction of P , the cop has a feasible move from c to c at time t. Since C's strategy is winning, the token eventually traverses an arc ((c, x, C, t)), (x, x, R, t)) ∈ A, where (x, x, R, t) ∈ Tar . Respectively, the cop will traverse (c, x) ∈ E t and capture the robber.

Theorem 3. Given a dynamic graph G = (G 1 , G 2 , . . . , G T ) in the offline case, we can decide if c off (G) = 1, that is, if G is cop-win, in time O(n 3 T ).
Proof: By Lemma 1, it holds c off (G) = 1, if and only if, for a reachability game (V C , V R , Tar ) played on P = (S, A), where V C , V R , Tar are defined according to the statement of Lemma 1, it holds (∅, ∅, C, 0) ∈ W C . By Theorem 2, we decide whether

(∅, ∅, C, 0) ∈ W C in time O(|S| + |A|) = O(n 2 T + n 3 T ) = O(n 3 T ).
An important remark is that, in Theorem 1 (5; 21), the winning strategy derived for player p ∈ {C, R} is memoryless; see Proposition 2.18 in [START_REF] Mazala | Infinite games[END_REF]. In other words, it only depends on the current position of the token, and not on any past moves. By the reduction presented in Lemma 1, the winning strategy for the cop/robber is also memoryless: it only depends on the current positions of the cop, the robber, and the time step of evolution.

Let us conclude this part by explaining how the above framework can be generalized and therefore used to determine whether a dynamic graph

G = (G 1 , G 2 , . . . , G T ) is k-cop-win, when k > 1.
Since k cops are placed on V throughout the game, it suffices to expand our definition of states by substituting the cop position by a k-tuple of cop positions. That is, the state set S of the configuration graph P now contains tuples of the form ((c 1 , c 2 , . . . , c k ), r, p, t), where c i , for i ∈ {1, 2, . . . , k}, denotes the location of the i-th cop in V . For the arc set, for C, we add

(((c 1 , c 2 , . . . , c k ), r, C, t), ((c 1 , c 2 , . . . , c k ), r, R, t)) ∈ A, if for each i ∈ {1, 2, . . . , k} it holds c i ∈ N t [c i ]. For R, we get (((c 1 , c 2 , . . . , c k ), r, R, t), ((c 1 , c 2 , . . . , c k ), r , C, t+ 1)) ∈ A, if it holds r ∈ N t [r]
. Again, we include auxiliary states and arcs to cater for the initial placements. Overall, we now get |S| ∈ O(n k+1 T ), and |A| ∈ O(n 2k+1 T ), since for the dominantin-magnitude number of C-turn arcs there exist at most n 2k cop transitions from (c 1 , c 2 , . . . , c k ) to (c 1 , c 2 , . . . , c k ). By reapplying the whole framework with Tar = {((c 1 , c 2 , . . . , c k ), r, p, t) | c i = r for some 1 ≤ i ≤ k} we conclude:

Corollary 1. Given a dynamic graph G = (G 1 , G 2 , . . . , G T ) and an integer k ≥ 1 in the offline case, we can decide if c off (G) ≤ k, i.e., if G is k-cop-win, in time O(n 2k+1 T ).
We may now run a search utilizing the result in Corollary 1 and derive an exponential time algorithm to determine the exact value of c off (G).

Corollary 2. For some dynamic graph G, with an associated time horizon T , the problem of determining the exact value of c off (G) is in EXPTIME.

Online Case

In the online case, we are given an underlying graph G = (V, E) and an indefinite number of discrete time steps of evolution t = 1, 2, 3, . . ., that is, time evolution may take place ad infinitum. At each time step t, an instance

G t = (V t , E t ) is realized, where V t = V , E t ⊆ E.
The only assumption we make on the topology of generated instances, is that we require each G t to be connected. Note that this is a widely used assumption in several dynamic graphs appearing in literature (12; 28). Removing this assumption could lead to trivial cases where, for instance, the k cops or the robber lie indefinitely on isolated vertices.

Initially, the cops and then the robber place themselves on V before the appearance of G 1 . In the general case, neither the cops nor the robber have any knowledge about the evolution sequence. The cops and the robber, taking turns in this order, make their respective moves in G t , then G t+1 is generated, and so forth. Similarly to the offline case, a token at vertex v moves to a vertex in N t [v] (all the cops move simultaneously). Let c t (G) stand for the temporal cop number, the worst-case minimum number of cops required to capture a robber for an underlying graph evolving like described above. In our analysis, we consider worst-case scenarios for the temporal cop number; a different type of analysis is left for future work. In other words, for our bounds to follow, one may assume the robber controls the dynamics of G to its advantage. Hence, at round t, the robber defines instance G t according to the above restrictions.

Preliminary Bounds. As a warm up, let us consider two special cases for the topology of the underlying graph: a tree, and a complete graph. Proposition 1. For any tree T , it holds c t (T ) = 1.

Proof: Since, for any time step t, G t must be connected, it follows G t = T . Since the topology of the tree remains static over time, it holds c t (T ) = c(T ). It suffices to verify c(T ) = 1 for any T (26).

Proposition 2. For any complete graph

K n , n ≥ 2, it holds c t (K n ) = n -1. Proof: It holds c t (K n ) ≤ n -1, since we can initially place n -1 cops on n -1 distinct vertices at K n .
The robber places itself on the only cop-free vertex. Then, G 1 is realized: since G 1 is connected, there exists at least one edge connecting a cop-vertex to the robber-vertex. The corresponding cop traverses that edge and captures the robber at the first cop turn.

Stefan Balev, Juan Luis Jiménez Laredo, Ioannis Lamprou, Yoann Pigné, Eric Sanlaville

We now demonstrate c t (K n ) > n -2. The n -2 cops are initially placed on vertices of V . The robber places itself on a cop-free vertex. Regardless of the cops placement, at any time, there are always at least two cop-free vertices. Without loss of generality, for each time t, G t is a path v 1 , v 2 , . . . , v n-1 , v n with the currently cop-free vertices at one end of the path. For example, the robber lies on v 1 , and v 2 (and possibly other vertices) are cop-free. The cops move during their turn, but they cannot capture the robber: Since the number of cop-free vertices is at least two, a cop can only reach a vertex at distance at least one from the robber (v 2 ). The robber remains at its position indefinitely and avoids capture.

The above propositions cast some intuition on the relationship between the (static/classical) cop number c(G) and our introduced temporal cop number c t (G). For the static case, it is easy to see that if G is either a tree or a clique then c(G) = 1. However, in the temporal case c t (T ) = 1 for a tree T , and c t (K n ) = n-1 for any clique on n ≥ 2 vertices. Intuitively, the denser the underlying graph is, the more leeway there is for the robber due to worst-case dynamics. Overall, for any graph G, c t (G) ≤ n -1, since initially placing the n -1 cops on distinct vertices guarantees an edge between a cop-vertex and the robber-vertex in G 1 due to connectedness. Thus, for the ratio of the two cop numbers, we get

1 ≤ c t (G)/c(G) ≤ n -1.
We now provide a preliminary bound on c t (•) by considering a subset of sparse graphs, that is, underlying graphs with at most linear number of edges.

Theorem 4. For any graph G = (V, E), m = n -1 + λ, it holds c t (G) ≤ λ + 1.
Proof: To describe the cop-winning strategy, let us define a partition of the vertices into

V C and V R such that V = V C ∪ V R and V C ∩ V R = ∅.
Intuitively, V C stands for the cop-secured vertices, i.e., vertices the robber will never be able to visit, whereas V R stands for the vertices (possibly) still within the eventual reach of the robber. More precisely, the cop strategy below builds a sequence of partitions (V C , V R ) where V C is a set of vertices the robber will never be able to visit, V R contains the other vertices and the cardinality of V R strictly decreases at each time step. This strategy may not be the fastest as V R may contain robber-unreachable vertices, but this is not required for the proof.

Consider the situation before some round t. Let T denote some (arbitrary) spanning tree of G. We refer to the edges of T as the black edges and to any path consisting only of black edges as a black path. We refer to all other edges, which are exactly λ, as the blue edges. Suppose there is one cop at one extremity of each blue edge. Note that several cops may lie on the same vertex. We refer to these cops as the blue cops. One last cop, the black cop, is placed on some other (blue-cop free) vertex, say x ∈ V . The robber is on a cop-free vertex, say r ∈ V . For a visual assistance for the rest of the proof, please refer to Figure 1.

Consider the spanning tree T : there exists a unique (black) path from x to r. Let (x, x ) be the first edge of this path. If this edge is removed from the black tree T , T is split into two black subtrees containing x and x respectively, namely T x and T x . Then, let

V C = V (T x ) and V R = V \ V C = V (T x ). Notice that it holds r ∈ V R with this partition.
By construction, the cut associated to (V C , V R ) contains exactly one black edge, (x, x ), plus (possibly) some blue edges. Since G t is connected for all time steps t, at least one edge associated to the cut is present in E t . If the black edge (x, x ) is present, then the black cop moves from x to x during the cops turn. Otherwise, if only a blue edge, say (v, v ), where v ∈ V C , is present, then the associated cop moves from v to v (or remains at v if it were already there). Now, we swap the role of the two edges. That is, (v, v ) becomes a black edge, and its associated cop becomes the black cop, whereas (x, x ) becomes a blue edge, and its associated cop becomes a blue cop. By construction, the set of black edges defines a new black spanning tree T : the unique black path from v to v is replaced by the new black edge (v, v ).

(Notice that, in the previous swap-less case, we trivially had T = T ). Afterwards, the robber may move at its turn; we still refer to its position by r. Even after the robber moves, it holds r ∈ V R \ {v }: there is no edge the robber could use to reach V C since all cut-edges are protected, and v is occupied by the black cop.

Before the next round of the game, let us now reapply the method used to obtain the partition on G t+1 . Let x = v stand for the black cop's current position, and set T = T . Consider again the unique black path from x to r, and denote by (x, x ) its first edge. By construction of T , there is a unique black path from x to all vertices of V C . Hence, if T is split as before into two subtrees after removing edge (x, x ), the resulting subtree T x contains x and also all vertices of former V C (and possibly more vertices). Then, let us set

V C = V (T x ) and V R = V \ V C = V (T x ).
As there is still one cop on one extremity of each blue edge, the vertices of V C are unreachable by the robber.

Let us now consider the very first step. We start from an arbitrary spanning tree, denoted by T , whose edges are the black ones, the other being the blue ones. For the initial positions, let us place one cop at one extremity of each blue edge. One last cop, the black cop, is placed on some other (blue-cop free) vertex, say x ∈ V . Then, the robber chooses a cop-free vertex, say r ∈ V , for its initial place. Edge (x, x ), and sets V C and V R are similarly defined, hence the vertices of V C are unreachable by the robber. The cardinality of V R is at most n -1.

If we inductively apply the above method for the cops, it follows that after each round, the number of vertices of V R , which contains the vertices reachable by the robber, is strictly decreased. It will eventually reach the value of zero and the robber will be captured in at most n rounds. robber space cop space Fig. 1: A depiction for the proof of Theorem 4. The black cop lies on x, with x at the other side of the cut. Colored vertices/edges indicate blue cops/edges.

Stefan Balev, Juan Luis Jiménez Laredo, Ioannis Lamprou, Yoann Pigné, Eric Sanlaville

The above result provides a better upper bound than the easy to see c t (G) ≤ n -1, for sparse graphs when λ ≤ n -3. For λ = 1, cycle graphs are a tight example. We demonstrate the result is nearly tight for certain graph families, see Theorem 5 in the next part of this section.

A nearly tight graph family for sparse graphs. We hereby consider the graph family G = {G λ |λ mod 2 = 1 ∧ λ ≥ 5} for sufficiently large odd values of λ ∈ N. We define the vertex set as

V (G λ ) = {v 1 , v 2 , . . . , v 2λ-2 , v 1 , v 2 , . . . , v 2λ-2 }. For i = 1, 2, . . . , 2λ -2, let (v i , v (i+1) mod (2λ-2) ) ∈ E(G λ ) and (v i , v i ) ∈ E(G λ )
. Note, we assume v 0 ≡ v 2λ-2 for the use of modulo above. Also, for i = 1, 3, 5, . . . , 2λ -3, let

(v i , v i+1 ) ∈ E(G λ ). Overall, it holds n = |V (G λ )| = 4λ -4 and m = |E(G λ )| = 2(2λ -2) + (2λ -2)/2 = 5(2λ -2)/2 = 5λ -5 = n -1 + λ.
Intuitively, G λ is a cycle on 2λ -2 vertices where another λ -1 disjoint 4-cycles are attached. An example depiction is given in Figure 2. Notice that G λ becomes a tree by the removal of λ edges, for example, the λ -1 edges (v i , v i+1 ), for i = 1, 3, 5, . . . , 2λ -3 and another edge (v j , v j+1 ) for some j ∈ {1, 2, . . . , 2λ -3}.

v 1 v 1 v 2 v 2 v 3 v 3 v 4 v 4 v 5 v 5 v 6 v 6 v 7 v 7 v 8 v 8 v 9 v 9 v 10 v 10 v 11 v 11 v 12 v 12
Fig. 2: The graph G 7 ∈ G.

Theorem 5. For any

G λ ∈ G, it holds c t (G λ ) = λ -1.
This theorem is a direct consequence of the two lemmata that follow, which demonstrate the corresponding (worst-case) upper and lower bound strategies.

Lemma 2. For any

G λ ∈ G, it holds c t (G λ ) ≤ λ -1.
Proof: We present a strategy for λ -1 cops to win against the robber under any dynamics and/or robber strategy. Initially, the λ-1 cops are placed as follows: place one cop at v i for each i = 2, 6, 10, . . . , 2λ-4 and for each i = 3, 7, 11, . . . , 2λ -3. To verify, since there are two sequences of cops using a distance 4 step, overall the number of cops is 2(2λ -2)/4 = λ -1. For an example placement on G 7 , see Figure 3. Then, the robber places itself at some cop-free vertex. By symmetry of G λ and cop placement, without loss of generality, we assume the robber places itself on some vertex in R := {v 4 , v 5 , v 3 , v 4 , v 5 , v 6 }. In the cop strategy we will now propose, the robber will never be able to escape this set of vertices. Therefore, we restrict the proof to the subgraph induced by {v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 3 , v 4 , v 5 , v 6 }, see Figure 4a, and will demonstrate how the four cops in this subgraph can always capture a robber with an initial placement within R. For all robber turns below, we assume the robber always remains within R; by our strategy, it is impossible for the robber to move outside R since it would mean "jumping" over a cop.

v1 v 1 v2 v 2 v3 v 3 v4 v 4 v5 v 5 v6 v 6 v7 v 7 v8 v 8 v9 v 9 v10 v 10 v11 v 11 v12 v 12 1 1 1 1 1 1
Fig. 3: The initial positions for cops in graph G 7 ∈ G. In all figures, an integer within a vertex stands for the number of cops currently placed on the vertex.

v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 1 1 1 1
(a) Initial positions for cops in subgraph.

v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 1 1 2
(b) After the first move: a cop moved from v7 to v6.

Fig. 4: The first move of the cop strategy

The cops' strategy is the following. Since the instance needs to be connected at each time step, at least one edge in {(v 2 , v 3 ), (v 6 , v 7 )} is available. By symmetry, without loss of generality, assume (v 6 , v 7 ) is present and the cop on v 7 moves to v 6 , see Figure 4b. It suffices to prove that the cops have a winning strategy starting from this configuration.

In the next round (following Figure 4b), the cops move as follows. If (v 6 , v 6 ) is available, then one of the cops moves to v 6 (Case 1, Figure 5a). Otherwise, if (v 6 , v 6 ) is not available, in order to ensure connectivity of the instance, either (v 6 , v 5 ) is available, and one cop moves to v 5 (Case 2, Figure 6a), or (v 2 , v 3 ) is available and one cop moves to v 3 , so that two cops lie on v 3 (Case 3, Figure 7a). In all cases, the robber takes its turn in R.

In Case 1, at least one cop can move to vertex v 5 (Case 1a, Figure 5b), v 5 (Case 1b, Figure 5c), or v 3 (Case 1c, Figure 5d) by connectivity of the instance. In Case 1a, one cop can move either to v 5 or to v 3 , otherwise the instance is disconnected. If a cop moves to v 5 , the robber lies within {v 4 , v 3 , v 4 } and at the next step a cop traverses either (v 5 , v 4 ) (hence the robber is trapped on v 3 or v 4 and loses within the next two rounds) or (v 2 , v 3 ) (hence at the next round either a cop arrives at v 4 and the robber is blocked or a cop arrives at v 3 and the robber loses at the following round). If starting from Case 1a a cop moves to v 3 , then in the next round a cop can move to {v 5 , v 4 , v 3 }: if a cop moves to v 5 , in the next round a cop can move to {v 4 , v 3 } and the robber loses in at most two rounds, otherwise, if a cop moves to v 4 or v 3 , the robber again loses in at most two rounds regardless its strategy. In Case 1b, the robber loses if it was on v 5 . Otherwise, a cop can traverse either (v 5 , v 4 ) or (v 2 , v 3 ) and the rest of the strategy is the same as for Case 1a. In Case 1c, at least one cop can move to a vertex in {v 5 , v 5 , v 4 , v 3 }. Similarly to above, in all subcases, it is easy to see that the cops win in at most two steps against any robber position/movement. In Case 2, if the robber lies on v 5 or v 6 , it is easy to see the cops win in at most two steps, since connectivity to the rest of the graph must be maintained. Instead, if the robber lies in {v 4 , v 3 , v 4 }, then a cop traverses either (v 5 , v 4 ) (Case 2a, Figure 6b) or (v 2 , v 3 ) (Case 2b, Figure 6c). In Case 2a, we arrive to 4-cycle {v 3 , v 4 , v 3 , v 4 } with cops on v 4 and v 3 , and as before, the cops win in at most two steps. In Case 2b, again by preservation of connectivity, at least one edge in {(v 5 , v 4 ), (v 3 , v 4 ), (v 3 , v 3 )} must be available and one cop moves to either v 4 or v 3 . In either case, the cops win in at most another two steps.

v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 1 1 1 1 (a) Case 1 v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 1 1 1 1 (b) Case 1a v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 1 1 1 1 (c) Case 1b v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 2 1 1 (d) Case 1c
In Case 3, before they take this new turn, two cops lie on v 6 and another two cops lie on v 3 . By preservation of connectivity, at least one cop can reach a vertex in {v 6 , v 5 , v 4 , v 3 }. By symmetry, it suffices to consider the worst-case scenarios where a cop arrives on v 6 (Case 3a, Figure 7b) and v 5 (Case

v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 1 1 1 1 (a) Case 2 v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 1 1 1 1 (b) Case 2a v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 2 1 1 (c) Case 2b
Fig. 6: Case 2 analysis for the proof of Lemma 2

v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 2 2 (a) Case 3 v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 2 1 1 (b) Case 3a v2 v3 v4 v5 v6 v7 v 6 v 5 v 4 v 3 2 1 1 (c) Case 3b
Fig. 7: Case 3 analysis for the proof of Lemma 2 3b, Figure 7c). We notice Case 3a is the same as Case 1c and Case 3b the same as Case 2b.

To help us with the matching lower bound to follow, we hereby provide some useful definitions and claims on cop movement restrictions on G λ incurred by worst-case dynamics. From now on, all vertex indices are assumed to be modulo 2λ -

2 with v 0 ≡ v 2λ-2 . For i = 1, 2, . . . , λ -1, let loop L i refer to the 4-cycle with V (L i ) = {v 2i-1 , v 2i , v 2i-1 , v 2i } and let its edge-set be defined as E(L i ) = {(v 2i-1 , v 2i ), (v 2i-1 , v 2i ), (v 2i-1 , v 2i-1 ), (v 2i , v 2i )}.
We say that L i is cop-occupied if at least one cop lies at some vertex in V (L i ), otherwise, L i is cop-free. We say that a cop crosses L i if, starting from vertex v 2i-1 (cross-start vertex), it can eventually arrive to vertex v 2i (cross-end vertex), or vice versa. We refer to a (counterclockwise-movement) crossing from v 2i-1 to v 2i as a cc-crossing and to a (clockwisemovement) crossing from v 2i to v 2i-1 as a c-crossing. A cop trivially cc-crosses L i if it already lies on v 2i or v 2i+1 , i.e., the counterclockwise neighbor of v 2i . Respectively, a cop trivially c-crosses L i if it already lies on v 2i-1 or v 2i-2 , i.e., the clockwise neighbor of v 2i-1 . The intuition behind Proposition 3 is that, while a number of cops crosses a loop, at least one of them must stay behind, that is, will not be able to ever cross the loop due to worst-case dynamics.

Proposition 3. Assume we focus on a given loop L i ⊂ V (G λ ) and at most one edge in E(L i ) is not present at each time step of evolution. In the worst case, at most ρ cops can cross L i , if ρ + 1 cops are present at the cross-start vertex.

Proof: Without loss of generality, consider loop L 1 = {v 1 , v 2 , v 1 , v 2 } and suppose ρ + 1 cops lie on v 1 and wish to cross to v 2 . The dynamics of the graph evolve as follows: for each t, if at the end of round t there is at least one cop on v 1 , then (v 1 , v 2 ) ∈ E t+1 . Otherwise, (v 1 , v 2 ) ∈ E t+1 . In other words, as long as there is a cop on v 1 , the edge to v 2 is blocked. The cops could take advantage of this situation such that at most ρ of them reach v 2 via the available path v 1 , v 1 , v 2 , v 2 . If at any time v 1 is cop-free, then the above path is blocked and (v 1 , v 2 ) is available, however no cop is there to traverse it and cross the loop. The last remaining cop cannot cross since it would mean that, at some point in time, either v 1 is cop-occupied and (v 1 , v 2 ) is available or v 1 is cop-free and (v 1 , v 2 ) is available, a contradiction to the specified dynamics.

Assume strictly fewer than λ -1 cops initially place themselves at the vertices of G λ . Since there are λ -1 loops, there exists at least one cop-free loop L i . In general, after the cops are initially positioned, G λ can be partitioned into alternating sequences of cop-occupied and cop-free loops L i . Let O 1 , . . . , O p , respectively F 1 , . . . , F p , stand for the sequences of cop-occupied, respectively cop-free loops, where F 1 is set arbitrarily, and we assume F i is between O i (clockwise) and O i+1 (counterclockwise). Moreover, for i = 1, 2, . . . , p, let |F i | = f i and |O i | = o i . The cardinality p of the two sequence sets is the same, since two non-maximal adjacent cop-occupied subsequences, i.e., with no cop-free loop between them, form one bigger cop-occupied sequence; a similar observation holds for cop-free sequences. By the reasoning above, it holds p ≥ 1. An example initial placement on G 7 is given in Figure 8: The sequences of copoccupied and cop-free loops formed are The following proposition provides us with a necessary condition in order for the cops to win against a robber placed on some cop-free sequence of loops. For a sequence

O 1 = {L 6 , L 1 , L 2 }, F 1 = {L 3 }, O 2 = {L 4 }, and F 2 = {L 5 }. v 1 v 1 v 2 v 2 v 3 v 3 v 4 v 4 v 5 v 5 v 6 v 6 v 7 v 7 v 8 v 8 v 9 v 9 v 10
F = {L 1 , L 2 , . . . , L f }, let V (F ) = ∪ f i=1 V (L i ). Proposition 4. Let F = {L 1 , L 2 , .
. . , L f } be a cop-free sequence of loops with the robber lying on some vertex within V (F ) not adjacent to a cop. Let L cc , respectively L c , stand for the cop-occupied loop adjacent to the counter clockwise of F , respectively to the clockwise of F . At least f + 1 cops must be able to c-cross L cc , and another f + 1 cops to cc-cross L c , in order for the cops to win.

Proof: In contradiction, and without loss of generality, assume whenever f + 1 cops can cc-cross L c at most f cops can c-cross L cc . Assume L f is clockwise adjacent to L cc , L i is clockwise adjacent to L i+1 for i = 1, 2, . . . , f -1, and L c is clockwise adjacent to L 1 ; see Figure 9. From now on, consider that the dynamics of the graph force the single edge connecting L c to L 1 to be unavailable in all graph instances. So, no cop may leave L c and reach L 1 in F by moving counterclockwise and each graph instance remains connected.

L c L 1 L 2 L f -1 L f L cc • • •
Fig. 9: Loop numbering for a cop-free sequence F = {L 1 , L 2 , . . . , L f }. Left stands for counterclockwise direction in G λ , respectively right for clockwise direction.

Having crossed L cc , the f cops may all move to L f . By Proposition 3, at most f -1 cops can ccross L f . For some i ≥ 1, assume fi cops have c-crossed L f +1-i . Then, by Proposition 3, at most

f -i -1 = f -(i + 1) cops can c-cross L f +1-(i+1) . Overall, by induction, at most f -i cops are able to c-cross L f +1-i . For i = f -1, at most f -(f -1) = 1 cop is able to c-cross L 2 .
To win, the robber has a feasible strategy to evade indefinitely, that is, to be placed at the vertex in L 1 connected by the (always unavailable) edge to L c as discussed above. No cop can arrive to L 1 from L c due to the missing edge, and since at most 1 cop can c-cross L 2 , no cop can ever c-cross L 1 . Now, we are ready to show, in Proposition 5, how the robber can identify a cop-free sequence to employ the winning strategy demonstrated in Proposition 4.

For integers i, w i , w i , where

1 ≤ i ≤ λ -1, 0 ≤ w i ≤ p -1, 0 ≤ w i ≤ p -1, let F c (i, w i ) = {F i , F i-1 , .
. . , F i-wi } stand for the set including F i and the w i cop-free sequences nearer to F i in clockwise fashion, and F cc (i, w i ) = {F i , F i+1 , . . . , F i+w i } stand for the set including F i and the w i cop-free sequences nearer to F i in counterclockwise fashion. In a similar manner, for the cop-occupied sequences, let O c (i, w i ) = {O i , O i-1 , . . . O i-wi } and O cc (i, w i ) = {O i , O i+1 , . . . , O i+w i }. For a cop-occupied sequence O i , we say that o i = |O i | cops (choosing one per loop in O i ) are its occupant cops. If strictly more than o i cops lie at vertices of O i , then this surplus of cops are referred to as extra cops. Proposition 5. If there exists a cop-free sequence F i in G λ such that at least one of the following holds: (a) strictly fewer than Fj ∈Fc(i,wi) f j extra cops lie within vertices in O c (i, w i ), for all integers w i , where 0 ≤ w i ≤ p -1, (b) strictly fewer than Fj ∈Fcc(i,w i ) f j extra cops lie within vertices in O cc (i + 1, w i ), for all integers w i , where 0 ≤ w i ≤ p -1, then the robber wins.

Proof: Assume the cops are initially placed and the robber is able to identify a cop-free sequence F i = {L 1 , . . . , L fi }, where, for i = 1, 2, . . . , f i -1, L i is clockwise adjacent to L i+1 , L c is clockwise adjacent to L 1 and L fi is clockwise adjacent to L cc , like in Figure 9, such that at least one of (a) and (b) holds.

Stefan Balev, Juan Luis Jiménez Laredo, Ioannis Lamprou, Yoann Pigné, Eric Sanlaville Without loss of generality, we hereby consider only case (a); the other case follows in similar manner by symmetry.

The robber strategy is simply to place itself at vertex v in L fi , which is adjacent to vertex u in L cc and, from now on, consider that the dynamics always force edge (v, u) to be unavailable. We now show that no cop can cc-cross L fi , therefore the robber wins.

For w i = 0, strictly fewer than f i extra cops lie in O c (i, 0) = {O i }. Hence, by using only cops within O c (i, 0), at most f i cops can cross L c : the extra cops in O i and, by Proposition 3, at most one occupant cop, e.g., the one occupying L c by its initial placement. By Proposition 4, the robber wins.

Inductively, assume that, for some w where 0 ≤ w < p -1, for all w i ≤ w it holds that, by only using cops within O c (i, w i ), at most f i cops can cross L c . If we consider w + 1, by assumption, for w i = 0, 1, . . . , w + 1, strictly fewer than Fj ∈Fc(i,wi) f j extra cops lie within O c (i, w i ). Let f < Fj ∈Fc(i,w) f j be the number of extra cops within O c (i, w) and f < Fj ∈Fc(i,w+1) f j be the number of extra cops within O c (i, w + 1). Then,

f * = f -f ≥ 0 extra cops lie within O c (i, w + 1) \ O c (i, w) = {O i-(w+1) }.
We consider two cases:

• If f * ≥ f i-(w+1) ,
(i, w) = O c (i, w) \ {O i-w } ∪ {O i-w } is f -f i-(w+1) < Fj ∈Fc(i,w+1) f j -f i-(w+1) =
Fj ∈Fc(i,w) f j . By the inductive assumption for w, by only using cops within O c (i, w), at most f i cops can cross L c . Since at most f i cops can cross L c for all possible w i ≤ w, then by Proposition 4, the robber wins. By assumption, their number is f < Fj ∈Fc(i,w) f j and the proof follows as in the first case.

Proposition 6. Assume strictly fewer than λ -1 cops are initially placed on G λ . Then, there exists a cop-free sequence F i in G λ such that at least one of conditions (a) and (b) in Proposition 5 holds.

Proof: Since strictly fewer than λ -1 cops are initially placed on G λ , and G λ has exactly λ -1 loops L i , then by pigeonhole principle there exists at least one loop with no cop on its vertices, and so at least one cop-free sequence in G λ . By contradiction, suppose that for every cop-free sequence F i in G λ (i) there exists w i such that at least Fj ∈Fc(i,wi) f j extra cops lie within O c (i, w i ), and (ii) there exists w i such that at least Fj ∈Fcc(i,w i ) f j extra cops lie within O cc (i + 1, w i ). Consider some cop-free sequence, say F i1 , where i 1 = 1 without loss of generality. By (ii), there exists some (minimum-value) w i1 such that at least Fj ∈Fcc(i1,wi 1 ) f j extra cops lie within O cc (i 1 + 1, w i1 ). Let F i2 = F i1+1+wi 1 be the first cop-free sequence to the counterclockwise of O cc (i 1 + 1, w i1 ). Then, by (ii), there exists some (minimum-value) w i2 such that at least Fj ∈Fcc(i2,wi 2 ) f j extra cops lie within O cc (i 2 + 1, w i2 ). We proceed with such statements, inductively, until we reach F i l , for which there exists (minimum-value) w i l such that at least Fj ∈Fcc(i l ,wi l ) f j extra cops lie within O cc (i l + 1, w i l ) and i l + 1 + w i l ≥ p + i 1 . That is, we have performed a full round on G λ . There are three cases to consider with respect to the value i l + 1 + w i l .

• If i l + 1 + w i l = p + i 1 , then, for i z = i 1 , i 2 , . . . , i l , sets O cc (i z + 1, w iz ) form a partition of the cop-occupied space in G λ . By assumption, for each such i z , at least Fj ∈Fcc(iz,wi z ) f j extra cops lie within O cc (i z + 1, w iz ). Summing it all, l z=1 Fj ∈Fcc(iz,wi z ) f j = p j=1 f j extra cops lie within the cop-occupied sequences, since ∪ l z=1 F cc (i z , w iz ) contains all cop-free loops in G λ . • If i l +1+w i l = p+i y , for some y > 1, then the last interval fully covers some already defined intervals starting at i 1 , i 2 , . . . , i y-1 . In this case, for i z = i y , i y+1 , . . . i l , sets O cc (i z +1, w iz ) form a partition of the cop-occupied space in G λ . By assumption, for each such i z , at least Fj ∈Fcc(iz,wi z ) f j extra cops lie within O cc (i z + 1, w iz ). Summing it all together as in the previous case, at least l z=y Fj ∈Fcc(iz,wi z ) f j = p j=1 f j extra cops lie within the cop-occupied sequences. • If p + i y < i l + 1 + w i l < p + i y+1 , for some y > 1, then the last interval fully contains intervals starting at i 1 , i 2 , . . . , i y-1 and partially overlaps with interval i y . Let i l + 1 + w i l = p + i y + x for some 1 ≤ x ≤ i y+1i y . There are strictly fewer than f iy + f iy+1 + . . . For the rest of the graph, for z = y + 1, . . . , l -1, at least Fj ∈Fcc(iz,wi z ) f j extra cops lie within O cc (i z + 1, w iz ). Summing it all together, at least p j=1 f j extra cops lie within the cop-occupied sequences, since each f j is considered once in the above calculations.

+
In all three cases, considering occupant cops and extra cops together, it follows there are at least p i=1 (o i + f i ) = λ -1 cops in G λ , since the number of loops in all the sequences is exactly the number of loops in G λ . Lemma 3. For any G λ ∈ G, it holds c t (G λ ) ≥ λ -1.

Proof: Follows by the combination of Propositions 5 and 6.

Conclusions

In this paper, we consider the topic of playing Cops and Robbers games on dynamic graphs. We show how the cop number can be computed in the offline case, where all graph dynamics are known a priori, via a reduction to a reachability game. In the online case with a connectedness restriction, we show a nearly tight bound on the cop number of a family of sparse graphs.

In the future, considering the online case, we would like to tighten the bound for sparse graphs, and also consider dense graphs.

Fig. 5 :

 5 Fig. 5: Case 1 analysis for the proof of Lemma 2

Fig. 8 :

 8 Fig. 8: An initial placement of λ -2 = 5 cops on G 7 .

•

  If f * < f i-(w+1) , by inductively applying Proposition 3, move all f * extra cops in O i-(w+1) to become occupant cops of some free loops in F i-(w+1) . Let F * , where |F * | = f * , denote the formerly free loops which are now occupied. We now reset O i-(w+1) to a larger sequence O i-(w+1) containing all loops in F * and O i-(w+1) . We wish to use cops only within O c (i, w+1) = O c (i, w+ 1) \ {O i-(w+1) } ∪ {O i-(w+1) }. Since no extra cops remain within O i-(w+1) , we focus only on the number of extra cops within O c (i, w).

  by inductively applying Proposition 3, move f i-(w+1) out of the f extra cops in O i-(w+1) to become occupant cops of all the free loops in F i-(w+1) . Since there is no free loop left between the original sequences O i-w and O i-(w+1) , we now reset O i-w to a larger sequence O

i-w containing all loops in O i-w , F i-(w+1) , O i-(w+1)

. The number of extra cops within vertices in O c

  f iy+x-1 extra cops within vertices in O iy+1 , . . . , O iy+x , otherwise the choice of w iy would not be minimum. As an implication, there are at least f iy+x + . . . + f iy+wi y extra cops within O iy+x+1 , . . . , O iy+wi y +1 . Also, by assumption, at leastf i l + f i l +1 + . . . + f 1 + . . . + f iy+x-1 extra cops lie within vertices in O i l +1 , O i l +2 , . . . , O 1 , . . . , O iy+x . Overall, at least f i l + f i l +1 + . . . + f 1 + . . . + f iy+x-1 + f iy+x + . . . + f iy+wi y extra cops lie within O i l +1 , O i l +2 , . . . ,O 1 , . . . , O iy+x , O iy+x+1 , . . . , O iy+wi y +1 .

Stefan Balev, Juan Luis Jiménez Laredo, Ioannis Lamprou, Yoann Pigné, Eric Sanlaville


Minh-Quyet Ha

Duong-Nguyen Nguyen

Viet-Cuong Nguyen

Hiori Kino

Yasunobu Ando

Takashi Miyake

Thierry Denoeux

Van-Nam Huynh

Hieu-Chi Dam
email: dam@jaist.ac.jp

J K Rudin

T.-L Nguyen

V.-C Pham

T.-D Nguyen

Evidence-based data mining method to reveal similarities between materials based on physical mechanisms Evidence-based data mining method to reveal similarities between materials based on physical mechanisms

Measuring the similarity between materials is essential for estimating their properties and revealing the associated physical mechanisms. However, current methods for measuring the similarity between materials rely on theoretically derived descriptors and parameters fitted from experimental or computational data, which are often insufficient and biased. Further, outliers and data generated by multiple mechanisms are usually included in the dataset, making the data-driven approach challenging and mathematically complicated. To overcome such issues, we apply the Dempster-Shafer theory to develop an evidential regression-based similarity measurement (eRSM) method, which can rationally transform data into evidence. It then combines such evidence to conclude the similarities between materials, considering their physical properties. To evaluate the eRSM, we used two materials datasets, including 3d transition metal-4f rare-earth binary and quaternary high-entropy alloys with target properties, Curie temperature and magnetization. Based on the information obtained on the similarities between the materials, a clustering technique is applied to learn the cluster structures of the materials that facilitate the interpretation of the mechanism. The unsupervised learning experiments demonstrate that the obtained similarities are applicable to detect anomalies and appropriately identify groups of materials whose properties correlate differently with their compositions. Furthermore, significant improvements in the accuracies of the predictions for the Curie temperature and magnetization of the quaternary alloys are obtained by introducing the similarities, with the reduction in mean absolute errors (MAE) of 36% and 18%, respectively. The results show that the eRSM can adequately measure the similarities and dissimilarities between materials in these datasets with respect to mechanisms of the target properties.

I. INTRODUCTION

The concept of machine learning has great potential for application in several areas of materials science, especially for discovering new materials. In materials science, a number of the problems addressed by data-driven approaches require the effective utilization of existing material data for predicting the properties of new materials and understanding the underlying physicochemical mechanisms 1 . From an engineering point of view, developing a datadriven model that quickly and accurately predicts the physical properties of possible materials from accumulated data can reduce the time required for material development. By applying a data-driven model to screen materials in-silico, we narrow down the candidates that require expensive calculations and experiments to verify. If there are sufficient independent supervised data from the distribution of the target material data, a model with high prediction accuracy can be built using state-of-the-art data-driven techniques. However, because materi-55 als research and development aim to develop materials 56 that are superior to existing ones, the distribution of the 57 target prediction data may be completely different from 58 the distribution of the original training data. Therefore, 59 there are concerns about whether data-driven models can 60 accurately predict the physical properties of new materi-61 als. 62 On the contrary, considering the history of materi-63 als science, researchers have discovered various materi-64 als through a loop of hypothesis and verification based 65 on their knowledge, experience, and serendipity. Partic-66 ularly, hypothesizing relies heavily on describing, inter-67 preting, and understanding the underlying physicochem-68 ical mechanisms of the observed physical phenomena of 69 materials. Scientifically, applying a data-driven approach 70 to extracting knowledge from existing complicated mate-71 rial data can accelerate the process of describing, inter-72 preting, and understanding the physicochemical mech-73 anisms underlying the observed physical phenomena of accelerated material discovery," npj Computational Materials 5, 18

materials. This reduces the time required for material development. Hence, to be effectively applied to materials science, data-driven approaches that are interpretable and understandable to humans must be developed.

One of the most intuitive and interpretable data-driven approaches for humans is analogy-based inductive reasoning, which infers the properties of a new instance using the information of the observed instances that are most similar to it 2-5 . By applying analogy-based models, we can easily explain the reasoning process behind the predictions and reveal the physicochemical mechanisms rationalizing the observations 6,7 . Materials scientists have resolved different problems in materials science by systematizing information about analogies in composition or structure between materials that exhibit similar physicochemical properties [8][9][10][11] .

Especially, in a discipline based on fundamental principles, such as condensed matter physics, it is essential to elucidate the physical mechanisms and which materials are manifested through each of these physical mechanisms. However, despite several new materials and superior properties having been discovered, it is still difficult to appropriately quantify the similarities between materials to elucidate the underlying physicochemical mechanisms of these properties. Furthermore, this difficulty arises from the fact that the mechanisms of materials' properties are typically interpreted in terms of physicochemical concepts based on relative criteria.

The phenomenon of superconductivity in materials, which originates from the instability of metals, is a wellknown example of the above difficulty. One of the most successful theories that describe the microscopic mechanisms is the Bardeen-Cooper-Schrieffer (BCS) theory for superconductivity 12 , the origin of which is electronphonon interactions. However, there also exist other mechanisms. For example, one of the most plausive origins of superconductivity in the high-T C cuprates is electron-electron interactions. Nevertheless, it is not easy to achieve a consensus of classifying the superconducting mechanism of materials among researchers as the origins. Although the emergence of superconductivity is basically due to the instability in the metallic phase, it is not easy to achieve the consensus because both the mentioned and other mechanisms can contribute cooperatively in increasing the T C value, for example. Although it is challenging to classify individual materials when considering phenomena that cause such a situation, it is expected that the underlying physical mechanisms can be discovered if we can inductively quantify the similarities between the materials of interest and group similar materials using all observation data. Incidentally, inductive reasoning with inefficient similarity assessment can lead to misidentification of outliers 13 and difficulty in explaining the underlying physicochemical mechanisms of datasets using single models. Therefore, regarding predefined material descriptors, an exhaustive examination of all possible hypotheses about the unknown physicochemical mecha-nisms is necessary to assess the similarity between the does not provide any information about the simi-64 larity between (x i , y i ) and (x j , y j ).

65

To quantitatively evaluate whether (x i , y i ) can be con- In other words, the interval that determines the proba-81 bility that a data instance (x i , y i ) belongs to f r is α σ xi , 82 and if the data instance falls outside this interval, it is 83 determined that it does not belong to f r . By increasing 84 or decreasing the value of the parameter α, the condition for determining whether a data instance (x i , y i ) belongs to f r is relaxed or tightened, making p(O i |f r ) larger or smaller, respectively. Optimal values of α can be chosen using statistical criteria and appropriate validation methods; however, we set α = 2 for all experiments in this work to reduce model complexity. We consider p(O i |f r ) as the probability that (x i , y i ) is generated by f r , and 1 illustrates the process of modeling the probability p(O i |f r ).

74 p(O i |f r ) = 1 if ∆ i ≤ 3 σ 2 × +∞ ∆i-3 σ N (u|0, α σ xi ) du otherwise , (1) where ∆ i = |y i -ŷi | = |y i -f r (x i )| is the deviation
p(O i |f r ) = 1 -p(O i |f r ) is the probability that (x i , y i ) is not generated by f r . Supplementary Figure
Events where (x i , y i ) or (x j , y j ) is generated by the function f r are independent events. Therefore, considering the function f r , we can evaluate the joint probabilities of observing:

• Both data instances:

p(O i , O j |f r ) = p(O i |f r ) × p(O j |f r );
(2)

• Only one of the data instances:

p(O i , O j |f r ) + p(O i , O j |f r ) = p(O i |f r ) × p(O j |f r ) + p(O i |f r ) × p(O j |f r ); (3)
• Neither of the data instances:

p(O i , O j |f r ) = p(O i |f r ) × p(O j |f r ) = 1 -p(O i , O j |f r ) -p(O i , O j |f r ) -p(O i , O j |f r ). (4)

B. Modeling evidence by mass functions

Considering the Dempster-Shafer theory framework 16 , we begin by defining the frame of discernment Ω. Let Ω = {s, ds} be the universal set representing the similarity states of any two data instances (x i , y i ) and (x j , y j ).

s and ds denote the similarity and dissimilarity states between the two data instances, respectively.

According to the Dempster-Shafer theory, the evidence of the similarity states between these two data instances is represented by a mass function m i,j (or a basic probability assignment) 16 . This assigns probability masses to all the nonempty subsets of Ω (X = {{s}, {ds}, {s, ds}}).

It is defined as follows:

m i,j : X → [0, 1] with E∈X m(E) = 1. (5)
The masses assigned to {s} and {ds} reflect the degrees of belief exactly committed to the evidence to support the similarity and dissimilarity between (x i , y i ) and (x j , y j ),

respectively. The weight assigned to {s, ds} expresses the degree of belief that the evidence provides no information about the similarity (or dissimilarity) between (x i , y i ) and (x j , y j ).

Therefore, the mass function m i,j fr , which models a piece of evidence of the similarity between (x i , y i ) and (x j , y j ) collected from f r , is defined as follows:

m i,j fr ({s}) = p(O i , O j |f r ) γ i,j (6)
m i,j fr ({ds}) = p(O i , O j |f r ) + p(O i , O j |f r ) γ i,j (7)
m i,j fr ({s, ds}) = 1 -

1 γ i,j + p(O i , O j |f r ) γ i,j , (8)
where γ i,j = (e σ ∆y +1)×( Assuming that we can collect q pieces of evidence from 55 F r = {f 1 r , . . . , f q r }, a set of q reference functions is gen-

σx i σ +1)×( σx j σ +1)
64 m i,j {f l r ,f k r } (E) = (m i,j f l r ⊕ m i,j f k r )(E) = Et∩Ev=E m i,j f l r (E t ) × m i,j f k r (E v ) 1 - Et∩Ev=∅ m i,j f l r (E t ) × m i,j f k r (E v ) , (9)
where E, E t , and E v are nonempty subsets of Ω. Demp-65 ster's rule is commutative and associative.

66

Based on Dempster's rule, the obtained mass functions 67 corresponding to the q pieces of evidence are combined 68 to assign the final mass m i,j Fr as follows:

69 m i,j Fr (E) = m i,j f 1 r ⊕ m i,j f 2 r ⊕ • • • ⊕ m i,j f q r (E). (10)
We perform similar analyses for all pairs of data in- between them. Thereafter, the obtained matrix is applied for further unsupervised data mining analysis, such as clustering or data visualization.

III. EXPERIMENTS AND RESULTS

In this section, we perform three experiments to demonstrate the application of our similarity measurement in dealing with outliers and data generated by multiple mechanisms when designing materials descriptors.

We apply the eRSM to measure similarities between magnetic of three datasets for detecting subgroups of ma-

A. Datasets

The details of the datasets investigated in this study are as follows.

• The remaining alloys do not show apparent similarities with alloys in groups G T C 1 and G T C 2 ; thus, they are not assigned to any group.

(b) (a) 𝐺 ! "#$ 𝐺 % "#$ Outlier 𝐺 ! "#$ 𝐺 % "#$ Outlier Model 𝐺 ! "#$ Model 𝐺 % "#$ (c) 𝐺 ! & ! 𝐺 % & ! Outlier 𝐺 ! &! 𝐺 % &! Outlier Model 𝐺 ! &! Model 𝐺 % &! Model Outlier (e) (d) (f)
Following the same analysis procedure as in the previous section, we trained regression models for Curie temperature using data from each of the three groups Co-X when focusing on the magnetization mechanisms.

G T C 1 , G T C 2 ,

  59materials. Furthermore, similarity measures are usually 60 context-dependent. Because the context changes, the 61 similarity measure must be modified to adequately cap-62 ture the phenomena under study14,15 . Thus, a quanti-63 tative measure of similarity needs to consider the uncer-64 tainty arising from the context or the measurement itself, 65 especially in situations where material data are often in-66 sufficient and heavily biased. Moreover, similarities from 67 different contexts may not be directly comparable in the 68 integration to draw conclusions about the similarity be-69 tween materials. These reasons make it challenging to 70 apply data-driven approaches to materials science. 71 To overcome such issues and efficiently extract knowl-72 edge from the data, we propose a new approach that 73 shifts from measuring the similarity between materials 74 to quantitatively measure the confidence in their simi-75 larities. We adopt the Dempster-Shafer theory 16-18 , re-76 ferred to as the evidence theory, to develop an eviden-77 tial regression-based similarity measurement (eRSM) for 78 detecting subgroups of materials such that leaned mod-79 els from the subgroups show high correlations between 80 descriptors and the target property of the constituent 81 materials. Further analysis of models describing the sub-82 groups provide valuable information to extract, interpret, 83 and understand physical mechanisms. The Dempster-84 Shafer theory can be regarded as a generalization of the 85 Bayesian approach for solving the problem of incomplete 86 and insufficient information. Moreover, it is suitable for 87 solving material data problems 19,20 . The measure of sim-88 ilarity here refers to whether the observed physical prop-89 erties of the materials under study are described using 90 the same hidden mechanism that has not yet been re-91 vealed. In other words, we consider any pair of materials 92 (in the dataset) as similar if their physical properties can 93 be described by the same hidden mechanism; otherwise, 94 the pair of materials is considered dissimilar. We then 95 first generate numerous hypothetical mechanisms by ran-96 domly choosing subsets of data instances and construct-97 ing regression models for each subset. Each regression 98 model is considered a source of evidence of the similari-99 ties between materials. Thereafter, the Dempster-Shafer 100 theory 16-18 , which has a foundation for modeling and 101 combining the uncertainty of evidence, is applied to inte-102 grate the collected pieces of evidence to draw conclusions 103 about the similarities between materials. The eRSM con-104 sists of three main steps as follows: 105 1. Collect sources of evidence: Hypothetical mecha-106 nisms are collected from a dataset by applying re-107 gression analysis with single or mixture models and 108 are used as sources of evidence to rationalize the 109 similarity states of materials.

110 2 .FIG. 1 .

 21 FIG.1. Illustrative figures of the three possible similarity states between two data instances (blue circles), including similar (a), dissimilar (b), and uncertain (c), considering a referential regression model fr (black line). The gray region is the interval that determines whether a data instance can be considered to have been generated by regression model fr.

56

  have been generated by the function f r (Fig.1 a).

57••

  Dissimilar: Only one of the data instances can be 58 considered to have been generated by the function 59 f r (Fig. 1 b).60 Uncertain: Neither of the data instances can be 61 considered to have been generated by the function 62 f r (Fig. 1 c). The uncertain state indicates that f r 63

66

  sidered to have been generated by the regression function 67 f r , we use the likelihood p(O i |f r ), the probability of event 68 O i that a data instance (x i , y i ) is observed, considering 69 f r . The likelihood p(O i |f r ) is modeled using a normal 70 distribution with mean and standard deviation depend-71 ing on the predicted target value ŷi = f r (x i ) and the cor-72 responding standard error σ xi by f r , respectively. This 73 is expressed as:

75

  from the true to the predicted target values of data in-76 stance i using f r , and σ is the average of the predictive 77 standard error of all the data instances in D ref . α is 78 the hyperparameter used to adjust the condition that re-79 stricts the data instances belonging to the function f r . 80

56

  erated from D to evaluate the similarity between a pair 57 of data instances with indices i and j. According to the 58 Dempster-Shafer theory framework, any two pieces of ev-59 idence collected from the reference functions f l r and f k r , 60 which are modeled by the corresponding mass functions 61 m i,j f l r and m i,j f k r , respectively, can be combined using the 62 Dempster rule of combination to assign the joint mass 63 m i,j {f l r ,f k r } to each nonempty subset E of Ω as follows:

  70stances in D to construct symmetric matrices M com-71 prising the similarities (M [i, j] = M [j, i] = m i,jFr ({s}))

terials: 1 )

 1 The experimentally observed Curie temperature dataset (D binary ) of binary alloys for transitioning rare earth metals, 2) Dataset of calculated magnetization of quaternary high-entropy alloys (D M ag quaternary ), and 3) Dataset of calculated Curie temperature of quaternary high-entropy alloys (D T C quaternary ). Note that the datasets D M ag quaternary and D T C quaternary contain similar alloys and differ only in the target properties.

Figure 2 7 30 tering analysis results. 31 To

 23031 FIG. 2. (a) Observed and predicted Curie temperature of alloys in the dataset D binary using model generated for nickel (Ni), iron (Fe), and manganese (Mn)-based alloys. The blue and gray points indicate cobalt (Co)-based alloys and alloys of other transition metals (Ni, Fe, Mn), respectively. (b) Prediction error of Co-based alloys when excluding (top) or including (bottom) data of other Co-based alloys to the training dataset.

30 T 31 G M ag 1 and G M ag 2 ,

 303112 FIG. 5. (a,d) Heatmaps illustrating the similarity matrices M M ag quaternary (a) and M T C quaternary (d) extracted from datasets D M ag quaternary and D T C quaternary , focusing on mechanisms of magnetization and TC , respectively. (b,e) The confusion matrix summarizes the differences between the magnetization (b) or TC (e) mechanisms of alloys in extracted groups. (c,f) Visualization of quaternary alloys in the two-dimensional embedding spaces constructed by applying the T-distributed Stochastic Neighbor Embedding (t-SNE) to M M ag quaternary (c) and M T C quaternary (f). Red, blue, and gray contours indicate gaussian models ĜMag 1

FIG. 7 ., G M ag 2 ,Figure 7 , G M ag 2 ,

 7272 FIG. 7. Proportions of quaternary alloys containing Fe or Co in group G M ag 1

173

  figuration, the T C can be estimated from the spin-spin 35

  ). The gray region is the interval that determines whether a data instance can be considered to have been generated by regression model fr. , y i ) and (x j , y j ) in D eval .

				36	sidering D ref , we can generate a single or multiple ref-
				37	erence functions f r : R n → R using a Gaussian process
				38	(GP) 21 or a mixture of Gaussian processes (MGP) 22 , re-
				39	spectively. This study applies GP-or MGP-based models
				40	instead of other nonlinear regression models such as ker-
				41	nel ridge regression 23 , random forest regression 24 , or arti-
				42	ficial neural networks 25 because GP or MGP can quantify
				43	the uncertainty of its prediction without introducing any
				44	other statistical validation. The sampling ratios of D ref
				45	from D are fixed at 0.3 and 0.7 for the experiments with
				46	GP and MGP, respectively. Each reference function f r
				47	is considered as a source to provide pieces of evidence
				for the similarity between (x i 48
				49	The function f r is not used to provide any information
				50	about the similarities between the data instances in D ref
				51	or between a data instance in D ref and a data instance
	1 2	combination is used to integrate the pieces of the evidence.	52 53 54	in D eval . This is to exclude self-evaluation to ensure the objectivity of the evidence. Regarding a reference func-tion f r , we consider the state of the similarity between
	3	The steps of the eRSM are explained in detail in Sec-	55	(x i , y i ) and (x j , y j ) as:
	4 5	tion II. Regarding the framework of the evidence theory, the essential contributions of the eRSM are collecting		• Similar: Both data instances can be considered to
	6	sources of evidence about the similarities between mate-
	7	rials from datasets and designing suitable mass functions
	8	to model the pieces of evidence rationally. The effective-
	9	ness of obtained similarities using the eRSM for subdi-
	10	viding alloys from datasets into homogenous subgroups
	11	is supported by experiments on 1) a dataset of binary
	12	alloys with their Curie temperature as a target property
	13	(Section III B); and 2) two dataset of quaternary alloys
	14	with their magnetization (Section III C) and Curie tem-
	15	perature (Section III D) as the target properties. Further
	16	analysis of the detected subgroups to interpret the under-
	17	lying physical mechanisms is shown in Section III E
	18	II. METHODOLOGY
	19	We consider a dataset D consisting of p data in-
	20	stances. We assume that a data instance with index
	21	i in D is described by n predefined descriptors and
	22	is represented by an n-dimensional numerical vector,
		x i = x 1 i , x 2 i , . . . , x n i	∈ R n . The target property of
	24	the data instance x i is y i ∈ R. Thereafter, the dataset
	25	D = {(x 1 , y 1 ), (x 2 , y 2 ) . . . (x p , y p )} is represented using
	26	a (p × (n + 1)) matrix. In this study, we consider that
	27	D may contain pairs of data instances x i and x j , where
	28	x i ≈ x j ; however, the value of y i is far from y j .
	29	A. Collecting sources of similarity evidence
	30	We perform random subset sampling of the data in-
	31	stances without replacement to collect a large amount of
	32	evidence of the similarity between pairs of data instances
	33	in D. Considering each sample, we obtain two datasets:
		the reference dataset, D ref , and the evaluation dataset,

  is a discount-

	41
	ing factor 16,26 , which describes the unreliability of evi-

42

dence about the similarity between (x i , y i ) and (x j , y j ) 43 collected from a source of evidence f r . ∆ y is the varia-44 tion range of the target variable y in the dataset D. The 45 smaller σ is relative to ∆ y , the more reliable the learned 46 regression function f r is. Also, when σ xi and σ xj are 47 smaller than σ, f r can provide reliable evidence for the 48 relationship between (x i , y i ) and (x j , y j ). By contrast, 49 when σ xi and σ xj are large compared to σ, f r cannot pro-50 vide reliable evidence for the relationship between (x i , y i ) 51 and (x j , y j ). A detailed explanation of each component 52 in γ i,j is provided in Supplementary Section I. 53 C. Dempster's rule in combining evidence 54

DATA AVAILABILITY STATEMENT

12