David Ilcinkas
email: david.ilcinkas@labri.fr

Ahmed M Wade
email: awade@ept.sn

Exploration of Dynamic Cactuses with Sub-logarithmic Overhead

Keywords: Exploration, Dynamic graphs, Mobile agent, Connectivity over time

. In this paper, we consider the same problem and we suppose that the underlying graph is a cactus graph (a connected graph in which any two simple cycles have at most one vertex in common).

We propose an algorithm that allows the agent to explore these dynamic graphs in at most O(n log n log log n ) time units. We show that the lower bound of the algorithm is Ω (n log n (log log n) 2 ) time units (for infinitely many n).

Introduction

The exploration of a graph by a (physical or software) mobile agent consists of visiting at least once each of the vertices of the graph, starting from a given vertex of the graph. In practice, many concrete systems can be modeled by graphs. This is what makes the use of graphs very versatile. For example, graphs can be used to model pipeline systems, underground tunnels, roads networks, etc. In this case, the exploration is performed by a mobile robot. Graphs can also be used to model more abstract environments such as computer networks. In this case, the mobile entities used to explore these environments are software agents, that is to say a program running in these environments.

This fundamental problem in distributed computing by mobile agents has been extensively studied since the seminal paper by Claude Shannon [START_REF] Shannon | Presentation of a maze-solving machine[END_REF]. However, the majority of the work concerns static graphs, while new generations of interconnected environments tend to be extremely dynamic. To take into account the dynamism of these extreme environments, for a decade, researchers have begun to model these dynamic environments with dynamic graphs. Several models have been developed. The interested reader may find in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] a comprehensive overview of the different models and studies of dynamic graphs (see also [START_REF] Kuhn | Dynamic networks: models and algorithms[END_REF]).

One of the first developed models, and also one of the most classical, is the model of evolving graphs [START_REF] Ferreira | Building a Reference Combinatorial Model for Dynamic Networks: Initial Results in Evolving Graphs[END_REF]. For simplicity, given a static graph G, called underlying graph, an evolving graph G based on G is a (possibly infinite) sequence of (spanning but not necessarily connected) subgraphs of G (see Section 2 for the precise definitions). This model is particularly suited for modeling synchronous dynamic networks.

In this paper, we study the problem of exploration of dynamic graphs considering the model of constantly connected evolving graphs. An evolving graph G = (G 1 , G 2 , . . . ) is called constantly connected if each graph G i which composes it is connected. This class of graphs was used in [START_REF] Dell | Information dissemination in highly dynamic graphs[END_REF] to study the problem of information dissemination. In 2010, Kuhn, Lynch and Oshman [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] generalize this class of dynamic graphs by introducing the notion of T -interval-connectivity. Roughly speaking, given an integer T ≥ 1, a dynamic graph is T -interval-connected if for any window of T time units, there is a connected spanning subgraph that is stable throughout the period. (The notion of constant connectivity is equivalent to the notion of 1-intervalconnectivity.) This new concept, which captures the connection stability over time, allows to derive interesting results: the T -interval-connectivity allows a savings of a factor about Θ (T ) on the number of messages necessary and sufficient to achieve a complete exchange of information between all vertices [START_REF] Dutta | On the Complexity of Information Spreading in Dynamic Networks[END_REF][START_REF] Kuhn | Distributed computation in dynamic networks[END_REF].

During these last few years, several studies consider constantly connected dynamic graphs where the underlying graph of the dynamic graph is a ring of n vertices.

The problem of exploration with termination by a mobile agent is considered in [START_REF] Di Luna | Distributed exploration of dynamic rings[END_REF][START_REF] Gotoh | Masuzawa Dynamic Ring Exploration with (H,S) View In Algorithms[END_REF][START_REF] Ilcinkas | Exploration of the T -Interval-Connected Dynamic Graphs: the Case of the Ring[END_REF]. If the dynamics of the graph is known, [START_REF] Ilcinkas | Exploration of the T -Interval-Connected Dynamic Graphs: the Case of the Ring[END_REF] shows that a single agent can solve the problem, and 2n -3 time units are necessary and sufficient. If the dynamics is not known in advance, [START_REF] Di Luna | Distributed exploration of dynamic rings[END_REF] shows that two agents knowing an upper bound N on the number of vertices can solve the problem, and (3N -6) time units are sufficient if all agents are active at each time step, and O(N 2 ) moves are sufficient if a subset of the agents might be active at each time step. The case when the agent has partial information about network changes is considered in [START_REF] Gotoh | Masuzawa Dynamic Ring Exploration with (H,S) View In Algorithms[END_REF]. More precisely, the authors study the exploration time for a single agent which knows the dynamics of the graph for the next S steps in its H-hop neighborhood, for given parameters S and H.

