# Energy Constrained Depth First Search111Research partially supported by
National Science Centre (Poland) grant number 2015/17/B/ST6/01887.

Shantanu Das  LIF, Aix-Marseille University and CNRS, Marseille, France
<EMAIL_ADDRESS>Dariusz Dereniowski  Faculty of Electronics,
Telecommunications and Informatics, Gdańsk University of Technology, Poland
<EMAIL_ADDRESS>Przemysław Uznański  Department of Computer Science, ETH
Zürich, Switzerland
<EMAIL_ADDRESS>
###### Abstract

Depth first search is a natural algorithmic technique for constructing a
closed route that visits all vertices of a graph. The length of such route
equals, in an edge-weighted tree, twice the total weight of all edges of the
tree and this is asymptotically optimal over all exploration strategies. This
paper considers a variant of such search strategies where the length of each
route is bounded by a positive integer $B$ (e.g. due to limited energy
resources of the searcher). The objective is to cover all the edges of a tree
$T$ using the minimum number of routes, each starting and ending at the root
and each being of length at most $B$. To this end, we analyze the following
natural greedy tree traversal process that is based on decomposing a depth
first search traversal into a sequence of limited length routes. Given any
arbitrary depth first search traversal $R$ of the tree $T$, we cover $R$ with
routes $R_{1},\ldots,R_{l}$, each of length at most $B$ such that: $R_{i}$
starts at the root, reaches directly the farthest point of $R$ visited by
$R_{i-1}$, then $R_{i}$ continues along the path $R$ as far as possible, and
finally $R_{i}$ returns to the root. We call the above algorithm _piecemeal-
DFS_ and we prove that it achieves the asymptotically minimal number of routes
$l$, regardless of the choice of $R$. Our analysis also shows that the total
length of the traversal (and thus the traversal time) of piecemeal-DFS is
asymptotically minimum over all energy-constrained exploration strategies. The
fact that $R$ can be chosen arbitrarily means that the exploration strategy
can be constructed in an online fashion when the input tree $T$ is not known
in advance. Each route $R_{i}$ can be constructed without any knowledge of the
yet unvisited part of $T$. Surprisingly, our results show that depth first
search is efficient for energy constrained exploration of trees, even though
it is known that the same does not hold for energy constrained exploration of
arbitrary graphs.

Key Words: DFS traversal, distributed algorithm, graph exploration, piecemeal
exploration, online exploration

##  1 Introduction

Graph-theoretic problems in which one wants to cover the entire graph with one
or more routes satisfying certain objective is a well established and long
studied topic in many areas of computer science. Particular problems vary
depending on the research area or potential applications, including the study
of simple graph traversals like DFS or BFS, for algorithmic purposes, to
complex transportation problems with many variations of traveling salesman
problem (TSP), or pursuit-evasion games like the watchman problem, and finally
distributed monitoring of networks using mobile agents.

For one possible application of our results, consider a mobile robot that
needs to explore an initially unknown tree. We assume that the tree is edge-
weighted and the weight of each edge denotes the length of that edge. Starting
from a single vertex (the root) of the tree, the robot must traverse all edges
of and return to its initial location. Upon visiting a vertex $v$ for the
first time, the robot discovers the edges incident to $v$ and can choose one
of them to continue the exploration. Provided that the robot can remember the
visited vertices and edges, a simple depth first search (DFS) is an efficient
algorithm for exploring the tree, achieving the optimal cost of twice the sum
of the lengths of edges in the tree.

Consider a more interesting scenario, when the robot has a limited source of
energy (e.g. a battery) which allows it to traverse a path of length at most
$B$ (we say such a robot is _energy constrained_). Naturally, we assume that
each vertex of the tree is at distance at most $B/2$ from the root, otherwise
the tree cannot be fully explored. In this case, exploration is possible if
the robot can recharge its battery whenever it returns back to the starting
location. Thus, the exploration is a collection of routes of the robot, each
of which starts and ends at the root, and has length at most $B$. We are
interested in the minimum number of such routes needed (i.e. the number of
times the robot has to recharge) to completely explore the tree.

This model of exploration may be of interest for several reasons. One obvious
reason is related to the capabilities of the robot; it may have a restricted
fuel tank capacity or perhaps a harsh or risky environment enforces a return
to its home-base every so often. A robot that returns periodically to the root
can inform about new discoveries — in this way the knowledge is accumulated
gradually at the base-station while the algorithm progresses. This may, for
example, reduce the risk of having no data in case of robot failure prior to
the end of exploration. From a different point of view, this process may be
seen as a _piecemeal learning_ , that is, one in which it is possible to have
a trade off between exploration and utilization; the two phases representing
parts in which learning occurs (exploration) and part in which accumulated
knowledge is used (utilization). Finally, having many restricted-length routes
covering a tree instead of a single long route may be potentially applied in
scenarios in which one wants to minimize exploration time by strategies using
multiple robots. In fact, when the robots are incapable of refueling, we can
use several robots to explore the tree, each robot traversing a path of length
$B$. In that case, it is important to minimize the number of robots used as
well as the total energy cost for exploration.

Note that the _piecemeal exploration_ problem has been studied before not just
for trees but also for arbitrary connected graphs. However those results were
restricted to visiting vertices at depth of at most $B/2(1+\beta)$, for some
$\beta>0$, with the cost of exploration deteriorating sharply as $\beta$
approached zero. In this paper we would like to consider exploration
strategies that completely visit all trees up to the maximum possible depth of
$B/2$. No such exploration algorithm have been studied for either general
graphs or special graphs such as trees. Simple strategies based on depth-first
search (breadth first search) perform badly in the case of piecemeal
exploration of arbitrary graphs. However as we show in this paper, the
piecemeal version of depth-first search performs optimally in trees. This fact
is surprising given the fact that for exploration by multiple open routes
(routes that do not end at the root) depth-first strategies in trees can have
an overhead of $\Omega(\log{n})$ [11].

Related work: There exists extensive literature on graph traversal and
exploration, we survey here only the most relevant results on graph
exploration by mobile agents. Exploration of general graphs having $n$ nodes
and $m$ edges, by a single agent, has been studied in [24] who gave an
algorithm of $m+O(n)$ steps. For exploration by $k$ agents, [19] provides an
exploration algorithm taking $O(D+n/\log k)$ steps in trees of $n$ nodes and
height $D$. This algorithm turns out to be $O(k/\log k)$ competitive [21]
(where competitiveness is the ratio of the number of steps of an algorithm
over the optimal number of steps). Authors in [9] give a $O(n/k+D^{k-1})$ time
algorithm for tree exploration while [17] gives an algorithm for sparse trees
with competitive ratio $O(D^{1-1/p})$, where $p$ is defined as the tree
density. For some lower bound on exploration time, see [18, 19, 21]. For other
recent results on exploration time see e.g. [9, 13, 14, 22, 23]. Other than
optimizing time, exploration using little memory for the agents has also been
studied, see e.g. [1, 12].

None of the results mentioned above consider any energy limitation for the
agents. The energy constrained exploration problem was first studied under the
name of _Piecemeal Graph Exploration_ [8], with the assumption that the route
length $B\geq 2(1+\beta)r$, where $r$ is the furthest distance from the
starting node to other nodes, and $0<\beta<1$. That paper provided exploration
algorithms for a special class of grid graphs with ‘rectangular obstacles’.
Awerbuch et al. [5] showed that, for general graphs, there exists an energy
constrained exploration algorithm with a total cost of $O(m+n^{1+o(1)})$. This
has been further improved (by an algorithm that is a combination of DFS and
BFS) to $O(m+n\log^{2}n)$ in [6]. Finally [15] provided an exploration
algorithm for general unknown weighted graphs with total cost asymptotic to
the sum of edge weights of the graph. Note that, as mentioned, all the above
strategies require the length of each route to be strictly larger than the
shortest return path from the starting vertex to the farthest vertex. In other
words, these algorithms fail in the extreme cases when the height of the
explored tree (or the diameter of the graph) is equal to half of the energy
budget, which seem to be the most challenging cases.

The same tree exploration model as we study in this work has been considered
in [11, 16] for unweighted trees and multiple agents, with one difference:
each agent traverses a path of length at most $B$ such that the path starts at
the root but may end at any node of the tree (in other words, agents do not
have to return to the homebase). It has been shown in [11] that if the tree is
not known in advance, then there exists an exploration algorithm (that
minimizes the number of agents used) with competitive ratio of $O(\log B)$ and
this is the best possible. On the other hand, it was shown that by allowing
the route lengths to be a constant factor more than $B$, it is possible to
explore the tree using the minimum number of agents [16]. Distributed
algorithms for energy constrained agents has been a subject of recent
investigation, see e.g. [2, 3, 7]. Authors in [10] also consider a model in
which agents are allowed to transfer part of their energy to another agent.
There are many studies on variants of the traveling salesman problem,
including the $k$-TSP [4, 20] related to the task of finding a bounded length
route in a graph. Such results are out of scope for this paper.

