{'fraction_non_alphanumeric': 0.05027932960893855, 'fraction_numerical': 0.01327310907722176, 'mean_word_length': 3.5840900835452234, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Nearest Neighbor Network Traversal

A mobile agent in a network wants to visit every node of an n-node network, using a small number of steps. We investigate the performance of the following ``nearest neighbor'' heuristic: always go to the nearest unvisited node. If the network graph never changes, then from (Rosenkrantz, Stearns and Lewis, 1977) and (Hurkens and Woeginger, 2004) it follows that Theta(n log n) steps are necessary and sufficient in the worst case. We give a simpler proof of the upper bound and an example that improves the best known lower bound. We investigate how the performance of this heuristic changes when it is distributively implemented in a network. Even if network edges are allow to fail over time, we show that the nearest neighbor strategy never runs for more than O(n^2) iterations. We also show that any strategy can be forced to take at least n(n-1)/2 steps before all nodes are visited, if the edges of the network are deleted in an adversarial way.


Introduction
In this paper we consider a problem about a computer network. We use a graph as our model: each computer is a vertex, and we join two vertices u, v by an edge whenever there is a direct communication link joining u and v. An agent in the network is an entity that inhabits one node at a time, and is allowed to move in steps, where a step consists of the agent leaving its current position u and entering a neighbor v of u.
The main goal of this paper is to discuss the task of agent node traversal, which is to make the agent visit all of the nodes of the network at least once. One practical application of traversal is that the agent can collect information from every node (like a census), without the need for any global network coordination. One might also use traversal as a way of exploring an initially unknown network.
One well-known technique for performing a traversal is to use depth first search (DFS), but we claim that it is not practical in all real-world settings. In a depth first search, whenever the agent is adjacent to an unvisited node, it moves to that node; whenever all adjacent nodes are visited, the agent backtracks its path by one step. It is not hard to see that in a network of n nodes, after 2(n − 1) steps, the network will be traversed and the agent will have returned to its initial position. Here's the problem: what if some edges of the network die? The agent may try to backtrack along an edge that no longer exists. Although we could restart DFS every time this happens, this solution seems somewhat inelegant and inefficient.
One simple alternative mechanism for graph traversal is the following: the agent always travels to the closest unvisited node. This heuristic, which we call the nearest neighbor (NN) strategy, is the subject of our paper. It has been studied before under the guise of an approximation algorithm for the traveling salesman problem (that setting differs from ours only in that, at the end, the agent must return to its initial position). For each n ≥ 1, let the approximation ratio of NN be the least upper bound on the ratio COST (g)/COST (OP T ) where g is an NN traversal on an n-node graph, COST measures the number of steps, and OP T is the cheapest traversal of the graph. Abusing this definition slightly, for a fixed graph G and NN traversal g, we sometimes call COST (g)/COST (OP T ) an approximation ratio of NN on G.
The authors of [7] proved that the approximation ratio of NN is at most ( 1 2 + o(1)) log 2 n, and gave an infinite family of edge-weighted graphs where NN has an approximation ratio of at least ( 1 3 +o(1)) log 2 n. A simpler (and non-weighted) family was later found by [3] giving an approximation ratio of at least ( 1 4 + o(1)) log 2 n.

Our Contribution
The authors of [2] point out that the upper bound proof in [7] is "technical." In Section 2.1 we give a simple and new proof, but where the approximation ratio 1 2 log 2 n is replaced by ln n, which is slightly worse. Our approach is to bound the number of long steps in a traversal generated by NN. At the conclusion of the paper we mention another application of this technique. Remark: this paper was submitted to a conference and a referee pointed out that this proof technique can also be found in an analysis [1] by Alon and Azar of the Imase-Waxman online minimum Steiner tree heuristic.
We also improve the best known lower bound and show a family of (non-weighted) graphs upon which NN has an approximation ratio of at least ( 1 2 + o(1)) log 2 n. This appears in Section 2.2. With slightly more work, and using the upper bound from [7], this establishes that the approximation ratio of NN is ( 1 2 + o(1)) log 2 n. In Section 3, we analyze a simple distributed implementation of the NN heuristic. If there are no faults, then the algorithm always visits all nodes within O(n log n) time. However, as our introduction suggests, we are interested in what happens when faults are allowed. To our knowledge, ours is the first such analysis. We allow edges to be destroyed over time, but no edges are ever added to the graph or restored. We prove an O(n 2 ) upper bound on the time before the distributed NN algorithm terminates (i.e., until every node remaining in the agent's connected component is visited).
Finally, in Section 3.2, we give a result which indicates that NN is in some sense optimal. We show that for every strategy that an agent could use, there is an edge failure pattern which forces the agent to take at least n 2 steps. Hence NN uses the least number of steps (in the worst case) of any heuristic, up to a constant factor. This is not true of DFS with the "restart when you cannot backtrack" modification; see Appendix C.

Static Graphs
In this section, we assume that the graph G = (V, E) does not change over time. For any two nodes u and v, their distance d(u, v) denotes the minimum number of edges in any u-v path. The nearest neighbor heuristic is shown below (Algorithm 2.1). The algorithm takes a cost function c as input, so if we only want to count the number of steps taken by the agent, then we would take c = d. We consider only symmetric cost functions in this paper, in other words, we assume c(u, v) = c(v, u) for all nodes u, v ∈ V. Algorithm 2.1 NN(G, c): produces a nearest neighbor traversal v 1 is the initial location of the agent for i from 2 to n do let v i be any node in V \{v 1 , . . . , v i−1 } such that c(v i−1 , v i ) is minimized 2 2 2 1 2 X Figure 1: Take X → ∞ in the diagram above. The cheapest traversal has cost 5, but as indicated by the arrows, there is an NN traversal of cost X + 3. So without the triangle inequality, the approximation ratio of NN is unbounded.
A traversal is any permutation of the vertex set V. We call any sequence (v 1 , . . . , v n ) that can be produced by the above algorithm a nearest neighbor traversal.

Upper Bound
A vertex sequence x = (x 1 , . . . , x k ) has cost x defined by We say that a function c satisfies the triangle inequality if c(u, v) ≤ c(u, w) + c(w, v) for all nodes u, v, w. The triangle inequality may be equivalent stated as: for a given u-v path, replacing that path by the single edge uv (sometimes called short-cutting) doesn't increase the cost. Note that d satisfies the triangle inequality. The precise statement of the main theorem of this section is as follows.
Theorem 2.1. Suppose c is a non-negative integer-valued function that is symmetric and satisfies the triangle inequality. Then the approximation ratio of NN(G, c) is at most (1 + ln(n − 1)). Now when c = d (i.e., the cost is the number of agent steps) then a DFS traversal has cost at most 2(n − 1), and hence in this case Theorem 2.1 implies that NN always returns a traversal of cost at most O(n log n). We remark that the triangle inequality is necessary here to get a performance bound that depends only on n, as exemplified in Figure 1.
Hereafter we fix the number n of vertices, a cost function c that satisfies the triangle inequality, and a traversal (g 1 , . . . , g n ) generated by NN. Define λ j to be the number of pairs of consecutive nodes with cost at least j between them: By switching the order of summation, we see that the NN traversal's cost is precisely the sum of all λ j : Lemma 2.2. Let P = (P 1 , . . . , P k ) be a partition of V and suppose for each k, for any two nodes Proof. Suppose that c(g i , g i+1 ) > D and let g i be contained in class P j of the partition. We claim that g i was the last node of P j visited by the agent. Otherwise, if x ∈ P j \{g 1 , . . . , g i }, then after reaching g i the agent chose g i+1 such that c( , contradicting the fact that the agent makes greedy choices. Thus for each of the k parts P j there is at most one node g i in P j such that c(g i , g i+1 ) > D. Furthermore, let P j be the part containing g n , and we see d(g i , g i+1 ) < D for each g i ∈ P j . The lemma then follows.
. . , o n ) be a traversal of optimal cost C := o . By a short-cutting argument it is easy to see that c(o i , o j ) ≤ C for all vertices o i , o j ∈ V and hence λ j = 0 when j > C. Moreover, we obtain the following bound on λ j for other values of j.
Proof. By Lemma 2.2, it suffices to exhibit a partition of V into at most C/j + 1 parts, such that the pairwise costs within each part are at most j − 1. We can do this by breaking o into paths of length about j − 1 each. Define a(1) = 1 and iteratively compute integers a(i) ≤ n for i = 2, 3, . . . such that This is continued as long as possible, that is, until some k satisfies Note a is a strictly increasing sequence, so k is well-defined. Let a(k + 1) = n + 1 and define Note that the k sets P i partition V. Furthermore, using the triangle inequality in a short-cutting argument, it is easy to see that c(u, v) < j for each u, v ∈ P i . Intuitively, each P i accounts for a portion of o of length j, so we would expect o /j = C/j parts plus a remainder. Formally, using the definition of C and Equation (3), we have so k, the number of parts, is at most C/j + 1, as needed.
Finally, we estimate the resulting bound on the length of g, and hence prove Theorem 2.1. (1) we have λ i ≤ n − 1 for all n. Further, recall that λ j = 0 for j > C. We may assume without loss of generality that n − 1 divides C, as otherwise we can increase c uniformly by a factor of n − 1. We apply Equation (2) and then Lemma 2.3, obtaining

Proof of Theorem 2.1. From Equation
Thus, as claimed, the cost of g is at most (1 + ln(n − 1)) times the cost of o.
Let m (resp. M ) denote the minimum (resp. maximum) value of c(u, v) over all pairs {u, v} ⊂ V. We can tighten Theorem 2.1 in some cases and show that the approximation guarantee of NN depends logarithmically on the aspect ratio α := M/m : In comparison, Monnot [5] showed that in the absence of the triangle inequality, NN has approximation ratio 1+α 2 + o(1).

Lower Bound
In this section we describe a new family of graphs upon which NN has an approximation ratio of at least ( 1 2 + o(1)) log 2 n. We remark that the original lower bound of [7] could not be realized as the distance function d of any unweighted graph, but ours (like the example from [3]) can be.
We call the family layered ring graphs because of their shape. The layered ring graphs are denoted LR k (2 m ) where k ≥ 0 is the number of layers and m ≥ 1 is a size parameter. The basic idea is that the agent in the nearest neighbor algorithm can be forced to walk "around" the ring k times, once for each layer.
Each vertex in LR k (2 m ) is assigned a position p(v) ∈ {0, 1, . . . , 2 m } and we define two nodes u, v to be adjacent precisely when p(v) − p(u) ∈ {±1, 0} (mod 2 m + 1). Every layered ring graph includes the backbone vertices b 0 , b 1 , . . . , b 2 m whose positions are p(b i ) = i. It follows that every layered ring graph is hamiltonian, since starting at b 0 we can visit all vertices in position 0, then take an edge to b 1 and subsequently visit all vertices in position 1, and so forth until we return from the last vertex at position 2 m to b 0 .
For notational convenience, we fix m at this point and use only k as a parameter; so we omit m and write LR k instead of LR k (2 m ). The first layered ring graph LR 0 consists of only the backbone. Each ring graph LR k , k > 0 is constructed from the previous one LR k−1 by the addition of a layer.
We'll show that on LR k , the agent can walk around the ring k times, and hence the NN heuristic can return a traversal of cost about k · 2 m . As we will make precise in Lemma 2.8, when k is roughly equal to m/2, we'll have |V (LR m/2 )| = 2 m (1 + o(1)); but since LR m/2 is hamiltonian, we get an approximation ratio of at least We are about to define a sequence L 1 , L 2 , . . . , of layers. We say that a, b are L i -neighbors if L i ∩ {a, . . . , b} = {a, b}, and we denote this relation by N i (a, b) where a < b.
Definition 2.5. Define the first layer L 1 as follows: For i ≥ 1, define the (i + 1)st layer L i+1 as follows: Proof. We will show that the agent may visit the nodes in the following order: backbone, layer k, layer k − 1, and so on, visiting layer 1 last. Each layer, and also the backbone, is visited in increasing order of position.
In the backbone, c(b i , b i+1 ) = 1 for 0 ≤ i < 2 m , and so these steps are valid for the NN heuristic as all pairwise distances are at least 1. Similarly, as c(b 2 m , ℓ k 0 ) = 1 and c(ℓ i 2 m , ℓ i−1 0 ) = 1 for k ≥ i > 1, it remains only to show that the intra-layer steps are valid. Precisely, for each k ≥ i ≥ 1 and for each a, b such that N i (a, b), say that a node Our goal is to show that no bad nodes exist. Fix a, b, i as above. First, consider the nodes of layer i that are not visited before ℓ i a . Since we visit layer i in increasing order of position, no node of the form x = ℓ i j , j ≥ b is bad unless j > 2 m + 1 + a − (b − a). But from Definition 2.5 it follows easily that b ≤ 2a, and so no bad nodes exist in layer i.
It remains to show that no bad nodes exist in layers i − 1, i − 2, . . . , 1. If b = a + 1 then this is trivial. Otherwise, by the definition of layers, it must be that In Appendix A, we show a simple way to count the number of nodes in LR k (2 m ), obtaining: In what follows, we write a ∼ b to mean that a = b(1 + o(1)). Proof. First note that |V (LR k (2 m )| > 2 m . For an upper bound on |V (LR k (2 m )|, Equation (4) gives In turn, we can bound this expression by reinterpreting the sum using a binomial random variable and applying a Chernoff bound [6,Thm. 4.2]. Namely, Then recalling Equation (5), we see that |V (LR k (2 m )| = 2 m + o(2 m ) as claimed.
Proof. The upper bound in [7] that we have mentioned implies that the left-hand side of Equation (6) is at most 1/2. Now pick any δ > 0 and consider the family of graphs in Lemma 2.8. The number n of vertices satisfies n ∼ 2 m . By Claim 2.7 each graph in the family admits an NN traversal of cost (2 m + 1)(k + 1) − 1 ∼ n log 2 (n)/(2 + δ). But each graph is hamiltonian and so has optimal traversal cost n − 1. Hence ar(n) log 2 (n)/(2 + δ). As m → ∞ so does n → ∞, and by taking m → ∞ and δ → 0 we obtain Equation (6).
With a little more effort, we can replace the lim sup in the above equation by lim, or in other words we can establish that ar(n) ∼ 1 2 log 2 n. We defer the details to Appendix B.

Network Implementation with Failures
As we stated in the introduction, one motivation for the nearest neighbor algorithm is its potential usefulness in computer networks with edge failures. We give a simple implementation below (Algorithm 3.1). The variable pos represents the position of the agent. Each node v keeps a flag v.vis to indicate whether it has been visited, and a number v.dist which represents an estimate of the distance from v to the nearest unvisited node. Line 5 determines the shortest paths to unvisited for each node v such that v.vis = true, in parallel do 5: let v.dist := 1 + min{u.dist | u = v or uv ∈ E} 6: if pos has a neighbor u such that u.dist < pos.dist then some edges may be deleted nodes, and Line 6 makes the agent travel along these paths. For future reference, we need the following remarks: R1. For each node v, the value v.dist is nondecreasing with time.
R2. At all times, v.dist is at most the actual distance to the closest unvisited node.
Remark R1 can be proved by induction on the number of iterations elapsed, and remark R2 can be proved by induction on the distance to the closest unvisited node. Say that a node is explored the first time that the agent visits it. If no failures occur, it is not too difficult to show that the agent generates a greedy tour g in the following way: after exploring g i , it remains motionless for d(g i , g i+1 ) rounds, and in the following d(g i , g i+1 ) rounds it travels directly to g i+1 . Using Theorem 2.1, we find that g = O(n log n), so all nodes are visited within O(n log n) iterations. The purpose of this section is to show that edge failures can dramatically increase the time complexity of network traversal.
We considered a variant of the above implementation where each node instantly knows the actual distance to the nearest unvisited node, but the results were essentially the same as what we present here.

Upper Bound
If the graph becomes disconnected due to edge failures, then it may not be possible for the agent to visit all of the nodes. Given this fact, and furthermore that the agent may not initially know the value of n, how can we detect termination? We use the following idea: the agent keeps a count exp of how many nodes it has explored so far, and once pos.dist > exp, (using R2) there can be no more reachable unvisited nodes. Using this as the definition of termination, we now upper bound the algorithm's running time. Proof. To simplify the arguments, suppose we do not permit any dist label to exceed n + 1 (that is, once it hits this value, it does not increase further). It is not hard to see that this does not affect the observed behavior of the algorithm.
First, we claim there are at most O(n 2 ) iterations in which the agent moves. When the agent moves, the value pos.dist decreases by at least 1. However, the value pos.dist can only increase O(n 2 ) times, since pos can be any of the n nodes, and each node's dist label increases at most n + 1 times (by R1).
Second, we can also show there are at most O(n 2 ) iterations in which the agent does not move.
Claim 3.2. If the agent does not move in a given iteration, then either the algorithm terminates in that iteration, or v.dist increases for some node v.
Proof. For the sake of contradiction, consider a non-final iteration in which v.dist does not increase for any node v. By induction on t, we can show that every node v at distance t from the nearest unvisited node has v.dist = t, and if all nodes in the connected component of v are visited, then v.dist = n + 1. But this is a contradiction, for it is easy to see that the agent would have taken a step towards a nearest unvisited node.
Since there are n nodes and each nodes's dist label can increase at most n + 1 times, we see that the agent remains still in O(n 2 ) iterations.
In Appendix C we show, in contrast, that DFS with restarting (as described in the introduction) may take Ω(n 3 ) time.

Lower Bound
The upper bound of Theorem 3.1, it turns out, has a lower bound that matches it up to a constant factor. However, the lower bound doesn't depend on any properties of the NN heuristic. Rather, we can show that any heuristic for visiting all nodes must take at least n 2 steps, if a suitable pattern of edge deletions occurs.
We express this idea as a game: the objective of the agent is to be in a connected component of G where every node has been visited, and an adversary chooses the edges to delete, and wants to Figure 3: A picture of phase i. The agent (denoted by ⋆) is trying to visit node x 1 , and the adversary wants to avoid this. In each iteration, the agent moves to an adjacent node (denoted by the arrow) and then the adversary deletes some edges (denoted by dashed lines ). Shaded figures are cliques.
foil the agent for as long as possible. An adaptive adversary -one that can see the current state of the network in each iteration before deciding what to delete -is arguably the most powerful adversary possible. We phrase our proof using an adaptive adversary. Note however that for a deterministic traversal heuristic, a non-adaptive adversary is just as powerful as an adaptive one, since the adversary can optimize its behavior ahead of time by simulating the agent.
Here is what we, as the adversary, should do. The graph G is originally a complete graph on n vertices. We wait until the agent has visited n − 1 nodes; let v be the (n − 1)st node visited, and x 1 be the last remaining unvisited node. We then destroy the edge vx 1 . As a result, the agent cannot visit x 1 in the next step. Similarly, as soon as the agent moves to any other node y such that y is adjacent to x 1 , we destroy the edge yx 1 . We continue this until there are precisely 2 nodes z 1 and z ′ 1 adjacent to x 1 , and we wait for the agent to visit one or the other (clearly the algorithm cannot terminate before then, since the agent is connected to the unvisited node x 1 ). Without loss of generality, assume the agent steps to z 1 before z ′ 1 . Then we perform two edge deletions: we remove both x 1 z 1 and z 1 z ′ 1 . Define x 2 := z ′ 1 . Intuitively, we now want to keep the agent at distance 2 or more from x 1 for as long as possible.
In general, the ith "phase" begins when x i is defined. Each time the agent moves onto a node y adjacent to x i , we delete yx i . This continues until there are two nodes other than x i−1 adjacent to x i , which we call z i and z ′ i . W.o.l.o.g. let the agent reach z i first, and at that point, we delete both x i z i and z i z ′ i . We also define x i+1 := z ′ i and the (i + 1)st phase begins. We depict a generic phase in Figure 3.
This can be continued until the end of the (n − 3)rd phase, at which point the nodes consist of x 1 , . . . , x n−3 , z ′ n−2 , y, z n−2 with the agent at z n−2 . The remaining graph is a path, and the agent needs to take (n − 1) more steps to complete its traversal. In the ith phase, the agent has to move onto (n − i − 2) distinct nodes. There are at least (n − 2) additional steps at the beginning before we define x 1 . Hence the total number of steps is at least

Discussion
A nearest neighbor tree, introduced in [4], is any tree that can be produced by Algorithm 4.1 shown below. (Note that it always produces a tree.) Using the technique of Section 2.1, we are able to get a simpler proof of the main approximation result from [4].
Algorithm 4.1 Algorithm for construction of a nearest neighbor tree each node v is assigned a unique rank r(v) for each node v such that v is not the maximum-rank node (in parallel) do let w be a node such that Proof. Let λ j denote the number of edges in T of cost j or more. Let OP T be a minimum spanning tree and let o be a depth-first search traversal of OP T ; it follows that o ≤ 2c(OP T ). As in the proof of Lemma 2.3, for any integer j, we can partition V into o /j + 1 parts P i such that in each part, every pair of nodes is at most a distance j − 1 apart. In each part P i , we claim that at most one node in P i tries to form a connection of cost j or greater. Indeed, only the maximum-rank node u in P i can do so, as all others can connect to u instead at cost at most j − 1. As before we find that λ j ≤ o /j which permits us to use the same integral estimate as in the proof of Theorem 2.1. We get There is an interesting and difficult related problem which we were unable to solve. Consider our original problem of counting the number of steps taken by an agent executing the NN heuristicin other words, assume that c is the distance function for some (unweighted) graph. The costly NN traversal of layered ring graphs, and similarly the NN traversal of the example from [3], both perform a lot of arbitrary tie-breaking. If we break all ties randomly, then the performance seems to improve. Is it possible that this would improve the approximation ratio of NN to O(1)? (An observation in [7] shows in the case of edge-weighted graphs, random tie-breaking doesn't help.) Similarly, when the edge-deleting adversary is not adaptive, does randomization help in the distributed setting? backbone nodes).

B Approximation Ratio Interpolation
We need to do some interpolation to show that lim n→∞ ar(n)/ log 2 (n) = 1/2.
The problem is that as m increases by one, the graphs LR (m−1)/(2+δ) (2 m ) roughly double their number of vertices, leaving a large gap. For this purpose, we may generalize the construction of layered ring graphs in the following way. We replace the size parameter 2 m by a size parameter ν, and no longer insist that L i -neighbors differ by a power of 2. We redefine the layers in the following way.
Having defined the layers, we define the layered ring graphs LR k (ν) using Definition 2.6 exactly as before. It is straightforward to see that this indeed generalizes our previous construction. That is, if ν = 2 m , then LR k (ν) = LR k (2 m ) for all k. We omit the straightforward proof of the following claim.