The problem of perpetual exploration is considered in [START_REF] Bournat | Computability of Perpetual Exploration in Highly Dynamic Rings[END_REF][START_REF] Gotoh | Masuzawa and Nicola Santoro Tight Bounds on Distributed Exploration of Temporal Graphs In 23[END_REF]. In [START_REF] Bournat | Computability of Perpetual Exploration in Highly Dynamic Rings[END_REF], the authors consider that all agents are active at each time step and show that to solve the problem, one agent is sufficient in the rings of size two1 , two agents are sufficient in the rings of size three, and three agents are sufficient for all other rings. In [START_REF] Gotoh | Masuzawa and Nicola Santoro Tight Bounds on Distributed Exploration of Temporal Graphs In 23[END_REF] the authors consider time varying graphs whose topology is arbitrary and unknown to the agents and investigates the number of agents that are necessary and sufficient to explore such graphs. In addition to the problem of exploration, the problem of dispersion of a team of agents [START_REF] Agarwalla | Deterministic Dispersion of Mobile Robots in Dynamic Rings[END_REF], gathering [START_REF] Di Luna | Gathering in dynamic rings[END_REF] and patrolling by a team of agents [START_REF] Das | Patrolling on Dynamic Ring Networks[END_REF] are studied, considering constantly connected dynamic graphs based on the ring.

Besides, several papers focus on the complexity of computing the optimal exploration time of a dynamic graph given as (a centralized) input, in a similar manner as in the Traveling Salesman Problem for static graphs. In the dynamic case, the problem is called Temporal Graph Exploration Problem [START_REF] Bodlaender | On exploring always-connected temporal graphs of small pathwidth In Information Processing Letters[END_REF][START_REF] Erlebach | On Temporal Graph Exploration[END_REF][START_REF] Michail | Traveling salesman problems in temporal graphs[END_REF] or Dynamic Map Visitation Problem [START_REF] Aaron | DMVP: Foremost Waypoint Coverage of Time-Varying Graphs[END_REF][START_REF] Aaron | Multi-Robot Foremost Coverage of Time-Varying Graphs[END_REF]. In [START_REF] Aaron | Multi-Robot Foremost Coverage of Time-Varying Graphs[END_REF], the case of several agents is considered, while [START_REF] Bodlaender | On exploring always-connected temporal graphs of small pathwidth In Information Processing Letters[END_REF][START_REF] Erlebach | On Temporal Graph Exploration[END_REF][START_REF] Michail | Traveling salesman problems in temporal graphs[END_REF] and most of [START_REF] Aaron | DMVP: Foremost Waypoint Coverage of Time-Varying Graphs[END_REF] consider the case of a single agent. The problem is shown to be NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected [START_REF] Bodlaender | On exploring always-connected temporal graphs of small pathwidth In Information Processing Letters[END_REF]. In the other papers, several polynomial-time algorithms are given, either exact algorithms for specific graph classes, or approximation algorithms for the general cases. In particular, [START_REF] Aaron | DMVP: Foremost Waypoint Coverage of Time-Varying Graphs[END_REF] gives an O(n 2 ) algorithm to compute the optimal exploration time of a given 1-interval-connected dynamic graph based on the n-vertex ring. Inapproximability results for the general case are given in [START_REF] Erlebach | On Temporal Graph Exploration[END_REF][START_REF] Michail | Traveling salesman problems in temporal graphs[END_REF].

It turns out that the problem of exploration is much more complex in dynamic graphs than in static graphs. Indeed, let us consider for example the scenario where the dynamic graph is known. The worst-case exploration time of n-vertex static graphs is clearly in Θ (n) (worst case 2n -3). On the other hand, the worst-case exploration time of n-vertex (1-interval-connected) dynamic graphs remains largely unknown.

In [START_REF] Erlebach | On Temporal Graph Exploration[END_REF] the authors give a worst-case lower bound in Ω (n 2 ) for general graphs and Ω (n log n) for degree-bounded graphs. An upper bound in O(d log d • n 2 log n ) for degreebounded graphs is given in [START_REF] Erlebach | Faster Exploration of Degree-Bounded Temporal Graphs[END_REF].

The goal of this paper is to extend the results obtained in [START_REF] Ilcinkas | Exploration of the T -Interval-Connected Dynamic Graphs: the Case of the Ring[END_REF] to larger families of underlying graphs. Unfortunately, the problem turns out to be much more difficult than it seems. We will see that proving that any dynamic graph based on a tree of cycles (a cactus) can be explored in time O(n) is already a challenging problem.