Our Results and Outline: In this work we analyze a very natural process of
partitioning a depth first search traversal $R_{\textup{DFS}}$ of a tree into
a sequence $\mathcal{S}=(R_{1},\ldots,R_{k})$ of routes where each route
$R_{i}$ has length at most $B$, starts and ends at the root of the tree (see
Section 3 for a formal definition). We prove that the number of routes $k$ is
asymptotically optimal (Theorem 1), that is, it is within a constant factor of
the number of routes in any exploration strategy composed of routes of length
at most $B$ that cover the entire tree. This fact, being intuitively expected
for trees (although it does not hold in general graphs [15]) turns out to be
nontrivial. Our approach is to consider another parameter of an exploration
strategy: the _cost_ (see Section 4) defined as the sum of the lengths of all
routes in an exploration strategy. In order to prove our main result, we
argue, in Section 5, that the cost of $\mathcal{S}$ is asymptotically optimal
(see Theorem 2). Then, in Section 4 we argue that the fact that $\mathcal{S}$
has small cost implies that the number of routes in $\mathcal{S}$ is
expectedly small.

We emphasize that the above claim holds independently of the choice of the
initial depth first search traversal $R_{\textup{DFS}}$. The implications of
this fact are twofold. First, it provides a theoretical insight into such a
partitioning of a depth first search traversals into bounded-length segments.
Second, for an exploration algorithm design it means that the routes $R_{i}$
may be constructed without knowing $R_{\textup{DFS}}$ in advance, or more
precisely, the routes may be build in an online fashion based only on the
knowledge of the subtree explored to date. This property makes our algorithm
suitable for online exploration of unknown trees by energy constrained mobile
agents.

##  2 Exploration strategies

In this work we consider edge-weighted rooted trees $T=(V(T),E(T),\omega\colon
E(T)\to\mathbb{R}_{+})$, with root $r$. We define a _route_ $R$ as sequence of
nodes, $R=(v_{0},v_{1},\ldots,v_{l})$, where $v_{i}$ is a vertex of $T$ for
each $i\in\\{0,\ldots,l\\}$, as follows:

  1. (i)

$\\{v_{i},v_{i+1}\\}\in E(T)$ for each $i\in\\{0,\ldots,l-1\\}$,

  2. (ii)

$v_{0}=v_{l}$ is the root $r$ of $T$.

Informally speaking, a route is a sequence of vertices forming a walk in $T$
that starts and ends at the root. We define the _length_ of $R$ to be

$\ell(R)=\sum_{i=1}^{l}\omega(\\{v_{i-1},v_{i}\\}).$

We say that a vertex $v$ is _visited_ (and edge $\\{v_{i-1},v_{i}\\}$ is
traversed) by the route if $v=v_{i}$ for some $i\in\\{1,\ldots,l\\}$. We also
say that the subtree of $T$ composed with all vertices visited by $R$ is
_covered_ by the route.

Given a tree $T$ and an integer $B$, we say that
$\mathcal{S}=(R_{1},\ldots,R_{k})$ is a $B$-_exploration strategy_ for $T$ (or
simply _exploration strategy_ if $B$ is clear from the context) if for each
$i\in\\{1,\ldots,k\\}$, $R_{i}$ is a route in $T$ of length at most $B$, and
each vertex of $T$ is visited by some route in $\mathcal{S}$. We write
$\left|\mathcal{S}\right|$ to refer to the number of routes in $\mathcal{S}$,
$k=\left|\mathcal{S}\right|$.

##  3 Problem statement and DFS exploration

The formulation of the combinatorial problem, to which we refer as _energy
constrained tree exploration_ , we study in this work is as follows.

Energy Constrained Tree Exploration problem

(ECTE)
Given a real number $B>1$ and an edge-weighted rooted tree $T$ of height at
most $B/2$ what is the minimum integer $k$ such that there exists a
$B$-exploration strategy that consists of $k$ routes?

Our goal is to analyze a particular type of solution to this problem, namely,
an exploration strategy that behaves like a depth first search traversal but
adopted to the fact that route lengths are bounded by $B$. Let
$R_{\textup{DFS}}=(v_{0},v_{1},\ldots,v_{l})$ be a route in $T$ that covers
the tree $T$ and performs a depth first search traversal of $T$. (Note that
$R_{\textup{DFS}}$ is a route and thus we consider a depth first search
traversal to have node repetitions.) For two vertices $u$ and $v$ of $T$,
$d(u,v)$ denotes the distance between $u$ and $v$ understood as the sum of
weights of the edges of the path connecting these vertices. We refer by
$\mathrm{PDFS}(T)=(R_{1},\ldots,R_{k})$ (_Piecemeal Depth First Search_) to
the following $B$-exploration strategy constructed iteratively for
$i:=1,\ldots,k$ (see also Figure 1 for an example):

  1. (i)

let $j_{0}=0$ i.e. $v_{j_{0}}=v_{0}=r$,

  2. (ii)

$R_{i}$ continues DFS exploration from where $R_{i-1}$ _stopped making
progress_ (from the node $v_{j_{i-1}}$) as long as for currently visited
$v_{p}$:

$d(r,v_{j_{i-1}})+\ell((v_{j_{i-1}},v_{j_{i-1}+1},\ldots,v_{p}))+d(v_{p},r)\leq
B,$ (1)

  3. (iii)

furthest $v_{p}$ (for $p\leq l$) that satisfies condition from (ii) is denoted
as $v_{j_{i}}$, the vertex where $R_{i}$ stopped making progress,

  4. (iv)

let
$R_{i}=P_{i-1}\circ(v_{j_{i-1}},v_{j_{i-1}+1},\ldots,v_{j_{i}-1},v_{j_{i}})\circ
P_{i}^{R}$, where $P_{i-1}$ is the path from $r$ to $v_{j_{i-1}}$, and
$P_{i}^{R}$ is the path from $v_{j_{i}}$ to $r$.

Such a strategy $\mathrm{PDFS}(T)$ is called a _DFS $B$-exploration_. We will
say that the part of $R_{i}$ containing the subsequence
$(v_{j_{i-1}},\ldots,v_{j_{i}})$ _makes progress_ on the route
$R_{\textup{DFS}}$.

Figure 1: A route $R_{\textup{DFS}}$ and the corresponding
$\mathrm{PDFS}(T)=(R_{1},R_{2},R_{3})$ with $B=20$: (a) a depth first search
traversal $R_{\textup{DFS}}=(a,b,c,b,d,e,d,f,d,b,a,g,a)$; (b)-(d) routes
$R_{1},R_{2},R_{3}$ with lengths $18,16$ and $20$, respectively

We remark that different depth first search traversals $R_{\textup{DFS}}$ may
result in different values of $k$ (different number of routes) in the
resulting DFS $B$-exploration, although for a particular choice of
$R_{\textup{DFS}}$ the corresponding $\mathrm{PDFS}(T)$ is unique. In the rest
of the work we fix the route $R_{\textup{DFS}}$ arbitrarily and thus
$\mathrm{PDFS}(T)$ refers to the unique DFS $B$-exploration strategy obtained
from $R_{\textup{DFS}}$.

##  4 Our results

The following theorem provides the first main result of this work.

######  Theorem 1.

Let $T$ be a tree and let the longest path from the root to a leaf in $T$ be
at most $B/2$. It holds $\left|\mathrm{PDFS}(T)\right|\leq
10\left|\mathcal{R}\right|$, where $\mathcal{R}$ is a $B$-exploration strategy
that consists of the minimum number of routes.

The theorem refers to the number of routes in an exploration strategy.
However, in order to analyze the behavior of $\mathrm{PDFS}(T)$, we will work
with another parameter on which we will focus in the entire analysis in the
subsequent section. For any $B$-exploration strategy
$\mathcal{S}=(R_{1},\ldots,R_{k})$ of $T$ we will denote by $\xi(\mathcal{S})$
the _cost_ of $\mathcal{S}$ defined as

$\xi(\mathcal{S})=\sum_{i=1}^{k}\ell(R_{i}).$

We denote by $\mathrm{COPT}(T)$ an optimal solution with respect to the cost,
that is, a $B$-exploration strategy whose cost is minimum over all
$B$-exploration strategies. This strategy will serve as a reference point to
prove asymptotic optimality (in terms of the number of routes) of the DFS
exploration. More precisely, we will prove the following theorem.

######  Theorem 2.

Let $T$ be a tree and let $B/2$ be greater than or equal to the longest path
from the root to a leaf in $T$. It holds $\xi(\mathrm{PDFS}(T))\leq
10\cdot\xi(\mathrm{COPT}(T))$.

The proof is postponed to the next parts of the paper and we finish this
section by concluding that Theorem 2 indeed implies Theorem 1.

###### Proof of Theorem 1.

We start with the following observation which relates the smallest possible
number of routes in a $B$-exploration strategy and the minimum possible cost.

######  Observation 3.

Given $T$ and $B$,
$\left|\mathcal{R}\right|\geq\left\lceil\xi(\mathrm{COPT}(T))/B\right\rceil$,
where $\mathcal{R}$ is a $B$-exploration strategy with minimum number of
routes.

###### Proof.

Each route of $\mathcal{R}$ is of length at most $B$. Thus,
$\left|\mathcal{R}\right|\geq\xi(\mathcal{R})/B$. By definition of
$\mathrm{COPT}(T)$, $\xi(\mathcal{R})\geq\xi(\mathrm{COPT}(T))$, and since
$\left|\mathcal{R}\right|$ is an integer, the claim follows. ∎

Recall that $R_{\textup{DFS}}=(v_{0},\ldots,v_{l})$ is the depth first search
traversal of $T$ used to obtain $\mathrm{PDFS}(T)$, and the $i$-th route
$R_{i}$ in $\mathrm{PDFS}(T)=(R_{1},\ldots,R_{k})$ makes progress on the depth
first search traversal by traversing the part of $R_{\textup{DFS}}$ that
starts at $v_{j_{i-1}}$ and ends at $v_{j_{i}}$. By definition of
$\mathrm{PDFS}(T)$, extending $R_{i}$ so that it makes progress with the walk
$(v_{j_{i-1}},\ldots,v_{j_{i}},v_{j_{i+1}})$ would exceed its length to be
more than $B$ for each $i<k$, i.e.,
$\ell(R_{i})+2\omega(\\{v_{j_{i}},v_{j_{i+1}}\\})>B$. Consider a tree
$T^{\prime}$ obtained from $T$ by subdividing the edge
$\\{v_{j_{i}},v_{j_{i+1}}\\}$ into two edges $\\{v_{j_{i}},x_{i}\\}$ and
$\\{x_{i},v_{j_{i+1}}\\}$ with weights $(B-\ell(R_{i}))/2$ and
$\omega(\\{v_{j_{i}},v_{j_{i+1}}\\})-(B-\ell(R_{i}))/2$, respectively, for
each $i\in\\{1,\ldots,k-1\\}$. (Hence the sum of the two weights of the new
edges $\\{v_{j_{i}},x_{i}\\}$ and $\\{x_{i},v_{j_{i+1}}\\}$ equals
$\omega(\\{v_{j_{i}},v_{j_{i+1}}\\})$, the weight of the subdivided edge.)
Note that the common nodes of $T$ and $T^{\prime}$ (that is, the nodes of $T$)
are visited by $\mathrm{PDFS}(T)$ and $\mathrm{PDFS}(T^{\prime})$ in the same
order, both $\mathrm{PDFS}(T)$ and $\mathrm{PDFS}(T^{\prime})$ are
$B$-exploration strategies and the length of each route in
$\mathrm{PDFS}(T^{\prime})$, except for the last one, is of length exactly
$B$. The latter in particular implies

$\left|\mathrm{PDFS}(T^{\prime})\right|=\left\lceil\frac{\xi(\mathrm{PDFS}(T^{\prime}))}{B}\right\rceil.$
(2)

Note that

$\xi(\mathrm{COPT}(T))=\xi(\mathrm{COPT}(T^{\prime}))$ (3)

because, informally speaking, a strategy that minimizes the cost never reaches
a node of degree two in order to return to previously visited node — thus, in
particular, a traversal of $\\{v_{j_{i}},x_{i}\\}$ is immediately followed by
a traversal of $\\{x_{i},v_{j_{i+1}}\\}$ and vice versa.

From Equation (2), Theorem 2 applied to $T^{\prime}$, Equation (3) and
Observation 3 (used in this order) we conclude that

$\left|\mathrm{PDFS}(T^{\prime})\right|=\left\lceil\frac{\xi(\mathrm{PDFS}(T^{\prime}))}{B}\right\rceil\leq
10\cdot\left\lceil\frac{\xi(\mathrm{COPT}(T^{\prime}))}{B}\right\rceil=10\cdot\left\lceil\frac{\xi(\mathrm{COPT}(T))}{B}\right\rceil\leq
10\cdot\left|\mathcal{R}\right|,$

and hence
$\left|\mathrm{PDFS}(T)\right|=\left|\mathrm{PDFS}(T^{\prime})\right|$
completes the proof of Theorem 1. ∎

##  5 Bounding the cost of $\mathrm{PDFS}(T)$

###  5.1 Additional notation

When referring to subtrees, we consider them always in the context of their
distance from the root. More specifically, we consider the _potential of a
node_ $v$, denoted by $\varphi(v)$, to be defined as $\varphi(v)=B/2-d(r,v)$.
If $u$ is the parent of $v$ in $T$, then we say that $u$ is the _higher_
endpoint of $\\{u,v\\}$ and $v$ is the _lower_ endpoint of the edge
$\\{u,v\\}$; we also say that $\\{u,v\\}$ is a _downward edge_ of $u$. For any
subtree $T^{\prime}$ of $T$, we define the _potential_ of $T^{\prime}$,
denoted $\varphi(T^{\prime})$, to be the potential of its root. Then,
$2\varphi(T^{\prime})$ is an upper bound on the total length of any route
inside $T^{\prime}$. We say that a route _reaches_ a potential $x$ in some
subtree if it reaches a vertex having potential $x$. Additionally, for any
subtree $T^{\prime}$ of $T$, we denote it _weight_ to be
$\omega(T^{\prime})=\sum_{e\in E(T^{\prime})}\omega(e)$, where $E(T^{\prime})$
is the edge set of $T^{\prime}$. In other words, the weight of $T$ to be the
total weight of its edges. We denote by $T[v]$ the subtree of $T$ rooted at
$v$ that contains $v$ and all its descendants, and by $T[e]$ the tree composed
of the edge $e$ and $T[v]$ where $v$ is the lower endpoint of $e$.

We say that a subtree $T^{\prime}$ of $T$ is _heavy_ if
$\omega(T^{\prime})>\varphi(T^{\prime})$, and otherwise we say that
$T^{\prime}$ is _light_. We extend this terminology to vertices and edges: a
vertex $v$ or an edge $e$ is _heavy_ if $T[v]$ or $T[e]$ is heavy,
respectively. Additionally, by $\mathsf{heavydeg}(v)$ we denote the number of
outgoing downward edges of $v$ that are heavy (note that if an edge is heavy,
then both its endpoints are heavy as well). Observe that if $v$ is any vertex
of $T$ and $T[v]$ is heavy, then one route is not enough to cover the entire
$T[v]$ in any $B$-exploration strategy.

###  5.2 Adversarial DFS-exploration

When analyzing the cost of $\mathrm{PDFS}(T)$ we will use a recursive approach
where the $B$-exploration of any subtree $T^{\prime}$ would be defined by
taking $B=2\varphi(T^{\prime})$, the maximum size of route starting and ending
at the root of $T^{\prime}$. However the first agent to reach subtree
$T^{\prime}$ may have performed other explorations before entering
$T^{\prime}$. Therefore we need to use a slightly generalized DFS
$B$-exploration, called a _$B^{\prime}$ -adversarial DFS $B$-exploration_,
denoted by $\mathrm{ADFS}_{B^{\prime}}(T)$, where the length of first route is
bounded by $B^{\prime}\leq B$. This is formally defined by replacing Equation
(1) for $i=1$ in condition (ii) in the definition of $\mathrm{PDFS}(T)$ by the
following equation (see also Figure 2):

$\ell((v_{j_{0}},v_{j_{0}+1},\ldots,v_{p}))+d(v_{p},r)\leq B^{\prime}.$ (4)

Figure 2: (a) a tree with a depth first search traversal
$(a,b,c,b,d,b,a,e,f,e,g,e,a)$; (b) a $B^{\prime}$-adversarial DFS
$B$-exploration $\mathcal{S}$ with $B^{\prime}=16$ and $B=20$ has three
routes: $(a,b,c,b,a)$ (length $14\leq B^{\prime}$), $(a,b,d,b,a,e,a)$ (length
$18\leq B$) and $(a,e,f,e,g,e,a)$ (length $16\leq B$);
$\xi(\mathcal{S})=14+16+16=46$. Note that two routes $(a,b,c,b,d,b,a)$ and
$(a,e,f,e,g,e,a)$ constitute a DFS $B$-exploration strategy with cost $34$

In other words, the length of the first route is bounded by $B^{\prime}$
(Equation (4)) and the lengths of the remaining routes are bounded by $B$
(Equation (1) for $i>1$).

For a given tree $T$, we define an _adversarial DFS exploration_ of $T$,
denoted by $\mathrm{ADFS}(T)$, and defined to be an exploration strategy
$\mathrm{ADFS}_{B^{\prime}}(T)$ that maximizes the cost, across all possible
values of $B^{\prime}$:

$\xi(\mathrm{ADFS}(T))=\max_{0\leq B^{\prime}\leq
2\varphi(T)}\xi(\mathrm{ADFS}_{B^{\prime}}(T)).$ (5)

In the following analysis, it will be convenient for us to use arguments that
rely on the fact that $B^{\prime}$, for our purposes, takes only one of the
finite values from $[0,2\varphi(T)]$. This is due to the above comment,
namely, for $T[r]$, where $r$ is the root of $T$, we have that $B^{\prime}=B$
and for any other subtree $T[v]$, the values of $B^{\prime}$ interesting for
us depend on the prefix of the route that starts at the root of $T$ and
reaches $v$. Thus, a simple inductive argument allows us to conclude that the
value of $B^{\prime}$ depends on all possible DFS $B$-exploration strategies
of $T$ (the number of those is finite). Hence, we denote by $\mathcal{B}$ the
finite set that consists all values $B^{\prime}=B-x$ such that there exists a
route in $T$ of length $x$ that starts at the root of $T$ and ends at $x$.
Thus, we can restate (5):

$\xi(\mathrm{ADFS}(T))=\max_{B^{\prime}\in\mathcal{B}}\xi(\mathrm{ADFS}_{B^{\prime}}(T)).$

Note that it follows from the definition that

$\xi(\mathrm{ADFS}(T))\geq\xi(\mathrm{PDFS}(T)).$