Our results. We will first give two exploration methods that are efficient for exploring a very large set of constantly connected dynamic graphs based on a cactus, when the agent knows the dynamics of the graph. We will then combine these two exploration methods. We show that the combination of the two methods yields an algorithm that explores all constantly connected dynamic graphs based on a cactus of n vertices in O(n log n log log n ) time units, and we derive a lower bound of Ω (n log n (log log n) 2 ) time units for the algorithm (for infinitely many n).

Preliminaries

This section provides precise definitions of the concepts and models discussed informally earlier. We also give some previous results from the literature on the problem studied in this paper.

Definition 1 (Dynamic graph) A dynamic graph is a pair G = (V, E ), where V is a static set of n vertices, and E is a function which maps every integer i ≥ 0 to a set

E (i) of undirected edges on V . Definition 2 (Underlying graph) Given a dynamic graph G = (V, E ), the static graph G = (V, ∞ i=0 E (i)
) is called the underlying graph of G . Conversely, the dynamic graph G is said to be based on the static graph G.

In this paper, we consider dynamic graphs based on a cactus of size n. We also assume that the agent knows the dynamics of the graph, that is to say, the times of appearance and disappearance of the edges of the dynamic graph.

Definition 3 (Constant connectivity) A dynamic graph is called constantly connected if, for any integer i, the static graph

G i = (V, E (i)) is connected.
Definition 4 (Cactus) A cactus is a simple graph G = (V, E) in which two connected cycles have at most one vertex in common (see Figure 1). A mobile entity, called agent, operates on these dynamic graphs. The agent can traverse at most one edge per time unit. It may also stay at the current vertex (typically to wait for an incident edge to appear). We say that an agent explores the dynamic graph if and only if it visits all the vertices.

In this article, we will use the following results from the literature.

Theorem 1 [START_REF] Ilcinkas | Exploration of the T -Interval-Connected Dynamic Graphs: the Case of the Ring[END_REF] For every integers n ≥ 3 and t ≥ 0, and for every constantly connected dynamic graph based on a ring with n vertices, there exists a vertex v (t) such that an agent starting at time t on v (t) and going in the clockwise2 direction for n -1 time units will never be blocked by a missing edge, and thus will explore all vertices within those n -1 time units.

Sketch of proof.

Consider n virtual agents placed on the n vertices (one agent on each vertex). Make all agents move in the clockwise direction for n -1 time units from time t. Since at most one edge is removed at a time, it holds that, at each time, at most one such virtual agent is blocked at this time without having been blocked before.

Thus, one of the n virtual agents is never blocked during the n -1 time units, and the starting vertex of this agent is the vertex v (t) we are looking for.

Theorem 2 [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] For every constantly connected dynamic graph on n vertices, at most n -1 time units are sufficient for an agent to go from any vertex to any other vertex in the graph, when the agent knows the dynamics of the graph.

Sketch of proof. Let u be some arbitrary vertex of the dynamic graph. For any integer i ≥ 0, let V i be the set of vertices reachable from u in at most i time units. We have that V i V i+1 until V i contains all the vertices. Indeed, before all vertices are reachable, there exists a vertex not in V i which is neighbor of a vertex in V i , because the dynamic graph is constantly connected.

Theorem 3 [START_REF] Ilcinkas | Exploration of the T -Interval-Connected Dynamic Graphs: the Case of the Ring[END_REF] For every integer n ≥ 3 and for every constantly connected dynamic graph based on a ring with n vertices, there exists an agent (algorithm), EXPLORE-RING, exploring this dynamic graph in time at most 2n -2 time units. (The agent knows the dynamics of the graph).

Sketch of proof. The algorithm proceeds as follows. Go to vertex v (n-1) , whose existence is guaranteed by Theorem 1. This can be done in at most n -1 time units, by Theorem 2. At time n -1, go clockwise during n -1 time units to fully explore the ring, thanks to the properties of v (n-1) .

In this paper, we will only consider asymptotic exploration times. Since exploration of an n-vertex dynamic graph requires at least n -1 edge traversals, Theorem 2 implies that requiring the agent to return to the starting vertex can at most double the exploration time. Therefore we will in fact study in this paper the exploration with return problem.

To give a simpler analysis of our algorithms, we consider the tree representation of a cactus given in [START_REF] Burkard | A Linear Algorithm for the Pos/Neg-Weighted 1-Median Problem on a Cactus[END_REF]. For any given cactus, the set of all vertices V is partitioned into three subsets of vertices. Call C-vertices the vertices of degree 2 that belong to one and only one cycle, G-vertices the vertices that do not belong to any cycle, and H-vertices the other vertices (which belong to at least one cycle and have a degree at least 3), which we also call attachment vertices.