Intuitively, if $v$ is any node of the tree $T$, then $\mathrm{ADFS}(T[v])$ is
the worst case scenario of how a DFS $B$-exploration may perform in $T[v]$ in
terms of the cost; this worst case is understood as considering the worst
possible ending point of the route that (in the entire tree $T$) precedes the
considered strategy $\mathrm{ADFS}(T[v])$.

######  Lemma 4.

If $v$ is any node of $T$ and $e_{1},e_{2},\ldots,e_{k}$ are all downward
edges of $v$, then

$\xi(\mathrm{COPT}(T[v]))=\sum_{1\leq i\leq k}\xi(\mathrm{COPT}(T[e_{i}])),$
(6) $\xi(\mathrm{ADFS}(T[v]))\leq\sum_{1\leq i\leq
k}\xi(\mathrm{ADFS}(T[e_{i}])).$ (7)

###### Proof.

Informally, equality in (6) for an optimal solution follows from the fact that
$\mathrm{COPT}(T[v])$ has the freedom to pick the length of each route to be
an arbitrary number in $\mathcal{B}$. Any strategies for
$T[e_{1}],T[e_{2}],\ldots,T[e_{k}]$ can be translated into strategy for
$T[v]$: the latter one is constructed by simply concatenating the former
exploration strategies. Similarly, if one takes an exploration strategy
$\mathrm{COPT}(T[v])$, then one can assume without affecting its cost that
each of its routes has only two occurrences of the root: it is the first and
last vertex of the route. But then, such a strategy $\mathrm{COPT}(T[v])$ can
be partitioned into the corresponding strategies for the trees
$T[e_{1}],T[e_{2}],\ldots,T[e_{k}]$.

We now prove (7). Consider an exploration strategy $\mathrm{ADFS}(T[v])$. Each
route of this strategy is of length at most $2\varphi(T)$. Obtain an
exploration strategy $\mathcal{S}$ by partitioning each route in
$\mathrm{ADFS}(T[v])$ in such a way that the concatenation of all routes in
$\mathcal{S}$ equals the concatenation of all routes in $\mathrm{ADFS}(T[v])$
and no route in $\mathcal{S}$ has $v$ as an internal vertex. (Thus, each route
of $\mathcal{S}$ starts and ends at $v$.) Note that
$\xi(\mathcal{S})=\xi(\mathrm{ADFS}(T[v]))$. Now, $\mathcal{S}$ can be
partitioned into $\mathcal{S}_{1},\ldots,\mathcal{S}_{k}$ such that
$\mathcal{S}_{i}$ is a $b_{i}^{\prime}$-adversarial DFS exploration strategy
of $T[e_{i}]$ for some $b_{i}^{\prime}\leq 2\varphi(T[v])$, i.e.,
$\mathcal{S}_{i}=\mathrm{ADFS}_{b_{i}^{\prime}}(T[e_{i}])$, for each
$i\in\\{1,\ldots,k\\}$ and the concatenation of
$\mathcal{S}_{1},\ldots,\mathcal{S}_{k}$ gives $\mathcal{S}$. Thus,

$\xi(\mathrm{ADFS}(T[v]))=\xi(\mathcal{S})=\sum_{i=1}^{k}\xi(\mathrm{ADFS}_{b_{i}^{\prime}}(T[e_{i}])).$

To conclude the proof, observe that by the definition of adversarial
exploration

$\xi(\mathrm{ADFS}_{b_{i}^{\prime}}(T[e_{i}]))\leq\xi(\mathrm{ADFS}(T[e_{i}])),\quad
i\in\\{1,\ldots,k\\}.\qed$

The proof of Theorem 2 will follow from the following two results (and the
fact that $\xi(\mathrm{PDFS}(T))\leq\xi(\mathrm{ADFS}(T))$.)

######  Lemma 5.

For any tree $T$, if $T$ is light, then
$\xi(\mathrm{ADFS}(T))<2\cdot\xi(\mathrm{COPT}(T)).$

###### Proof.

If $T$ is light, then observe that $\mathrm{ADFS}(T)$ either consists of one
route, in which case $\xi(\mathrm{ADFS}(T))=\xi(\mathrm{COPT}(T))$, or it
contains at least two routes but then the second route, having length up to
$2\varphi(T)$, will explore all remaining vertices of $T$ since
$\varphi(T)\geq\omega(T)$ holds for a light tree. Thus, in the latter case
$\mathrm{ADFS}(T)$ has exactly two routes, one of them being strictly shorter
than $2\omega(T)$, which gives $\xi(\mathrm{ADFS}(T))<4\omega(T)\leq
2\cdot\xi(\mathrm{COPT}(T))$. ∎

######  Theorem 6.

If $T$ is heavy and $r$ is its root, then:

  1. (i)

if $\mathsf{heavydeg}(r)=1$, then
$\xi(\mathrm{ADFS}(T))<10\cdot\xi(\mathrm{COPT}(T))-8\cdot\varphi(T)$,

  2. (ii)

if $\mathsf{heavydeg}(r)\not=1$, then
$\xi(\mathrm{ADFS}(T))<10\cdot\xi(\mathrm{COPT}(T))-16\cdot\varphi(T)$.

In order to prove the above Theorem we will first define a special class of
heavy trees called _Skinny Tree_ which has the following property.

  1. (ST)

Skinny Tree Property: _If the root $r$ of $T$ has heavy degree equal to one,
then consider the longest path in $T$ that connects $r$ to such a $r^{\prime}$
that each internal vertex of the path has heavy degree equal to $1$ (i.e. each
edge of the path is heavy). We then require that each vertex of this path,
except for $r^{\prime}$, has at most one light edge incident to it._

We can show (c.f. Section A in the appendix) how to rearrange any tree to have
the above property and we also show that:

######  Lemma 7.

For any tree T, there exists $\varepsilon>0$ and corresponding tree
$T_{\varepsilon}$ such that (i) $T_{\varepsilon}$ satisfies Property (ST), and
(ii) if Theorem 6 holds for $T_{\varepsilon}$ then Theorem 6 holds for $T$.

Due to above result, we can now focus on proving Theorem 6 for any tree $T$
with the above-mentioned property in the rest of the paper (Section 5.3).

###  5.3 Proof of Theorem 6 for Skinny Trees

We will proceed by induction on the number of heavy edges in a tree. This is a
valid approach since the parent of a heavy node is also heavy.

For the base case consider $T$ with no heavy edges. In particular we have that
$\mathsf{heavydeg}(r)=0$. Denote downward edges at $r$ by
$e_{1},e_{2},\ldots,e_{l}$. For each $i\in\\{1,\ldots,l\\}$, $T[e_{i}]$ is
light and hence by Lemma 5,
$\xi(\mathrm{ADFS}(T[e_{i}]))<2\cdot\xi(\mathrm{COPT}(T[e_{i}]))$. Thus in
particular, by (6) and (7) and $\xi(\mathrm{COPT}(T))\geq 2\omega(T)$,

$\xi(\mathrm{ADFS}(T))<2\xi(\mathrm{COPT}(T))\leq
10\xi(\mathrm{COPT}(T))-16\omega(T)\leq 10\xi(\mathrm{COPT}(T))-16\varphi(T).$

For the induction step, we assume that Theorem 6 holds for all heavy proper
subtrees of $T$. In what follows we consider two cases: when
$\mathsf{heavydeg}(r)>1$ and $\mathsf{heavydeg}(r)=1$.

#### Case of $\mathsf{heavydeg}(r)>1$

Let $e_{1},\ldots,e_{h}$ be the heavy downward edges at $r$ and
$e^{\prime}_{1},\ldots,e^{\prime}_{l}$ be the light downward edges at $r$. By
induction hypothesis (and precisely Theorem 6(i)) we obtain

$\xi(\mathrm{ADFS}(T[e_{i}]))<10\cdot\xi(\mathrm{COPT}(T[e_{i}]))-8\varphi(T[e_{i}])$

for each $i\in\\{1,\ldots,h\\}$. Then, by (7) of Lemma 4, by Lemma 5, and by
$\varphi(T)=\varphi(T[e_{i}]))$ (used in this order):

$\displaystyle\xi(\mathrm{ADFS}(T))$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{h}\mathrm{ADFS}(T[e_{i}])+\sum_{i=1}^{l}\mathrm{ADFS}(T[e_{i}^{\prime}])$
$\displaystyle<$
$\displaystyle\sum_{i=1}^{h}\big{(}10\xi(\mathrm{COPT}(T[e_{i}]))-8\varphi(T)\big{)}+\sum_{i=1}^{l}2\xi(\mathrm{COPT}(T[e^{\prime}_{i}]))$
$\displaystyle\leq$ $\displaystyle
10\left(\sum_{i=1}^{h}\xi(\mathrm{COPT}(T[e_{i}]))+\sum_{i=1}^{l}\xi(\mathrm{COPT}(T[e^{\prime}_{i}]))\right)-8\varphi(T)\cdot
h$ $\displaystyle\leq$ $\displaystyle 10\xi(\mathrm{COPT}(T))-16\varphi(T).$

The last inequality is due to (6) and $h=\mathsf{heavydeg}(r)\geq 2$.

#### Case of $\mathsf{heavydeg}(r)=1$