A subtree is a connected set consisting of H-vertices and G-vertices. A subtree is called maximal if the sets of H-vertices and G-vertices that it consists of cannot be extended. A graft is a maximal subtree that does not contain two H-vertices belonging to the same cycle. Finally, a block is a graft or a cycle.

It is not difficult to see that a cactus is formed by a set of blocks attached via H-vertices (see Figure 2.(a)). If we add an edge between the blocks and the H-vertices, we obtain the tree

T G = (V G , E G ) such that each element of V G is a block or an H-vertex. Figure 2.(b)
gives the tree representation of the cactus shown in Figures 1 and2.(a). We say that a cactus is rooted if the tree that represents it is rooted.

Given that constantly connected dynamic graphs based on trees (or grafts) are static and thus easy to explore, in this paper we consider cactuses that only consist of cycles and H-vertices. These cactuses will be called plump cactuses. Blocks are then always cycles, and we will use the term cycle in the sequel. In the following, we will assume that the cactus is rooted at the cycle where the agent starts exploration.

If the agent starts on an H-vertex, one of the cycles attached to the H-vertex will be the root cycle.

In this paper, we use the classical formalism of static trees. We will talk about degree, child, parent, height or depth of a cycle. Instead of subtree, we will rather use the term sub-cactus of a cactus C to denote a cactus C corresponding to a subtree in the rooted tree representation of C.

Chain method

In this section, we give a simple algorithm inspired by DFS to explore constantly connected dynamic graphs based on a plump cactus of n vertices. The principle of the algorithm is very simple. If the agent enters a cycle it has not visited yet, it visits it using the algorithm EXPLORE-RING for exploring dynamic graphs based on the ring (see Theorem 3), then passes to the attachment vertex of its closest unexplored child and explores it recursively. If all its children have already been explored and there is a cycle not yet explored, then it goes to its parent.

Algorithm 1 CHAIN-METHOD() GO-TO-THE-ATTACHMENT-VERTEX (with this child) 7: else 8:

GO-TO-THE-ATTACHMENT-VERTEX (with the parent) 9:

end if 10: end while Theorem 4 For any integer n ≥ 3, and for any constantly connected dynamic graph based on a plump cactus of n vertices, there is an agent, executing the algorithm CHAIN-METHOD, able to explore this dynamic graph in at most

∑ k i=1 (d i + 2)(n i -1)
time units, where n i is the size of the cycle i, d i its degree, and k the number of cycles of the cactus.

Proof An agent executing the algorithm CHAIN-METHOD pays on each cycle R n i of the cactus at most 2n i -2 time units to explore it (see Theorem 3). To switch to the attachment vertex of a child or the parent (if it has one), n i -1 time units are sufficient (see Theorem 2). As the degree of a cycle is equal to the number of its incident edges, then on each cycle R n i of the cactus, the agent pays at most

(d i + 2)(n i -1) time units.
The cactus is composed of k cycles, hence the agent pays at most

∑ k i=1 (d i + 2)(n i -1)
time units to explore the dynamic graph.

Note that if the degree of each cycle is constant, then the time to explore the dynamic graph using the CHAIN-METHOD is in O(n), where n is the size of the cactus. Figure 3 presents a plump cactus of size n in which exploration using the CHAIN-METHOD takes time Ω (n 2 ). Indeed, any algorithm exploring this graph has to explore the Ω (n) attached cycles of length 3. However, when the CHAIN-METHOD is used, the order of visit of these cycles is fixed and the adversary may choose the dynamicity of the graph such that going from one attached cycle to the next takes time Ω (n). Hence the overall exploration time is Ω (n 2 ).

Star method

As we have seen in the previous section, the algorithm CHAIN-METHOD is not effective for exploring constantly connected dynamic graphs based on cactuses with cycles of large degree, because the order of visit of the sub-cactuses is fixed, which makes the algorithm spend a lot of time to go from one sub-cactus to the next. On the contrary, the algorithm STAR-METHOD presented in this section focuses on reducing these transit times on the root cycle (the cycle where the exploration starts) to the minimum. The idea is to visit the sub-cactuses while exploring the root cycle. Note that directly using the algorithm EXPLORE-RING on the root cycle does not work, because when returning to the attachment vertex after exploring a sub-cactus, the agent cannot continue the exploration according to the algorithm EXPLORE-RING on n 3

Fig. 3 Difficult graph for the CHAIN-METHOD.