Let $r^{\prime}$ be the closest descendant of $r$ in $T$ that is heavy and
satisfies $\mathsf{heavydeg}(r^{\prime})\neq 1$. Note that such a vertex
always exists and $r^{\prime}$ is unique. Let $P$ denote the path connecting
$r$ to $r^{\prime}$. Additionally, we denote by $e_{1},e_{2},\ldots,e_{l}$ all
light edges incident to vertices in $V(P)\setminus\\{r^{\prime}\\}$ in the
_non-decreasing_ order of their potentials. (We remark here that the subtree
rooted at $r^{\prime}$ has been covered by the base case of the induction and
by the case when the heavy degree is greater than one.) Denote
$\varphi_{i}=\varphi(e_{i})$, $i\in\\{1,\ldots,l\\}$. Due to Lemma 7 (and more
precisely by the fact that thanks to Lemma 7 we assume that in the tree $T$
all edges $e_{1},\ldots,e_{l}$ have pairwise different potentials) we have:

$\varphi(r)>\varphi_{l}>\cdots>\varphi_{2}>\varphi_{1}>\varphi(r^{\prime})=\varphi_{0}.$

See Figure 3(a) that illustrates the path $P$ and placements of the edges
$e_{i}$ and the corresponding potentials.

Figure 3: (a) the path $P$ (although it may contain vertices of degree two,
they are trivial from the point of view of the analysis, thus omitted in the
picture); (b) illustration of $x_{i}$’s. Note that the first route (and
possibly arbitrarily many more routes) always reaches $r^{\prime}$

We take for brevity

$w_{i}=\omega(T[e_{i}])=\frac{1}{2}\xi(\mathrm{COPT}(T[e_{i}]))\text{\quad
for\ }i\in\\{1,\ldots,l\\},\quad
w_{0}=\frac{1}{2}\xi(\mathrm{COPT}(T[r^{\prime}])).$

Let $c$ be the number of routes in $\mathrm{COPT}(T)$, and we denote by
$x_{i}$ the lowest potential $i$-th route reached on the path $P$ (we ignore
potentials it reached in subtrees — see Figure 3(b)), where the routes are
without loss of generality ordered so that $x_{1}\leq x_{2}\leq\cdots\leq
x_{c}.$

Consider $j\in\\{1,\ldots,c\\}$. Informally speaking, the first $j$ routes of
$\mathrm{COPT}(T)$ need to cover all subtrees $T[e_{i}]$ such that the
potential of the higher endpoint of $e_{i}$ is _strictly_ smaller than
$x_{j}$; otherwise some vertices would not be visited by $\mathrm{COPT}(T)$.
The total weight of these subtrees is $\sum_{i:\varphi_{i}<x_{j}}w_{i}$.
Observe, that the total length of all parts of an $i$-th route that do not
belong to the path $P$ is at most $2x_{i}$. Thus, the above total weight of
the above-mentioned subtrees satisfies

$\sum_{i:\varphi_{i}<x_{j}}w_{i}\leq(x_{1}+\cdots+x_{j-1})\quad\text{for each
}j\in\\{1,\ldots,c+1\\},$ (8)

where we denote $x_{c+1}=+\infty$ for the sake of simplicity.

We are now interested in bounding the cost of $\mathrm{ADFS}(T)$ on the path
$P$ with respect to $\sum_{i=1}^{c}2(\varphi(r)-x_{i}),$ that is, with respect
to the cost of $\mathrm{COPT}(T)$ on the path $P$. To do this, we start by
comparing $x_{1},\ldots,x_{c}$ with $y_{1},\ldots,y_{d}$ chosen by an
appropriate greedy procedure:

$y_{j}=\min\big{\\{}y:\sum_{i:\varphi_{i}\leq
y}w_{i}>y_{1}+\ldots+y_{j-1}\big{\\}},$ (9)
$d=\min\left\\{i:y_{1}+\cdots+y_{i}\geq w_{0}+w_{1}+\ldots+w_{m}\right\\},$

in other words, assigning $y_{j}$ to be the first value where (8) is violated
given only $y_{1},\ldots,y_{j-1}$. (Notice that from the definition we have
that always $y_{j}\in\\{\varphi_{0},\varphi_{1},\ldots,\varphi_{l}\\}$.
Moreover, if $y_{j}>\varphi_{0}$, then $y_{j+1}>y_{j}$.) We obtain the
following lemma which says that, across all sequences satisfying (8), $y_{i}$
takes maximal values:

######  Lemma 8.

It holds that $d\leq c$ and $y_{j}\geq x_{j}$ for each $j\in\\{1,\ldots,d\\}$.

###### Proof.

We proceed by induction on $j$.

For the inductive base, we have $x_{1}=y_{1}=\varphi(r^{\prime})$. For the
inductive step, assume the claim holds for all indices smaller than $j$.
Suppose for a contradiction that $x_{j}>y_{j}$. Then,

$\sum_{i:\varphi_{i}\leq y_{j}}w_{i}\leq\sum_{i:\varphi_{i}<x_{j}}w_{i}$

and by (8) and the inductive assumption applied for all indices smaller than
$j$,

$\sum_{i:\varphi_{i}<x_{j}}w_{i}\leq y_{1}+\ldots+y_{j-1}.$

These two inequalities give a contradiction with $\eqref{eq4}$. ∎

Observe that $\mathrm{ADFS}(T)$ first traverses (in that order) some subset of
light subtrees $T[e_{i}]$, whose indices we denote by
$H\subseteq\\{1,\ldots,l\\}$, in a decreasing order of their indices. The
above routes, none of which contains $r^{\prime}$, will form the _first part
of_ $\mathrm{ADFS}(T)$. Then, all vertices of $T[r^{\prime}]$ are visited (to
those routes of $\mathrm{ADFS}(T)$ we refer at the _second part of_
$\mathrm{ADFS}(T)$) and following that, remaining light subtrees $T[e_{i}]$
for $i\in H^{\prime}=\\{1,\ldots,l\\}\setminus H$, in an increasing order of
their indices (_third part of_ $\mathrm{ADFS}(T)$). Note that there may exist
a route that has a non-empty intersection with a tree $T[e_{i}]$, $i\in H\cup
H^{\prime}$, and also contains $r^{\prime}$ — this route belongs by definition
to the second part of $\mathrm{ADFS}(T)$.

Denote by $z_{1},\ldots,z_{p}$ the lowest potentials reached by subsequent
routes in $\mathrm{ADFS}(T)$ on the path $P$ (ignoring as before the
potentials they reach in subtrees), only in the first part of
$\mathrm{ADFS}(T)$ in the reversed order of entering $T$:

$\varphi(r)\geq z_{p}\geq\cdots\geq z_{1}>\varphi(r^{\prime}).$ (10)

We note that each route in the first part of $\mathrm{ADFS}(T)$ visits
subtrees with a continuous segment of indices from $H$, that is $T[e_{i}]$’s
for $i\in H\cap\\{i_{1},\ldots,i_{2}\\}$ for some integers $i_{1},i_{2}$. We,
due to the weight of a light tree, its vertices belong to at most two
different routes.

######  Lemma 9.

If for some $i,j$ there is $z_{i}>y_{j}$, then $z_{i+1}\geq y_{j+1}$.

###### Proof.

If $y_{j+1}=y_{j}$ then the claim follows immediately from the fact that, by
(10), $z_{i+1}\geq z_{i}\geq y_{j}=y_{j+1}$. Similarly, if $z_{i}\geq y_{j+1}$
then by (10) we have $z_{i+1}\geq z_{i}\geq y_{j+1}$. Thus, assume that
$y_{j+1}\geq z_{i}$ and $y_{j+1}>y_{j}$.

Let $a>b$ be indices such that $y_{j}=\varphi_{a}$ and $y_{j+1}=\varphi_{b}$.
We have from the way $y_{j}$ is selected in (9):

$w_{0}+\cdots+w_{b}>y_{1}+\cdots+y_{j}\geq w_{0}+\cdots+w_{b-1},$
$w_{0}+\cdots+w_{a}>y_{1}+\cdots+y_{j-1}\geq w_{0}+\cdots+w_{a-1}.$

Thus,

$y_{j}>w_{a+1}+\cdots+w_{b-1}.$

This inequality, informally speaking, certifies that the total weight of all
subtrees $T[e_{s}]$ with $s\in\\{a+1,\ldots,b-1\\}$ is smaller than $y_{j}$.
By assumption $z_{i}>y_{j}$. By the definition of the sequence
$z_{1},\ldots,z_{p}$, the length of the $i$-th route in $\mathrm{ADFS}(T)$
restricted to the subtrees $T[e_{s}]$ is at least $2z_{i}$. (Note that we are
not using the fact that this route may avoid some subtrees $T[e_{s}]$ with
$s\in\\{a+1,\ldots,b-1\\}$ as we analyze the first part of $\mathrm{ADFS}(T)$
which ‘avoids’ each subtree $T[e_{s}]$ with $s\in\\{a+1,\ldots,b-1\\}\cap
H^{\prime}$.) Thus, the $i$-th route of $\mathrm{ADFS}(T)$ visits the node of
$P$ at potential $\varphi_{b}$ and hence $z_{i+1}\geq\varphi_{b}=y_{j+1}$ as
required in the lemma. ∎

We are now ready to bound the total cost of $\mathrm{ADFS}(T)$ with relation
to $\mathrm{COPT}(T)$. The cost of $\mathrm{COPT}(T)$ can be decomposed:

$\xi(\mathrm{COPT}(T))=O_{light}+O_{deep}+O_{path}+O_{flat},$ (11)

where:

$O_{light}$ — is the cost restricted to light subtrees $T[e_{i}]$ with
$i\in\\{1,\ldots,l\\}$,

$O_{deep}$ — is the cost restricted to the subtree $T[r^{\prime}]$,

$O_{path}$ — is the cost restricted to the path $P$ and the routes that do not
contain $r^{\prime}$, and

$O_{flat}$ — is the cost restricted to the path $P$ and routes that do contain
$r^{\prime}$.

Similarly, we express the cost of $\mathrm{ADFS}(T)$ as a sum:

$\xi(\mathrm{ADFS}(T))=D_{light}+D_{deep}+D_{desc}+D_{flat}+D_{asc},$ (12)

where

$D_{light}$ — is the cost of $\mathrm{ADFS}(T)$ restricted to light subtrees
$T[e_{i}]$ with $i\in\\{1,\ldots,l\\}$,

$D_{deep}$ — is the cost restricted to the subtree $T[r^{\prime}]$,

$D_{desc}$ — is the cost restricted to the path $P$ in the first part of
$\mathrm{ADFS}(T)$,

$D_{flat}$ — is the cost restricted to $P$ and the routes that contain
$r^{\prime}$ (i.e., the second part of $\mathrm{ADFS}(T)$), and

$D_{asc}$ — is the cost restricted to the path $P$ in the third part of
$\mathrm{ADFS}(T)$.

By Lemma 5, $\xi(\mathrm{ADFS}(T[e_{i}]))<2\xi(\mathrm{COPT}(T[e_{i}]))$ for
each $i\in\\{1,\ldots,l\\}$ and therefore

$D_{light}<2\cdot O_{light}.$ (13)

Denote by $s$ the smallest index such that $y_{s+1}>\varphi_{0}=y_{s}$ and let
$H=\\{j_{1},\ldots,j_{q}\\}$, $j_{1}<j_{2}<\cdots<j_{q}$. Recall that $H$ is
the set of indices $i$ such that $T[e_{i}]$ is covered in the first part of
$\mathrm{ADFS}(T)$. Since $z_{j_{1}}>y_{s}$, by iteratively applying Lemma 9
we obtain that

$z_{j_{i}}\geq y_{s+i-1}\textup{ for each }i\in\\{1,\ldots,q\\}.$

Therefore, by Lemma 8,

$\displaystyle\begin{aligned}
D_{desc}&=2\sum_{i=1}^{q}(\varphi(T)-z_{j_{i}})\leq
2\sum_{i=1}^{q}(\varphi(T)-y_{s+i-1})\\\ &\leq
2(\varphi(T)-\varphi_{0})+2\sum_{i=2}^{q}(\varphi(T)-x_{s+i-1})\leq
2\omega(P)+O_{path}.\end{aligned}$ (14)

By an analogous analysis, the same bound holds for the third part of
$\mathrm{ADFS}(T)$:

$D_{asc}\leq 2\omega(P)+O_{path}.$ (15)

By the inductive assumption we have

$D_{deep}<10\cdot O_{deep}-16\varphi(r^{\prime}).$ (16)

We also get the following bounds by analyzing how much each particular route
can overlap with $T[r^{\prime}]$. The first one follows from an observation
that each route having a non-empty intersection with $T[r^{\prime}]$ may have
length restricted to $T[r^{\prime}]$ at most $2\varphi(r^{\prime})$. Thus,
there exist at least $O_{deep}/(2\varphi(r^{\prime}))$ such routes in
$\mathrm{ADFS}(T)$ intersecting $T[r^{\prime}]$ and each such route
contributes at least $2\omega(P)$ to $O_{flat}$. Hence,

$O_{flat}\geq\frac{\omega(P)}{\varphi(r^{\prime})}\cdot O_{deep}.$ (17)

As for an upper bound, there exist at most $\lceil
D_{deep}/(2\varphi(r^{\prime}))\rceil+1$ routes in $\mathrm{PDFS}(T)$ that
contain $r^{\prime}$ (note that the first such route may include no other
vertices except for $r^{\prime}$ from $T[r^{\prime}]$). Thus,

$D_{flat}\leq 2\omega(P)\cdot\lceil
D_{deep}/(2\varphi(r^{\prime}))+1\rceil\leq 4\omega(P)+\omega(P)\cdot
D_{deep}/\varphi(r^{\prime}).$ (18)

Equations (18), (16) and (17), used in that order, give us

$\displaystyle D_{deep}+D_{flat}$ $\displaystyle\leq$ $\displaystyle
4\omega(P)+\left(\frac{\omega(P)}{\varphi(r^{\prime})}+1\right)D_{deep}$
$\displaystyle\leq$ $\displaystyle
4\omega(P)+\left(\frac{\omega(P)}{\varphi(r^{\prime})}+1\right)(10\cdot
O_{deep}-16\varphi(r^{\prime}))$ $\displaystyle\leq$ $\displaystyle
4\omega(P)-16\left(\omega(P)+\varphi(r^{\prime})\right)+10\cdot
O_{deep}\left(\frac{\omega(P)}{\varphi(r^{\prime})}+1\right)$
$\displaystyle\leq$ $\displaystyle
10O_{deep}+10O_{flat}-12\omega(P)-16\varphi(r^{\prime}).$

Then, by (13), (14) and (15) we have

$D_{light}+D_{asc}+D_{desc}\leq 2O_{light}+4\omega(P)+2O_{path}.$

The last two inequalities, (11), (12) and
$\varphi(r)=\omega(P)+\varphi(r^{\prime})$ finally give

$\displaystyle\xi(\mathrm{ADFS}(T))$ $\displaystyle\leq$ $\displaystyle
10O_{deep}+10O_{flat}+2O_{light}+2O_{path}-8\omega(P)-16\varphi(r^{\prime})$
$\displaystyle\leq$ $\displaystyle 10\xi(\mathrm{COPT}(T))-8\varphi(r),$

which completes the inductive proof of Theorem 6.

##  6 Conclusions and open problems

Our strategy $\mathrm{PDFS}(T)$ achieves the asymptotically minimum number of
routes and also minimizes the cost up to a small constant. In particular, we
provided an upper bound of $10$ for the competitiveness of any online
piecemeal exploration strategy. A trivial lower bound for the same problem is
$3/2$ (Consider the tree with three branches of lengths $B/2$, $B/2$ and $B$,
respectively, starting from the root: any online algorithm may cover the tree
with 3 routes, while the optimal is 2 routes). This leaves a gap between the
lower and upper bounds and the interesting open question is whether the
strategy $\mathrm{PDFS}(T)$ is the best possible algorithm? Another open
problem is to analyze similar strategies in other, more general, classes of
graphs instead of trees.

## References

  * [1] Christoph Ambühl, Leszek Gąsieniec, Andrzej Pelc, Tomasz Radzik, and Xiaohui Zhang.  Tree exploration with logarithmic memory.  ACM Trans. Algorithms, 7(2):17:1–17:21, 2011.
  * [2] Julian Anaya, Jérémie Chalopin, Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc, and Yann Vaxès.  Collecting information by power-aware mobile agents.  In Proceedings of Distributed Computing - 26th International Symposium, DISC 2012, pages 46–60.
  * [3] Julian Anaya, Jérémie Chalopin, Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc, and Yann Vaxès.  Convergecast and broadcast by power-aware mobile agents.  Algorithmica, 74(1):117–155, 2016.
  * [4] Sanjeev Arora.  Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems.  J. ACM, 45(5):753–782, 1998.
  * [5] Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, and Mona Singh.  Piecemeal graph exploration by a mobile robot.  Inf. Comput., 152(2):155–172, 1999.
  * [6] Baruch Awerbuch and Stephen G. Kobourov.  Polylogarithmic-overhead piecemeal graph exploration.  In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT 1998, pages 280–286.
  * [7] Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Barbara Geissmann, Daniel Graf, Arnaud Labourel, and Matús Mihalák.  Collaborative delivery with energy-constrained mobile robots.  In Proceedings of Structural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, pages 258–274.
  * [8] Margrit Betke, Ronald L. Rivest, and Mona Singh.  Piecemeal learning of an unknown environment.  Machine Learning, 18(2-3):231–254, 1995.
  * [9] Peter Brass, Flavio Cabrera-Mora, Andrea Gasparri, and Jizhong Xiao.  Multirobot tree and graph exploration.  IEEE Trans. Robotics, 27(4):707–717, 2011.
  * [10] Jurek Czyzowicz, Krzysztof Diks, Jean Moussi, and Wojciech Rytter.  Communication problems for mobile agents exchanging energy.  In Proceedings of Structural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, pages 275–288.
  * [11] Shantanu Das, Dariusz Dereniowski, and Christina Karousatou.  Collaborative exploration by energy-constrained mobile robots.  In Proceedings of Structural Information and Communication Complexity - 22nd International Colloquium, SIROCCO 2015, pages 357–369.
  * [12] Yann Disser, Jan Hackfeld, and Max Klimm.  Undirected graph exploration with $\Theta(\log\log N)$ pebbles.  In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 25–39.
  * [13] Yann Disser, Frank Mousset, Andreas Noever, Nemanja Skoric, and Angelika Steger.  A general lower bound for collaborative tree exploration.  CoRR, abs/1610.01753, 2016.
  * [14] Stefan Dobrev, Rastislav Královic, and Euripides Markou.  Online graph exploration with advice.  In Proceedings of Structural Information and Communication Complexity - 19th International Colloquium, SIROCCO 2012, pages 267–278.
  * [15] Christian A. Duncan, Stephen G. Kobourov, and V. S. Anil Kumar.  Optimal constrained graph exploration.  ACM Trans. Algorithms, 2(3):380–402, 2006.
  * [16] Mirosław Dynia, Mirosław Korzeniowski, and Christian Schindelhauer.  Power-aware collective tree exploration.  In Proceedings of Architecture of Computing Systems - ARCS 2006, 19th International Conference, pages 341–351.
  * [17] Mirosław Dynia, Jarosław Kutyłowski, Friedhelm Meyer auf der Heide, and Christian Schindelhauer.  Smart robot teams exploring sparse trees.  In Proceedings of Mathematical Foundations of Computer Science, 31st International Symposium, MFCS 2006, pages 327–338.
  * [18] Mirosław Dynia, Jakub Łopuszanski, and Christian Schindelhauer.  Why robots need maps.  In Proceedings of Structural Information and Communication Complexity, 14th International Colloquium, SIROCCO 2007, pages 41–50.
  * [19] Pierre Fraigniaud, Leszek Gąsieniec, Dariusz R. Kowalski, and Andrzej Pelc.  Collective tree exploration.  Networks, 48(3):166–177, 2006.
  * [20] Greg N. Frederickson, Matthew S. Hecht, and Chul E. Kim.  Approximation algorithms for some routing problems.  SIAM J. Comput., 7(2):178–193, 1978.
  * [21] Yuya Higashikawa, Naoki Katoh, Stefan Langerman, and Shin-ichi Tanigawa.  Online graph exploration algorithms for cycles and trees by multiple searchers.  J. Comb. Optim., 28(2):480–495, 2014.
  * [22] Nicole Megow, Kurt Mehlhorn, and Pascal Schweitzer.  Online graph exploration: New results on old and new algorithms.  Theor. Comput. Sci., 463:62–72, 2012.
  * [23] Christian Ortolf and Christian Schindelhauer.  A recursive approach to multi-robot exploration of trees.  In Proceedings of Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, pages 343–354.
  * [24] Petrisor Panaite and Andrzej Pelc.  Exploring unknown undirected graphs.  J. Algorithms, 33(2):281–295, 1999.