the root cycle, as the dynamicity has changed on this cycle. To avoid this issue, the algorithm STAR-METHOD uses the algorithm EXPLORE-RING on a carefully chosen virtual dynamic cycle that takes into account both the dynamics of the root cycle and the time needed to recursively explore the sub-cactuses.

Theorem 5 For any integer n ≥ 3, and for any constantly connected dynamic graph based on a plump cactus C of n vertices, there is an agent, executing the algorithm STAR-METHOD, able to explore this dynamic graph in at most f S (C) = 3(n r -1) time

units if C is an n r -vertex cycle, or f S (C) = 3(n r -1) + ∑ i=1 f S (C i ) + max 1≤i≤ f S (C i )
time units otherwise, where n r is the size of the root cycle, ≥ 1 is the number of

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 C 1 C 2 C 3 n r f (C 1 ) f (C 2 ) f (C 3 ) n r H 2 H 1 H 3
Fig. 4 Correspondence between the dynamic graph based on C and the dynamic graph based on R n .

We use the fundamental properties behind EXPLORE-RING, namely Theorem 1 and 2, on respectively G and G , to obtain a traversal that efficiently explores the root cycle and the sub-cactuses altogether. More precisely, if t is the time after n r -

1 time units elapsed, let v (t) be the vertex of R n described in Theorem 1. If v (t)
does not correspond to a vertex of the root cycle C, then we set v as the H-vertex in C corresponding to the static subpath containing v (t) . Otherwise, v is simply the corresponding vertex in C.

Now let Agent B be the virtual agent, starting from the previously defined vertex v (t) , that goes in the clockwise direction in G without being blocked for n -1 time units (by Theorem 1). We define the Agent A following the STAR-METHOD as follows.

First Agent A uses n r -1 time units to reach the previously defined vertex v on C. This is possible thanks to the property from Theorem 2. Now, whenever the (virtual) Agent B stays on a subpath P corresponding to some sub-cactus C i for at least f S (C i ) consecutive time units, Agent A uses this time to recursively explore the sub-cactus C i . If, after completing this exploration, Agent B is still lying on P, then Agent A simply waits on the attachment vertex. Whenever Agent B lies on the part corresponding to the root cycle (that is outside of the added subpaths), Agent A behaves exactly as Agent B.

This simulation of agent B on G takes at most n -1 = (n r -1)

+ ∑ i=1 f S (C i )
time units. By construction, the root cycle and all sub-cactuses are explored, except for possibly one sub-cactus C i , if the agent B starts (and ends) inside the static path corresponding to C i . In this case, the agent

A uses at most f S (C i ) ≤ max 1≤ j≤ f S (C j )
additional time units to explore C i . Finally, in any case, the agent returns to the start-ing vertex, using at most n r -1 time units. Overall, this can be done in f S (C) = 3(n r -1) + ∑ i=1 f S (C i ) + max 1≤i≤ f S (C i ) time units, which concludes the proof of the theorem.

If the height of the rooted tree of the cactus is constant, then the time to explore the dynamic graph using the STAR-METHOD is O(n) time units, where n is the size of the cactus. However, Figure 5 presents a plump cactus of size n in which exploration using the STAR-METHOD may take 2 Ω (n) n time units for a specific choice of missing edges at each time. Indeed, at each step of the induction, there is only one sub-cactus, and its cost is paid twice, once in the sum, and once in the max (cf. the formula in Theorem 5). The cycle of length n/2 to the right needs exploration time Ω (n). Then, recursively, each additional cycle of size 4 on its left will introduce a multiplicative factor of 2 in the recursive cost of the sub-cactus. As the number of cycles of size 4

is Ω (n), the overall exploration time is 2 Ω (n) n.

Starting vertex n 2

Fig. 5 Difficult graph for the STAR-METHOD.

Mixed method

In a plump cactus C with a root cycle of size n r and with sub-cactuses C 1 , . . . ,C , the recursive exploration time is

f C (C) = 3(n r -1) + ∑ i=1 f C (C i ) + • (n r -1)
for the algorithm CHAIN-METHOD, and f S (C) = 3(n r -1)

+ ∑ i=1 f S (C i ) + max 1≤i≤ f S (C i )
for the algorithm STAR-METHOD.

Because both methods presented above may have alone a large exploration time, we introduce in this section a combination of both methods, that is to say, on some sub-cactuses the agent will use the algorithm STAR-METHOD to explore them, and on the remaining sub-cactuses it will use the algorithm CHAIN-METHOD. The algorithm MIXED-METHOD is recursively defined as follows, with a cost function f M .

If the cactus is an n-vertex ring, then the agent uses the algorithm EXPLORE-RING (which is in fact what both methods do), with a cost of at most f M (C) = 3(n -1).

Otherwise, let n r be the number of vertices of the root cycle, and let C 1 , . . . ,C be its sub-cactuses, with ≥ 1. Assume without loss of generality that the sub-cactuses C 1 , . . . ,C are ranked in descending order of their exploration cost f M (C i ). The agent uses the algorithm CHAIN-METHOD for the k first sub-cactuses, and the algorithm STAR-METHOD for the other sub-cactuses, for a well-chosen k.

More precisely, for each sub-cactus C i , with 1 ≤ i ≤ k, the agent goes to the attachment vertex of C i in at most n r -1 time units (Theorem 2), and explores C i recursively using the algorithm MIXED-METHOD. Then it explores altogether what remains of the cactus (the root cycle and the cactuses C i , for i > k) similarly as in the algorithm STAR-METHOD. The only difference is that the recursive costs f M (C i ) are used to construct the virtual ring instead of the costs f S (C i ). As a consequence, the sub-cactuses are recursively explored using the algorithm MIXED-METHOD instead of the algorithm STAR-METHOD.

The resulting cost is then

∑ k i=1 n r -1 + f M (C i ) + 3(n r -1) + ∑ i=k+1 f M (C i ) + max k+1≤i≤ f M (C i ) .
Using the fact that the costs f M (C i ) are decreasing, the preced-

ing bound becomes 3(n r -1) + ∑ i=1 f M (C i ) + k • (n r -1) + f M (C k+1
) . 3 The algorithm MIXED-METHOD chooses k such as to minimize the additional cost k • (n r -

1)+ f M (C k+1 ).
To summarize, the exploration cost of the algorithm MIXED-METHOD

is f M (C) = 3(n r -1) + ∑ i=1 f M (C i ) + min 1≤k≤ (k • (n r -1) + f M (C k+1 )).

Upper bound for the algorithm MIXED-METHOD

In this section, we give an upper bound on the complexity of the algorithm MIXED-

METHOD. The term k • (n r -1) + f M (C k+1
) is a priori not monotone with respect to k. Therefore, it is not clear how to handle the min in the formula defining the function f M . To circumvent this issue, we study a variant of the algorithm MIXED-METHOD which chooses k more consistently.

+ ∑ i=1 f E (C i ) + 2c(n r -1) + f E (C 2c+1
). Among the first 2c sub-cactuses, there are at least c sub-cactuses whose number of vertices is at most n/c, where n is the total number of vertices in C. Also, all these sub-cactuses have a cost larger than

f E (C 2c+1 ).
It is therefore possible to charge the additional cost f E (C 2c+1 ) to these sub-cactuses. We obtain the upper bound

f E (C) ≤ 3(n r -1) + ∑ i=1 f E (C i ) + 2c(n r - 1) + 1 c ∑ |C i |≤ n c f E (C i ).
Differently speaking, there is a multiplicative factor 1+ Using the fact that lim

(C d,i-1 ) is j • t d,i-1 .
Therefore, the additional cost does not depend on k and is always equal to d •t d,i-1 . In other words, the cactus is constructed in such a way that all the algorithms CHAIN-METHOD, STAR-METHOD, and MIXED-METHOD have the same exploration cost.

Therefore, the exploration cost f

M (C d,i ) of C d,i is t d,i = 3(r d,i -1) + ∑ d j=1 ( j •t d,i-1 ) + d • t d,i-1 = (3 + d(d + 1)/2 + d) • t d,i-1 = ((d 2 + 3d + 6)/2) • t d,i-1 . r d,i sub d (C d,i-1 ) sub 1 (C d,i-1 ) sub 2 (C d,i-1 ) H 2 H d H 1 Fig. 6 Inductive construction of the cactus C d,i .
To simplify the notation, we now remove the first index d. Also, let α = (d 2 + 3d + 6)/2) and β = d(d + 1)/2. To summarize, we have

t 0 = d r 0 = (d + 3)/3 m 0 = (d + 3)/3 and, for 1 ≤ i ≤ h, t i = α • t i-1 r i = t i-1 + 1 m i = r i + β • m i-1 .
Solving the recurrences and setting γ = α/β , we obtain

t h = α h • t 0 r h = α h-1 • t 0 + 1 m h = β h • m 0 + h ∑ i=1 β h-i • r i = β h • m 0 + h ∑ i=1 (α i-1 • t 0 + 1)β h-i = β h • m 0 + t 0 • h-1 ∑ i=0 α i β h-1-i + h-1 ∑ i=0 β h-1-i = β h • m 0 + β h -1 β -1 + t 0 • β h-1 • γ h -1 γ -1 .
We now prove that the last term is somehow predominant. Indeed, we have