Appendix

##  Appendix A Tree rearrangement

This section is devoted to proving Lemma 7. We start with an informal
description providing a high level intuition that gives an overview of this
section. Our first step (Section A.1) is to construct a tree
$T_{\varepsilon}$, $\varepsilon\in\mathbb{R}^{+}$, based on $T$ such that
$T_{\varepsilon}$ satisfies property (ST). We will also need that
$T_{\varepsilon}$ ‘resembles’ $T$ in the following way: a search strategy is
valid for $T$ if and only if a ‘very similar’ strategy is valid for
$T_{\varepsilon}$. To simplify the statements considerably, it will be
convenient to encode strategies in an uniform way so that we can apply the
same strategy for both trees, without going into the details of tedious but
straightforward conversions between strategy for $T$ and strategy for
$T_{\varepsilon}$. We thus define (Section A.2) a collection $\mathcal{C}$ of
all possible strategies (including adversarial ones and those that are not
feasible for either $T$ or $T_{\varepsilon}$ because they contain routes that
are too long or do not visit all vertices). Then in Section A.3 we select the
right value of $\varepsilon$. The value of $\varepsilon$ and the construction
of $T_{\varepsilon}$ will ensure that a strategy in $\mathcal{C}$ is valid for
$T$ if and only if it is valid for $T_{\varepsilon}$. We then finally provide
the main result of this section (Lemma 7) states that, again thanks to the
choice of $\varepsilon$, if Theorem 6 holds for $T_{\varepsilon}$, then it
holds for $T$, thus allowing us to restrict only to trees satisfying property
(ST).

###  A.1 The construction of $T_{\varepsilon}$

We now construct the tree $T_{\varepsilon}=(V(T)\cup
X,E(T_{\varepsilon}),\omega^{\prime})$ based on $T=(V(T),E(T),\omega)$ and the
construction depends on a parameter $\varepsilon>0$ that will be fixed later.
We now impose only a condition on $\varepsilon$ that is needed for the
construction itself to be valid:

$\varepsilon<\min\\{\omega(e)\hskip 2.84544pt\bigl{|}\bigr{.}\hskip
2.84544pte\in E(T)\\}.$

Select an arbitrary vertex $u$ in $T$ with $\mathsf{heavydeg}(u)=1$ (denote by
$\\{u,v\\}$ the heavy downward edge at $u$) and $d>1$ light downward edges
$e_{1},\ldots,e_{d}$ at $v$. Subdivide the edge $e$ (see Figure 4 for an
illustration) by replacing it by a path
$P=(u=v_{0},v_{1},\ldots,v_{d-1},v_{d}=v)$ with the following edge lengths:
the first $d-1$ edges have length $\varepsilon/(d-1)$, i.e.,
$\omega^{\prime}(v_{i},v_{i+1})=\varepsilon/(d-1)$ for each
$i\in\\{0,\ldots,d-2\\}$, and for the last edge we set
$\omega^{\prime}(\\{v_{d-1},v\\})=\omega(\\{u,v\\})-\varepsilon$. (Note that
this preserves the distance between $u$ and $v$.) Then, the weight of each
edge $e_{i}$ decreases by $\varepsilon$,
$\omega^{\prime}(e_{i})=\omega(e_{i})-\varepsilon$ and the higher endpoint of
$e_{i}$ in $T_{\varepsilon}$ becomes $v_{i-1}$, $i\in\\{1,\ldots,d\\}$. (Note
that this ensures that the distance between $u$ and the lower endpoint of
$e_{i}$ or the distance between two children of $u$ is not greater in
$T_{\varepsilon}$ than in $T$.) This construction allows us to assume (by
permuting the edges $e_{1},\ldots,e_{d}$ appropriately) that the DFS traversal
of $T_{\varepsilon}$ visits the edges $e$ and $e_{1},\ldots,e_{d}$ in the same
order both in $T$ and in $T_{\varepsilon}$, ensuring that Condition (P2) is
satisfied.

Figure 4: (a) the node $u$ of $T$ with $\mathsf{heavydeg}(u)=1$ and light
downward edges $e_{1},\ldots,e_{d}$, $d=4$; (b) the corresponding edges in
$T_{\varepsilon}$ (the “$-\varepsilon$” indicated that the weight of the edge
is $\varepsilon$ smaller than the weight of the corresponding edge in $T$)

Since the vertex $v$ is selected arbitrarily, we repeat the above modification
for each such vertex $v$ obtaining the final tree $T_{\varepsilon}$.

We will require the following conditions to be satisfied:

  1. (P1)

there are at most two downward edges at each vertex in $T_{\varepsilon}$ with
$\mathsf{heavydeg}(v)=1$,

  2. (P2)

there exists a DFS traversal of $T_{\varepsilon}$ that visits the vertices in
$V(T)$ in the same order as the DFS traversal that we have fixed for $T$ in
this work,

  3. (P3)

$\mathcal{S}\in\mathcal{C}$ is feasible for $T$ if and only if $\mathcal{S}$
is feasible for $T_{\varepsilon}$.

Property (P3) will be proved in Lemma 13 and we now note:

######  Observation 10.

For each $\varepsilon>0$, the tree $T_{\varepsilon}$ satisfies Conditions (P1)
and (P2). ∎

######  Observation 11.

The strategies $\mathrm{ADFS}(T)$ and $\mathrm{ADFS}(T_{\varepsilon})$ visit
the nodes in $V(T)$ in the same order. ∎

###  A.2 Finding the right value of $\varepsilon$

We define a _potential route_ as a following pair: $R^{\prime}=(L,v)$, where
$L=(l_{1},\ldots,l_{p})$ is a sequence of leaves and $v\in
V(T_{\varepsilon})$. Then, $R^{\prime}$ _translates_ to a route $R$ in $T$ as
a concatenation of the following paths (in this order): the path from $r$ to
$l_{1}$, the path from $l_{i}$ to $l_{i+1}$, $i=1,\ldots,p-1$, the path from
$l_{p}$ to the closest ancestor $x$ of $v$ that belongs to $V(T)$ and finally
the path from $x$ to $r$. The length of $R$ is

$\ell(R)=d(r,l_{1})+d(l_{p},x)+d(x,r)+\sum_{1\leq i<p}d(l_{i},l_{i+1}).$

$R^{\prime}$ translates to a route in $T_{\varepsilon}$ in the same way,
except that take $x=v$, i.e., $v$ is not replaced by the ancestor. Then, a
_potential strategy_ is a sequence consisting of at most $j$ potential routes,
$j\in\\{1,\ldots,p\\}$, where $p$ is the number of leaves in $T$.

Note that a potential strategy may not translate to a valid $B$-exploration
strategy for $T$ or $T_{\varepsilon}$ because some nodes may not be explored
and some routes may be too long. A potential strategy is _feasible_ for $T$
(respectively $T_{\varepsilon}$) if it translates to a valid $B$-exploration
strategy for $T$ (respectively $T_{\varepsilon}$). We denote by $\mathcal{C}$
a collection of all potential strategies. Clearly, the size of $\mathcal{C}$
is finite.