β h • m 0 + β h -1 β -1 t 0 • β h-1 • γ h -1 γ-1 ≤ 2β • m 0 t 0 • γ -1 γ h -1 ≤ β • γ -1 γ h -1 .
Besides, we have

γ = d 2 + 3d + 6 d 2 + d = 1 + 2d + 6 d(d + 1) = 1 + 2 d + 4 d(d + 1)
.

Plugging the last equation into the previous one, we obtain

β h • m 0 + β h -1 β -1 t 0 • β h-1 • γ h -1 γ-1 ≤ β • 2 d + 4 d(d+1) (1 + 2 d + 4 d(d+1) ) h -1 ≤ β • 3 d (1 + 2 d ) d 2 2h d -1 ≤ 3β d • 1 2 logd -1 ≤ 2 ,
where the penultimate inequality uses the fact that lim x→+∞ (1 + 1/x) x = e and the definition of h.

We are now ready to derive a lower bound on the exploration time t h . (log log n) 2 . Finally, we obtain t h ≥ 1 18 n log n (log log n) 2 , which concludes the proof of the theorem.

t h ≥ α h • t 0 3t 0 • β h-1 • γ h -1 γ-1 • m h ≥ α 3 • γ h-1 • γ -1 γ h -1 • m h ≥ α 3 • γ -1 γ • m h ≥ α 3d • m h ≥ d 6

Conclusion

In this paper, we studied the time complexity for exploring constantly connected dynamic graphs based on cactuses, under the assumption that the agent knows the dynamics of the graph. We gave an exploration algorithm for dynamic graphs that we called MIXED-METHOD, and we have shown that for exploring the whole class of constantly connected dynamic graphs based on cactuses of n vertices, with this algorithm, Ω (n log n (log log n) 2 ) time units are necessary (for infinitely many n), and O(n log n log log n ) time units are sufficient. This study opens several perspectives.

In the short term, it would be interesting to find a new method in order to obtain a better upper bound on the exploration time of dynamic graphs based on cactuses. At a second stage, an interesting question to investigate would be if T -intervalconnectivity (for T > 1) allows to save a significant factor in the exploration time of the cactuses. A natural further objective is to extend the family of underlying graphs.

Note that the families of underlying graphs considered so far (rings and cactuses)

have the property that at most one edge can be absent at a given time in every biconnected component. Studying families of underlying graphs that do not possess this property seems to be a challenging problem.

A further perspective is to consider the exploration problem of dynamic graphs using more than one agent, assuming standard models of communication between the agents. The objective would be to study whether dynamic graph exploration can be performed more efficiently by using more than one agent.

Fig. 1

 1 Fig. 1 Example of a cactus.

Fig. 2

 2 Fig. 2 Tree representation of a cactus.

  sub-cactuses attached to the root cycle, and f S (C i ) is the recursive exploration cost of the sub-cactus C i using the same algorithm.Proof Let C be a plump cactus, with n vertices, and let G be a constantly connected dynamic graph based on C. We prove the theorem by induction on the tree structure of the cactus. If C consists of a single ring (base case), then the algorithm STAR-METHOD simply applies the algorithm EXPLORE-RING and returns to the starting vertex, which proves the theorem in this case. Otherwise let n r be the size of the root cycle, and let C 1 ,C 2 , . . . ,C be the sub-cactuses attached to this root cycle. Moreover, for a proof by induction, we assume that the theorem holds for these sub-cactuses.Let f S be the recursive function defined in the statement of the theorem. The algorithm STAR-METHOD proceeds as follows. First, we introduce the following transformation of G into another dynamic graph G , based on a ring R n of size n . The dynamic graph G is constructed as follows. We retain the root cycle of C and the dynamics of the graph G on this cycle. We replace every H-vertex of C with two C-vertices linked by a sequence of static paths of length equal to the recursive cost of exploring each subtree attached to the H-vertex. More precisely, the lengths of the added paths are f S (C i ), for all the sub-cactuses C i attached to the H-vertex. Thus, we obtain a constantly connected dynamic graph based on a ring of size n (see Figure 4). The dynamic graph G is indeed constantly connected because we retain the dynamicity of the subgraph of G based on the root cycle of C, which itself respects the constant connectivity.

Theorem 6

 6 An agent executing the algorithm MIXED-METHOD requires at most O n log n log log n time units to explore any constantly connected dynamic graph based on a plump cactus of n vertices. Proof Fix an arbitrary constantly connected dynamic graph based on a plump cactus C of n vertices. In order to study the exploration cost of the algorithm MIXED-METHOD, we will discuss another algorithm, denoted EXPLORE-CACTUS, which is less efficient but easier to analyze. The upper bound obtained for this less efficient algorithm will also give us a valid upper bound for the MIXED-METHOD. The algorithm EXPLORE-CACTUS is defined as the algorithm MIXED-METHOD except that the number k of sub-cactuses on which it uses the algorithm CHAIN-METHOD is always min{ , 2c}, with c = log n log log n . Therefore, the exploration cost f E (C) of the algorithm EXPLORE-CACTUS in a plump cactus C having a root cycle of size n r and sub-cactuses C 1 , . . . ,C is at most 3(n r -1)

c→+∞ ( 1 + 1 cTheorem 7

 117 ) c = e, if we replace c with its value, we obtain the claimed bound. This concludes the proof of the theorem. 5.2 Lower bound for the algorithm MIXED-METHOD It turns out that the algorithm MIXED-METHOD does not explore all constantly connected dynamic graphs based on a cactus of size n in O(n) time units. We have the following theorem to prove it. For infinitely many n, there is a constantly connected dynamic graph based on a plump cactus of n vertices such that the exploration of the dynamic graph by an agent executing the algorithm MIXED-METHOD takes at least Ω n log n (log log n) 2 time units. Proof Let d be the triple of a sufficiently large power of 2 and let h = 1 2 d log d. We construct a particular rooted plump cactus C d for which the exploration cost f M (C d ) of the algorithm MIXED-METHOD is large, namely in Ω (d • |C d |). To do so, we use the following transformation. Given an integer i ≥ 1 and a cactus C, the cactus sub i (C) is defined as the cactus C in which all edges have been subdivided in i edges. Note that, in particular, sub 1 (C) = C. We now define C d via an inductive construction. More precisely, we define the cactuses C d,i , for 0 ≤ i ≤ h by induction on i. We denote by m d,i , r d,i , and t d,i , the number of edges, the size of the root cycle, and the recursive cost f M (C d,i ), of the cactus C d,i . First, let C d,0 be a ring of m d,0 = r d,0 = (d + 3)/3 edges (which is an integer by definition of h). The exploration cost of this cactus is t d,0 = f M (C d,0 ) = 3(r d,0 -1) = d. For i ≥ 1, we define inductively C d,i as a cactus with a root cycle of size r d,i = t d,i-1 + 1 on which are attached on d different vertices the cactuses sub 1 (C d,i-1 ), sub 2 (C d,i-1 ), up to sub d (C d,i-1 ) (see Figure 6). Finally, C d is defined as C d,h . The number of edges of C d,i is m d,i = r d,i + ∑ d j=1 ( j • m d,i-1 ). Recall that the algorithm MIXED-METHOD chooses the number k of sub-cactuses to explore with the algorithm CHAIN-METHOD such as to minimize the additional cost k • (r d,i -1) + f M (sub d-k (C d,i-1 )). On one hand, we have r d,i -1 = t d,i-1 by definition. On the other hand, the recursive exploration cost of each sub-cactus sub j

• m h .

 h It remains now to express d and m h as a function of the number n of vertices of the cactus C d .2 d ≤ β h ≤ 1 2 m h ≤ n ≤ m h ≤ β 2h ≤ d 6hThe inequality 2 d ≤ n implies that log d ≤ log log n, while d 6h = d 3d log d ≥ n allows to derive that 3d log 2 d ≥ log n and thus that d ≥ 1 3 log n

  1 c in front of f E (C i ) for the sub-cactuses C i such that |C i | ≤ n c . Since the number of vertices is divided by c, there can be at most log c n such factors stacking in a branch of the cactus. Developing the recursive cost, we thus obtain a total exploration time of at most n(1+ 1 c ) log c n (2c+3).

In[START_REF] Bournat | Computability of Perpetual Exploration in Highly Dynamic Rings[END_REF], the authors define a ring of size two as a two-node path if the graph is simple, or as two nodes linked by two bidirectional edges otherwise.

The actual definition of the "clockwise" direction does not really matter as long as it is any fixed direction.

To simplify the notation, we define f M (C i ) as 0 when i > .

Acknowledgements The authors would like to thank Arnaud Casteigts for insightful and valuable discussions regarding the topic of this paper.

D. Ilcinkas is partially supported by the ANR projects DESCARTES (ANR-16-CE40-0023) and ESTATE (ANR-16-CE25-0009), and the "Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02). A. M. Wade is partially supported by the African Center of Excellence in Mathematics, Computer Science and ICT (CEA-MITIC).