We conclude with the following:

######  Observation 12.

For any route $R$ that may appear in $\mathrm{ADFS}(T)$, $\mathrm{COPT}(T)$,
$\mathrm{ADFS}(T_{\varepsilon})$ and $\mathrm{COPT}(T_{\varepsilon})$ there
exists a potential route that translates to $R$. ∎

###  A.3 The analysis of $T_{\varepsilon}$

In this section we argue that the construction of $T_{\varepsilon}$
‘preserves’ the problem: the minimum costs of adversarial DFS explorations of
both $T$ and $T_{\varepsilon}$, as well as $\mathrm{COPT}(T)$ and
$\mathrm{COPT}(T_{\varepsilon})$ remain close to each other for $\varepsilon$
small enough. Intuitively speaking, this follows from a ‘continuity argument’
formalized in the remaining part of this section.

For the tree $T_{\varepsilon}$ we define an interval denoted by
$\mathcal{I}=(0,y)$, $y<\min\\{\omega(e)\hskip 2.84544pt\bigl{|}\bigr{.}\hskip
2.84544pte\in E(T)\\}$, such that for each $\varepsilon\in(0,y)$, Condition
(P3) holds for $T_{\varepsilon}$. We now prove that this interval is well
defined, that is, $y>0$. (Note that for $\varepsilon=0$, $T_{\varepsilon}$ and
$T$ are the same.)

######  Lemma 13.

It holds $\mathcal{I}\neq\emptyset$.

###### Proof.

First we argue that there exists $y>0$ such that $T_{y}$ fulfills Condition
(P3). We select $y$ based on the tree $T$ and the collection $\mathcal{C}$.
Consider any $B^{\prime}\in\mathcal{B}$. The number of potential strategies in
$\mathcal{C}$ is finite, and hence the number of potential strategies in
$\mathcal{C}$ that do not translate to feasible ones for $T$ (denote subset of
those by $\mathcal{C}^{\prime}$) is also finite. For each
$\mathcal{S}\in\mathcal{C}^{\prime}$, define its _deficiency_ $x(\mathcal{S})$
as follows: the $x(\mathcal{S})$ is the maximum value such that either the
length of the first route in $\mathcal{S}$ is $B^{\prime}+x(\mathcal{S})$ or
the length of some other route in $\mathcal{S}$ in $T$ is $B+x(\mathcal{S})$.
Intuitively, $\mathcal{S}$ does not translate to a feasible
$B^{\prime}$-adversarial $B$-exploration strategy for $T$ because one of its
routes exceeds the allowed length by $x(\mathcal{S})$ and no route exceeds it
by more than $x(\mathcal{S})$. Take

$y:=\frac{1}{2n(m+1)}\cdot\min\left\\{\min\\{\omega(e)\hskip
2.84544pt\bigl{|}\bigr{.}\hskip 2.84544pte\in
E(T)\\},\min\\{x(\mathcal{S}^{\prime})\hskip 2.84544pt\bigl{|}\bigr{.}\hskip
2.84544pt\mathcal{S}^{\prime}\in\mathcal{C}^{\prime}\\}\right\\},$

where $m$ is the number edges in $T$. Since by definition, $x(\mathcal{S})>0$
for each $\mathcal{S}\in\mathcal{C}^{\prime}$, we obtain that $y>0$. Also, no
route in any $\mathcal{S}\in\mathcal{C}^{\prime}$ traverses an edge more than
$2n$ times and hence the length of any route of $\mathcal{S}$ in $T_{y}$
decreases by at most $2ynm$ with respect to its length in $T$. This implies
that some route $R$ of $\mathcal{S}$ has length in $T_{y}$ at least

$\tilde{B}+x(\mathcal{S})-2ynm\geq\tilde{B}+2yn(m+1)-2ynm>\tilde{B},$ (19)

where take $\tilde{B}=B^{\prime}$ if $R$ is the first route in $\mathcal{S}$
and $\tilde{B}=B$ otherwise. Therefore, $\mathcal{S}$ remains unfeasible in
$T_{y}$. Since exploration strategy that is feasible in $T$ remains feasible
in $T_{y}$ (recall that the length of each route is smaller in $T_{y}$ than in
$T$), we have that Condition (P3) holds for $T_{y}$.

Finally, observe that substituting $y$ by any value $\varepsilon$ smaller than
$y$ in the left hand side of (19) keeps this equation true. Therefore,
Condition (P3) is satisfied by $T_{\varepsilon}$ for each
$\varepsilon\in(0,y)$, which completes the proof. ∎

Before we state the main lemma of this section, we prove these technical
bounds:

######  Lemma 14.

For each $\varepsilon\in\mathcal{I}$ it holds:

  1. (i)

$\xi(\mathrm{ADFS}(T))\leq\xi(\mathrm{ADFS}(T_{\varepsilon}))+4\varepsilon
n^{2}$,

  2. (ii)

$\varphi(T_{\varepsilon})\leq\varphi(T)$, and

  3. (iii)

$\xi(\mathrm{COPT}(T_{\varepsilon}))\leq\xi(\mathrm{COPT}(T))$.

###### Proof.

By Observation 11, both $\mathrm{ADFS}(T)$ and
$\mathrm{ADFS}(T_{\varepsilon})$ visit the leaves of both trees in the same
order. Consider any edge $\\{u,v\\}$ in $T$ such that $v$ is its lower
endpoint. We have that there exists a _corresponding_ edge
$\\{u^{\prime},v\\}$ in $T_{\varepsilon}$. Moreover,
$\omega(\\{u,v\\})\leq\omega^{\prime}(\\{u^{\prime},v\\})+\varepsilon$. Since
for each edge traversal in $\mathrm{ADFS}(T)$, a traversal of the
corresponding edge occurs in $\mathrm{ADFS}(T_{\varepsilon})$ due to Condition
(P3), we obtain that if $t$ is the number of edge traversals in
$\mathrm{ADFS}(T)$, then

$\xi(\mathrm{ADFS}(T))\leq\xi(\mathrm{ADFS}(T_{\varepsilon}))+t\varepsilon\leq\xi(\mathrm{ADFS}(T_{\varepsilon}))+4n^{2}\varepsilon.$

The latter inequality follows from bounding each route in
$\mathrm{ADFS}(T_{\varepsilon})$ to have at most $2n$ edges, bounding the
number of routes by $n$ and observing that an edge is traversed at most twice
in each route.

Property (ii) is a direct consequence of the construction of
$T_{\varepsilon}$: any path in $T$ corresponds to a path in $T_{\varepsilon}$
that connects the same common nodes and contains all common edges of the
original path.

By construction of $T_{\varepsilon}$, the distance between any common nodes
$u\in V(T)$ and $v\in V(T)$ is not greater in $T$ than in $T_{\varepsilon}$,
which immediately gives (iii). ∎

######  Lemma 15.

There exists $\varepsilon>0$ such that if Theorem 6 holds for
$T_{\varepsilon}$, then Theorem 6 holds for $T$.

###### Proof.

We will analyze condition (i) in Theorem 6 and the proof for (ii) is analogous
as we note at the end of the proof.

Define a parameter $\tau(n^{\prime})$ to be the maximum number for which an
inequality

$\xi(\mathrm{ADFS}(T^{\prime}))\leq
10\cdot\xi(\mathrm{COPT}(T^{\prime}))-8\cdot\varphi(T^{\prime})-\tau(n^{\prime})$

holds for each tree $T^{\prime}$ on at most $n^{\prime}$ nodes that satisfies
Condition (i). Since the number of such trees is finite and the number of
potential strategies in $\mathcal{C}$ is finite for each tree $T^{\prime}$, we
obtain that $\tau(n^{\prime})>0$. By Lemma 13, there exists
$\varepsilon\in\mathcal{I}$ such that $\varepsilon>0$ and

$\varepsilon<\frac{\tau(2n)}{4n^{2}},$

$n=\left|V(T)\right|$, such that $T_{\varepsilon}$ satisfies Condition (P3).
Suppose that Theorem 6(i) holds for $T_{\varepsilon}$. Then, by Lemma 14 (in
particular, (i) of Lemma 14 is used to obtain the first inequality below and
(ii) and (iii) are used to obtain the third inequality below) we get:

$\displaystyle\xi(\mathrm{ADFS}(T))$ $\displaystyle<$
$\displaystyle\xi(\mathrm{ADFS}(T_{\varepsilon}))+4\varepsilon n^{2}$
$\displaystyle\leq$ $\displaystyle
10\cdot\xi(\mathrm{COPT}(T_{\varepsilon}))-8\cdot\varphi(T_{\varepsilon})+4\varepsilon
n^{2}-\tau(2n)$ $\displaystyle\leq$ $\displaystyle
10\cdot\xi(\mathrm{COPT}(T))-8\cdot\varphi(T)+4\varepsilon n^{2}-\tau(2n)$
$\displaystyle<$ $\displaystyle
10\cdot\xi(\mathrm{COPT}(T))-8\cdot\varphi(T).$

We can conduct the same argument for Theorem 6(ii) with the same value of
$\varepsilon$. Hence we obtain that Theorem 6 holds for $T$. ∎