A lower bound of 4 for online graph exploration
July 16, 2026
Abstract
In the online graph exploration problem, a single agent needs to visit every vertex of an initially unknown graph, which is learned over time in an online fashion, and return to its starting position. We prove that the competitive ratio of this problem is at least 4, improving on the previously best known lower bound of 10/3. A key ingredient of our proof is showing that several restrictions can be imposed on the agent’s behavior without affecting the competitive ratio. As a byproduct, we also obtain that certain graph properties, such as the triangle inequality or being subcubic, can be assumed without affecting the competitive ratio.
1 Introduction↩︎
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs [1]. In this setting, a single agent has to traverse an undirected, connected graph \(G=(V,E,w)\) with non-negative edge weights \(w\colon E \to \mathbb{R}_{\geq 0}\). We assume that every vertex and every edge has a unique identifier. Importantly, the graph is initially unknown and is learned by the agent over time in an online fashion. More precisely, upon visiting a vertex for the first time, the agent learns the identifiers of the adjacent vertices as well as the identifiers and weights of the corresponding edges. The cost incurred when traversing an edge is simply its weight. The objective is to visit all vertices and return to the starting position, while minimizing the total cost. In this work, we give an improved lower bound on the performance guarantee of any deterministic algorithm for this problem.
As usual in online optimization, we measure the quality of an algorithm in terms of competitive analysis. Given an algorithm \(\mathrm{\small Alg}\) for exploration, we denote by \(\mathrm{\small Alg}(G,v)\) the total cost incurred on graph \(G\) with starting vertex \(v\). By \(\mathrm{\small Opt}(G)\), we denote the offline optimum cost, that is, the length of a shortest TSP tour. Note that the cost incurred by an online algorithm may depend on the starting position, whereas the offline optimum cost does not. For \(\rho\geq 1\), we say that \(\mathrm{\small Alg}\) is \(\rho\)-competitive if there exists a constant \(C\in \mathbb{R}_{\geq 0}\) such that \(\mathrm{\small Alg}(G,v)\leq \rho \cdot \mathrm{\small Opt}(G)+C\) for every graph \(G\) and starting vertex \(v\) of \(G\). If \(C=0\) is possible, we say that \(\mathrm{\small Alg}\) is strictly \(\rho\)-competitive. The (strict) competitive ratio of \(\mathrm{\small Alg}\) is defined by \(\inf \{\rho\geq 1: \mathrm{\small Alg}\text{ is (strictly) \rho-competitive}\}\) and the (strict) competitive ratio of the problem is defined by \(\inf\{\rho\geq 1: \text{ there exists a (strictly) \rho-competitive algorithm}\}\). While in general, the strict competitive ratio may be larger than the competitive ratio, we prove in this work that these values coincide for online graph exploration ([obs:exploration-competitive-ratio]).
Arguably, the most important question in the study of the online graph exploration problem is whether there exists a constant-competitive algorithm. This question was proposed by Kalyanasundaram and Pruhs in 1994 [1] and is still open. The best known upper bound on the competitive ratio is \(\mathcal{O}(\log n)\), where \(n\) denotes the number of vertices [2], and, prior to our work, the best known lower bound was 10/3 [3]. Constant upper bounds are only known when restricting the problem to certain graph classes, such as graphs excluding a fixed minor (including planar, bounded-genus, and bounded-treewidth graphs) [4], or graphs that only use a constant number of different weights [5].
Our results.
Our main result is an improvement on the best known lower bound on the competitive ratio of the online graph exploration problem. Here, a graph is subcubic if all of its vertices have degree at most 3.
theoremexplorationlowerbound The competitive ratio of the online graph exploration problem is at least 4, even when restricted to subcubic planar graphs.
Prior to our work, the best known lower bound was 10/3 [3]. While our construction is closely related to that in [3], we provide a refined version that allows for better estimates on the backtracking cost of an agent, that is, the cost incurred when traversing already explored parts of the graph. Another key ingredient in proving [thm:4-lower-bound] is showing that several restrictions can be imposed on the agent’s behavior without affecting the competitive ratio. As a byproduct of the restrictions on the agent’s behavior, we obtain that certain assumptions can be made about the underlying graph itself without decreasing the competitive ratio. The following result summarizes the most important of these restrictions.
Proposition 1. In the online graph exploration problem, we can assume (any subset of) the following restrictions without affecting the competitive ratio of the problem.
Upon visiting a new vertex, the agent only learns the unique identifiers and weights of incident edges (but not the identifiers of neighboring vertices).
The graph is subcubic.
The edge weights fulfill the triangle inequality, i.e., \(w(e)\leq d(u,v)\) for every edge \(e=\{u,v\}\in E\). Here, \(d(\cdot,\cdot)\) denotes the shortest path distance.
The agent is given the total number of vertices beforehand.
We hope these insights will be useful for future research on online graph exploration beyond the lower bound construction presented here.
Related work.
Several algorithms have been proposed for the online graph exploration problem. The arguably most natural approach is the nearest neighbor algorithm, where, in each step, the agent greedily selects a closest unexplored vertex. Rosenkrantz, Stearns and Lewis proved that the competitive ratio of this algorithm is \(\Theta(\log n)\) [2]. Interestingly, the lower bound of \(\Omega(\log n)\) is already achieved on unweighted planar graphs [6] and on trees [7].
Another approach is given by hierarchical depth-first search (hDFS), which was introduced by Megow, Mehlhorn, and Schweitzer [5]. This algorithm is constant-competitive on graphs only using a bounded number of different weights and \(\Theta(\log n)\)-competitive on general graphs, where the lower bound of \(\Omega(\log n)\) is already achieved on a path. The algorithm \(\mathrm{\small Blocking}\) was introduced in [5] and builds on the algorithm Shortcut by Kalyanasundaram and Pruhs [1]. In the latter work, the authors showed that the algorithm has competitive ratio at most 16 on planar graphs. In [5], Megow, Mehlhorn, and Schweitzer extended this by proving that \(\mathrm{\small Blocking}\) is constant-competitive on bounded-genus graphs, and in [4], this is extended even further to graphs excluding a minor. In [8], Eberle et al. revisited the nearest neighbor approach with learning augmentation.
Miyazaki, Morimoto, and Okabe showed that the competitive ratio of online graph exploration is precisely \((1+\sqrt{3})/2\) on cycles and 2 on unweighted graphs [9]. Other graph classes on which the problem has been studied include tadpole graphs [10], unicyclic graphs [7], [11], and cactus graphs [7].
In terms of lower bounds, the first notable result was given in [9], where the authors proved that the competitive ratio of online graph exploration on unweighted graphs is at least 2, which matches the trivial upper bound of 2 achieved by DFS. Dobrev, Královič, and Markou gave a first weighted construction, proving a lower bound of 2.5 [12]. Birx, Disser, Hopp, and Karousatou built on this construction, proving a lower bound of 10/3 [3]. In this work, we further improve the lower bound to 4.
There are numerous other variants of graph exploration studied in the literature, such as exploration of directed graphs [13]–[16], assuming that the agent has limited memory [17], [18] but can use pebbles [19], or exploration with a team of agents [20]–[24].
2 Equivalent problems↩︎
In this section, we prove that we can impose several restrictions on the agent’s behavior that will turn out to be useful for our proof of [thm:4-lower-bound]. First, we introduce some notation used throughout the paper. During the course of exploration, we say that a vertex is explored if it has been visited by the agent and it is learned if one of its neighbors or the vertex itself is explored. A boundary edge is an edge with one explored and one unexplored endpoint. By convention, we denote boundary edges by \(e=(u,v)\), where \(u\) is explored and \(v\) is unexplored. Otherwise, we denote edges by \(e=\{u,v\}\) as usual for undirected graphs. For two learned vertices \(u\) and \(v\), we denote by \(d(u,v)\) the length of a shortest path from \(u\) to \(v\) whose internal vertices are explored. In other words, this is the smallest upper bound on the distance that the agent is aware of.
2.1 The adversary model↩︎
It is often useful to view an online optimization problem as a game: one player selects an instance and reveals it piece by piece to the other player, who must make online decisions. In this setting, the latter player is the online algorithm, and the first player is referred to as the adversary. For deterministic online algorithms, it does not matter whether the adversary chooses the entire instance beforehand and reveals it piece by piece, or whether the adversary adapts the unrevealed parts based on the algorithm’s decisions: By definition, if a deterministic algorithm is presented with the same instance \(I\) twice, it will make the same decisions in both runs. If there exists another instance \(I'\) that differs only in parts not yet revealed, the algorithm cannot distinguish between \(I\) and \(I'\), and thus behaves identically on both. Since a\(\rho\)-competitive algorithm must be \(\rho\)-competitive on every instance, the adversary can choose whether the algorithm is operating on \(I\) or \(I'\) once the distinction becomes relevant.
Finding strategies for the adversary can be seen as a “dual” online problem, called the adversary problem: Here, we have to construct an instance for the given online problem, while receiving information about the algorithm’s decisions over time in an online fashion, without being able to modify the parts of the instance already revealed. The objective is to maximize the ratio \(\mathrm{\small Alg}(I)/\mathrm{\small Opt}(I)\), where \(I\) is the instance constructed by the adversary. It is immediate that the optimal value achievable in the adversary problem coincides with the strict competitive ratio of the online problem. Importantly, note that this model of an adaptive adversary is only applicable when considering deterministic algorithms.
In the context of online graph exploration, the adversary problem can be stated as follows: We have to construct a weighted graph \(G\) adaptively and the counterplayer is an agent that, in each step, moves to a new unexplored vertex. Once a vertex \(v\) is explored, we have to irrevocably determine the identifiers of its adjacent vertices as well as the identifiers and weights of the corresponding edges. The objective is to maximize the ratio of the total distance traveled by the agent and the length of a shortest TSP tour.
Throughout this paper, we will often use this adversarial perspective to prove lower bounds or equivalences between online problems. In particular, it allows us to show the following.
observationobservationcompetitiveratio Let \(\rho\in \mathbb{R}_{\geq 1}\). There is a \(\rho\)-competitive algorithm for online graph exploration if and only if there is a strictly \(\rho\)-competitive algorithm.
Proof. By definition, every strictly \(\rho\)-competitive algorithm is also \(\rho\)-competitive. For the other direction, assume that there is no strictly \(\rho\)-competitive algorithm. Then there exists an adversarial strategy \(\cal A\) that constructs, for every exploration algorithm \(\mathrm{\small Alg}\), a graph \(G\) with starting vertex \(v\), such that \(\mathrm{\small Alg}(G,v)\geq \rho\cdot \mathrm{\small Opt}(G) + \varepsilon\) for some \(\varepsilon>0\). Consider the following adversarial strategy: Let the starting vertex \(v\) be adjacent to \(M\) vertices \(v_1, \dots, v_M\) via edges of weight 0. Treat each \(v_i\) as the starting vertex of a separate exploration instance and, for each, apply strategy \(\cal A\). Let \(G_1, \dots, G_M\) denote the resulting graphs. Note that they are not necessarily equal because the algorithm might choose to follow a different strategy when facing the same situation multiple times. However, the adversary is able to build a suitable graph for every possible change of strategy.
Observe that we can treat these as \(M\) instances of exploration because during exploration of \(G_i\), the agent does not gain any information about \(G_j\) for \(j\neq i\). We charge the cost incurred in graph \(G_i\) on the \(i\)-th problem and let \(\mathrm{\small Alg}_i\) denote the strategy followed in graph \(G_i\). We obtain overall a graph \(G\) with \[\mathrm{\small Alg}(G,v)=\sum\limits_{i=1}^M \mathrm{\small Alg}_i(G_i,v_i)\geq M\varepsilon+ \rho\cdot \sum\limits_{i=1}^M \mathrm{\small Opt}(G_i)=\rho \cdot \mathrm{\small Opt}(G)+M\varepsilon.\] Letting \(M\to \infty\), this shows that no \(\rho\)-competitive algorithm exists. ◻
In the remainder of the paper, we therefore use the competitive ratio of the problem and the strict competitive ratio of the problem interchangeably. In the next subsection, we further make use of the adversary model to prove that some variants of the online graph exploration problem are equivalent.
2.2 The restricted online graph exploration problem↩︎
We prove that we can impose several restrictions on the agent’s behavior without affecting the competitive ratio of the graph exploration problem. This will later be useful for our lower bound construction. In addition, these restrictions can serve as a “sanity check” when developing new algorithms: A sensible algorithm should not rely on any information or capabilities that we restrict in the following.
More precisely, consider the online graph exploration problem, where the agent is additionally restricted, and the adversary is relaxed, as follows.
Upon visiting a new vertex, the agent only learns the unique identifiers and weights of incident edges (but not the identifiers of neighboring vertices).
The graph may have parallel edges.
When the agent traverses a boundary edge \(e=(u,v)\), a new boundary edge \(e'=(u,v')\) of weight \(w(e)\) may appear incident to \(u\).
If there are two boundary edges \(e=(u,v)\) and \(e''=(u',v')\) with \(d(u',v)< w(e'')\), the agent must not traverse edge \(e''\).
If there are two boundary edges \(e=(u,v),e'=(u,v')\) incident to the same vertex \(u\) with \(w(e)=w(e')\), the adversary may decide which of the two edges the agent traverses first.
We call this version the restricted online graph exploration problem. Note in the above that none of these restrictions apply to the agent in the offline optimum, e.g., in the situation R5), the offline agent may traverse boundary edges in another order.
Next, we observe that these adaptations do not make the exploration problem harder in the following sense. While some of the next result is folklore, we provide a proof for the sake of completeness. For convenience, we treat any super-constant competitive ratio, i.e., depending on some graph parameters such as the number of vertices, as infinity.
observationrogep The competitive ratio of online graph exploration is equal to the competitive ratio of restricted online graph exploration.
Proof. It is immediate that a \(\rho\)-competitive algorithm for the restricted online graph exploration problem is also \(\rho\)-competitive for online graph exploration. For the other direction, assume there exists an adversarial strategy \(\cal A\), constructing, for every algorithm for the restricted problem, a multigraph \(G\) with starting vertex \(v\) such that \(\mathrm{\small Alg}(G,v) > \rho \cdot \mathrm{\small Opt}(G)\). We give an adversarial strategy that achieves the same lower bound of \(\rho\) in the classical online graph exploration setting. For this, we construct a graph that mimics the multigraph constructed by \(\cal A\) and argue that, in this graph, any movement of an agent for exploration mimics a movement of some agent for restricted exploration.
First, we argue that R1) and R2) can be assumed without loss of generality. The main idea is to replace each vertex \(v\) that \(\cal A\) introduces by a suitable graph \(G_v\) called a gadget, in which we set all edge weights to 0, and connect all edges incident to \(v\) to different vertices of \(G_v\) (see 1). For instance, we can set \(G_v\) to be a binary tree with at least \(d_v\) leaves, where \(d_v\) is the degree of \(v\), and connect the edges to its leaves.
From the perspective of the induced metric space of the resulting graph, all vertices in \(G_v\) represent essentially the same vertex \(v\) because their pairwise distances are 0. In particular, we can assume that, if the agent explores any vertex of \(G_v\), it immediately explores all vertices of \(G_v\) and thus, learns about all edges incident to vertices of \(G_v\). Moreover, this construction does not affect the offline optimum cost.
The key difference is the following: In the resulting graph, the agent cannot tell whether two boundary edges lead to the same gadget \(G_v\). In other words, learning the identifiers of the endpoints of boundary edges effectively reduces to learning only the identifiers of the boundary edges themselves. Moreover, parallel edges between vertices \(u\) and \(v\) in the graph constructed by \(\cal A\) can be modeled as multiple edges between leaves of \(G_u\) and \(G_v\). This shows that we can assume without loss of generality R1) and R2). We argue that the remaining properties can also be assumed without loss of generality using that we have already established this for R1) and R2). For the remainder of the proof, we denote boundary edges by \(e=(u, \cdot )\) and, once the agent decides to traverse it, the adversary chooses its endpoint.
The statement that we can assume R5) now immediately follows from R1): both edges have the form \(e=(u,\cdot)\) of the same weight, so the agent cannot distinguish between them.
For R3), we use the following construction: for every boundary edge \(e=(u,\cdot)\) introduced by \(\cal A\), we instead introduce a sufficiently large number of boundary edges of weight \(w(e)\), each incident to \(u\), which we call a bundle. If the agent traverses \(e\), this corresponds to traversing one of the edges of the corresponding bundle. Upon the traversal of an edge \(e=(u,v)\) in the bundle, the adversary can decide whether all edges of the bundle lead to vertex \(v\), or only \(e\) leads to vertex \(v\) and all other edges of the bundle lead to other vertices with not yet known endpoints, i.e., they remain boundary edges. Note that the latter corresponds to the capability of \(\cal A\) in R3).
For property R4), if the agent traverses a boundary edge \(e'=(u',\cdot )\) even though a boundary edge \(e=(u,\cdot)\) exists with \(d(u',u)+w(e)<w(e')\), the adversary lets \(e'\) and \(e\) have the same endpoint \(v\) and it introduces a new boundary edge incident to \(u'\) of weight \(w(e')\) (using R3). This corresponds to forcing the agent not to traverse \(e'\): If the agent decides otherwise, the outcome remains the same as if it had chosen to traverse \(e\), but it incurs a higher cost. ◻
The main idea for the proof was to replace each vertex by a binary tree and connect the edges to its leaves (see 1). If a graph class is closed under this operation, we say that it is closed under tree replacement. This property holds, for example, for the classes of all graphs, planar graphs, bounded-genus graphs, graphs excluding a non-planar minor, and graphs only using a bounded number of different edge weights including 0. Building on the last observation, we obtain equivalence results for further variants of the problem, which we summarize in the following.
corollarycorequiv The competitive ratios of the following problems coincide.
online graph exploration,
restricted online graph exploration,
restricted and classical online graph exploration on subcubic graphs,
restricted and classical online graph exploration on graphs fulfilling the triangle inequality,
each of the above problems with the relaxation that the agent is given the total number of vertices at the beginning of exploration.
The equivalence still holds when restricting all of the problems to the same graph class closed under tree replacement.
Proof. Equivalence of a) and b) is precisely [obs:exploration-restrictions] and c) follows from the fact that the graphs constructed in the proof of [obs:exploration-restrictions] are subcubic. For d), assume that an input graph contains an edge \(e=\{u,v\}\) not fulfilling the triangle inequality, i.e., \(w(e)>d(u,v)\), where the distance is measured here in the final graph. As long as \(e\) is a boundary edge, there exists another boundary edge on the shortest path from \(u\) to \(v\) that is cheaper for the agent to traverse. Due to property [property:exploration-restriction-triangle], \(e\) is never traversed so we can assume that the graph does not contain such edges.
For part e), let \(\mathrm{\small Alg}_N\) be the strategy that the agent follows when given the information that the final graph consists of \(N\) vertices and assume that \(\mathrm{\small Alg}_N\) is \(\rho\)-competitive on every graph on \(N\) vertices. Then \(\mathrm{\small Alg}_N\) is also \(\rho\)-competitive on every graph \(G\) on \(n\leq N\) vertices: The adversary can attach to the last explored vertex of \(G\) a path of \(N-n\) vertices using edges of weight 0 so that the agent technically operates on a graph on \(N\) vertices, however, its incurred cost on \(G\) equals the incurred cost in the modified graph. This shows that \(\mathrm{\small Alg}_N\) is also \(\rho\)-competitive on every graph on \(n\leq N\) vertices. For this reason, we can assume that \(\mathrm{\small Alg}_{N-1}=\mathrm{\small Alg}_N\) for every \(N\in \mathbb{N}_{\geq 2}\). We obtain that we can assume that the agent’s strategy is independent of the number of vertices, even when this information is given beforehand.
The last statement follows immediately from the fact that such a graph class is closed under the constructions in [obs:exploration-restrictions] and under attaching paths. ◻
This completes the proof of 1, which follows from [obs:exploration-restrictions] and [cor:exploration-restrictions].
We note that the results in this subsection are not applicable when proving super-constant bounds on the competitive ratio. For example, if one aims to prove that an algorithm has competitive ratio \(f(n)\) for some function depending on \(n\), one loses generality when assuming the above restrictions. This is because the constructions in the proof increase the number of vertices.
3 Overview of the proof of [thm:4-lower-bound]↩︎
To prove [thm:4-lower-bound], we have to do the following: We give an adversarial strategy that, given an algorithm \(\mathrm{\small Alg}\) fulfilling [property:exploration-restriction-endpoint]-[property:exploration-restriction-nochoice] and \(\varepsilon>0\), constructs a planar graph \(G\) with starting vertex \(v\) such that \(\mathrm{\small Alg}(G, v)/\mathrm{\small Opt}(G) \geq 4 - \varepsilon\). This implies that the strict competitive ratio of the restricted exploration problem on planar graphs is at least 4. Using [obs:exploration-competitive-ratio] and [cor:exploration-restrictions], this implies the statement of [thm:4-lower-bound].
Before giving the adversarial strategy in detail, let us introduce the main ideas behind it. Fix an algorithm \(\mathrm{\small Alg}\) for the restricted online graph exploration problem. When we refer to the agent, we mean the agent of this online algorithm. In contrast, the offline agent denotes the agent in an offline optimum solution. The graph \(G\) that we construct consists of subgraphs serving as building blocks, which we refer to as blocks. The agent will be forced to traverse almost every block in order to reach every vertex of the graph. Note that the cost incurred by the agent to traverse a block for the first time might differ from the cost of a second traversal, as the agent gains information during the first traversal that can be used later. Roughly speaking, we will arrange blocks such that every block is traversed once by the offline agent and twice by the online agent. Moreover, blocks will be built such that the agent pays three times as much as the offline agent for the first traversal.
We want to emphasize that the strategy of a block structure was already used in previous works on lower bounds for online graph exploration [3], [12]. Here, we use the same strategy for arranging the constructed blocks in the graph \(G\) as in [3]. The blocks that we define are based on the same ideas as in [3], [12], but we give a refined structure that allows for a stronger, and arguably simpler, analysis.
We informally describe the idea for the construction of a (single) block: Consider 2. The agent starts at vertex \(s\) and we estimate its incurred cost until it traverses a red edge (without requiring it to visit all vertices). By [property:exploration-restriction-nochoice], we can assume that the agent starts by exploring \(u_\mathrm{\small Alg}\), where it finds itself somewhere along a path of edges of weight 1. It then explores some of this path until the adversary decides to stop the process and we let \(w_k\) be the last explored vertex of the path. The other endpoint is then \(v_i\), which is not yet explored, but \(v_{i-1}\) is. The value of \(i\) depends on the algorithm’s behavior. Note that \(i\neq 1\) only occurs if the agent explores the path in “zigzag movements”, that is, if the agent changes direction before reaching an endpoint of the path. By [property:exploration-restriction-nochoice], we can assume that the agent has to explore \(v_i\) before it can traverse a red edge. Therefore, the agent has to travel along the edge of weight \(k\) to \(v_i\) and back before traversing a red edge. In contrast, the offline agent can visit all vertices by following the path \((s, v_i, \dots, v_1, u_\mathrm{\small Alg}, w_1, \dots, w_k, t_1\)).
When focusing on the red edges only, we observe the following behavior: Once the agent is located at \(w_k\), it incurs a cost of \(3k\) to traverse a red edge, whereas the offline agent only incurs a cost of \(k\) because it has explored \(v_i\) before \(w_k\). Intuitively speaking, this means that the agent pays three times as much for traversing a red edge as the offline optimum. Next, we recursively replace all edges of weight 1 in this graph by blocks of the same structure (with edge weights scaled down). This increases the fraction of edges for which the agent pays three times as much as the offline agent. In the limit, the agent incurs three times the cost of the offline agent for traversing the block.
Importantly, note that, during a second traversal, the agent does not have to use vertices \(v_1, \dots, v_i\), which makes the second traversal shorter. However, the cost incurred during the first traversal increases with \(i\), i.e., if the agent explores the path in “zigzag movements”. Therefore, in the analysis, we will carefully track these values. This is one of the key improvements over the work in [3]. In 4, we formally establish the notion of a block, the problem of traversing it, and the key values that need to be tracked. In 5, we then construct the blocks described above and prove that the agent incurs three times the cost of the offline optimum when traversing them.
Once we have established blocks, we arrange them in a graph as illustrated in 6, which is already used in [3]. The structure of this graph is motivated by a lower bound construction for the exploration problem on unweighted graphs, which can be used to prove a lower bound of 2 on this class. In this graph, the agent travels on some walk from \(v_\mathrm{s}\) to \(v_1\) (6), where it encounters three paths of blocks. Since it cannot distinguish between these paths, we may assume that the first path that is completely explored is the one that leads back to \(v_\mathrm{s}\). The agent then has to backtrack to \(v_1\) to make further progress. This behavior occurs in every cycle of the graph. The agent completes visiting all vertices at some position in the last cycle \(C^*\). After this, it has to return to the starting position, incurring additional cost. In total, we obtain that it traverses (almost) every block twice. By contrast, the offline agent traverses the upper half of each cycle first and then, starting from the last cycle, traverses the lower half of each cycle. It thus traverses every block precisely once. This construction is formalized in 6.
4 The block traversal problem↩︎
In this section, we formalize the problem of traversing a block, for which we introduce a new online problem, called the block traversal problem. Intuitively, it is a variant of online graph exploration, where the task is only to find the exit of a maze instead of exploring all of it.
An instance of the block traversal problem (see 2 for an example) consists of a weighted connected graph \(B\), called a block, together with a starting vertex \(s\) and two target vertices \(t_1, t_2\) (where \(s\), \(t_1, t_2\) are not considered to be part of \(B\)). The vertex \(s\) is connected to two different vertices of \(B\), called its algorithmic entry vertex \(u_\mathrm{\small Alg}\) and its optimal entry vertex \(u_\mathrm{\small Opt}\), via two edges of the same weight and we call these edges the algorithmic entry edge and optimal entry edge. The target vertices \(t_1\) and \(t_2\) are connected to the same vertex of \(B\), called its exit vertex \(u_\mathrm{Ex}\) and we call the corresponding edges the exit edges. By slight abuse of notation, by \(B\) we sometimes refer to the instance of the block traversal problem, instead of only the graph. In the block traversal problem, an exploration agent obeying rules [property:exploration-restriction-endpoint]-[property:exploration-restriction-nochoice] is initially located in \(s\) and is tasked to reach \(t_1\) or \(t_2\) while minimizing the total traveled distance.
Later, a block will be part of our graph in the lower bound construction and we will ensure that the agent needs to traverse almost all blocks in order to reach every vertex. Note that with the relaxed requirement that blocks only need to be traversed, instead of the requirement that all vertices are explored, we obtain a safe lower bound on the cost incurred by the agent. However, for the offline optimum, we still require it to visit all vertices to obtain an upper bound on the cost incurred by the offline agent.
As already hinted at in the previous section, we keep track of multiple values for an instance \(B\) of the block traversal problem that turn out to be useful later on. In our constructions, we will often connect blocks where the exit edges of one block \(B\) correspond to the entry edges of the subsequent block \(B'\). We will charge the cost of traversing these on the block \(B'\). For this reason, when studying \(B\) in isolation, we never charge the cost of traversing an exit edge in the following values.
The algorithm’s cost \(\mathrm{\small Alg}_B\) is the cost incurred by the agent for the block traversal problem on \(B\), excluding the cost of traversing an exit edge.
The block length is \(l_B:=d(s,u_\mathrm{Ex})\). In other words, this is the cost incurred by the online or offline agent in a second traversal.
The optimal exploration cost \(\mathrm{\small Opt}_B\) is the length of a shortest walk from \(s\) to \(u_\mathrm{Ex}\) that visits all vertices in \(B\). In other words, this is the cost incurred by the offline agent.
The zigzag length is \(z_B:=\mathrm{\small Opt}_B-l_B\). Intuitively, this is the “discount” that the offline or online agent obtains for a second traversal. The name is inspired by the fact that, in the instances that we construct, this value is larger if the agent prefers to travel in “zigzag movements”.
The algorithm’s core cost \(\mathrm{\small AlgC}_B\) is defined by \(\mathrm{\small AlgC}_B:=\mathrm{\small Alg}_B-z_B\).
The definition of the last value is motivated as follows: In our final construction, blocks will be traversed twice by the agent and we will be able to show that during the first traversal, the incurred cost is \(3\mathrm{\small Opt}_B+z_B\), and during the second traversal, the incurred cost is \(\mathrm{\small Opt}_B-z_B\). In a similar spirit to potential function arguments, the adversary “saves” \(z_B\) in the first traversal and charges it only in the second traversal, i.e., the core cost is the cost charged during the first traversal. As explained in 3, our goal is to prove the following result. While this is closely related to [3], the key difference is that we estimate the core cost instead of the total algorithm cost.
Theorem 1. There exists an adversarial strategy that, for every \(\varepsilon>0\) and every block traversal algorithm \(\mathrm{\small Alg}\), constructs an instance \(B\) of the block traversal problem with \(\mathrm{\small AlgC}_B/\mathrm{\small Opt}_B\geq 3-\varepsilon\).
We will often use that blocks can be connected to each other. We define a chain of blocks (see 3) as a sequence of blocks \(B_1, \dots, B_i\) where all entry and exit edges have the same weight, by identifying the exit vertex of block \(B_j\) with the starting vertex of block \(B_{j+1}\) (\(j\in \{1, \dots, i-1\})\). In particular, we identify the target vertices of block \(B_j\) with the algorithmic and optimal entry vertex of block \(B_{j+1}\). Let \(s\) be the starting vertex of \(B_1\) and \(t_1^*, t_2^*\) be the target vertices of the last block \(B_i\). Consider the block traversal problem on the chain, which we call in the following \(P\), with \(s\) as the starting vertex and \(t_1^*, t_2^*\) as the target vertices. Note that, while \(\mathrm{\small Alg}\) does not learn anything during the traversal of a block \(B_j\) about another block \(B_{j'}\), the traversal of \(B_j\) can still affect the strategy followed in \(B_{j'}\): Indeed, the agent may change strategy when facing the same situation multiple times. Let \(\mathrm{\small Alg}_{B_j}\) denote the strategy followed in block \(B_j\).
observationobservationchain In the block traversal problem on chain \(P\), we have
\(\mathrm{\small Alg}_P\geq \sum_{j=1}^i \mathrm{\small Alg}_{B_j}\),
\(\mathrm{\small Opt}_P=\sum_{j=1}^i \mathrm{\small Opt}_{B_j}\),
\(l_P=\sum_{j=1}^il_{B_j}\).
Proof. When the online or offline agent traverses an edge leading from \(B_j\) to \(B_{j+1}\), we charge this cost on \(B_{j+1}\). The statements now follow from the fact that every path from \(s\) to \(t_1^*\) or \(t_2^*\) contains the exit vertices of all blocks (where the exit vertex of one block is the starting vertex of the subsequent block). ◻
5 Recursive block construction↩︎
We now turn to proving 1. As explained in 3, we construct the blocks for this recursively using similar ideas as in [3], but estimate the core cost instead of the algorithm’s total cost. One of the key differences is that our blocks have a fixed block length and variable optimum costs, whereas in [3], the block length is variable and the optimum cost is fixed. In our final construction, when the agent has to backtrack, it will have the choice between two different chains containing the same number of blocks. It will be beneficial for us that these have the same length. Another key difference is that we construct only one type of block, where in [3], the beginnings and ends of chains of blocks have a special form so that three types of blocks are needed. This is not necessary for our construction, which makes it simpler.
Fix a sufficiently large and even integer \(k\). For \(d\in\mathbb{N}_0\), we recursively define an adversarial strategy \(\mathcal{A}_d\) that constructs an instance \(B\) of the block traversal problem with the following properties.
The block length is \(l_B=2k^d\).
The optimal cost is bounded by \(\mathrm{\small Opt}_B \leq (d+2)k^d\).
The weight of the entry edges and exit edges is \(k^d\).
We say that \(d\) is the level of the adversarial strategy, which corresponds to its recursion depth.
Lemma 1. For every \(d\in \mathbb{N}_0\), there exists an adversarial strategy \(\mathcal{A}_d\) of level \(d\) that, for every block traversal algorithm \(\mathrm{\small Alg}\), constructs a planar instance \(B\) of the block traversal problem fulfilling B1)-B3) with the following property: Let \(r_d\) be the infimum of \(\mathrm{\small AlgC}_B/\mathrm{\small Opt}_B\) over all algorithms \(\mathrm{\small Alg}\), where \(B\) is the block constructed by \(\mathcal{A}_d\) for \(\mathrm{\small Alg}\). Letting \(k\in\Omega(d^2)\) and \(d\to \infty\), we have \(r_d\to 3\).
Proof. For \(d=0\), we define \(\mathcal{A}_0\) to output the block traversal instance illustrated in 4 for every algorithm \(\mathrm{\small Alg}\). It is straightforward that \(l_B=\mathrm{\small Opt}_B=\mathrm{\small Alg}_B=2\) so that properties B1)-B3) are fulfilled and we have \(r_0=1\). Next, we define the strategy \(\mathcal{A}_d\) for \(d\geq 1\) assuming that \(\mathcal{A}_{d-1}\) is already given.
Construction. The construction is illustrated in 5. The starting vertex \(s\) is incident to the two entry edges of weight \(k^d\) and we may assume that the agent traverses the algorithmic entry edge (using [property:exploration-restriction-nochoice]). Then it is at position \(u_\mathrm{\small Alg}\), which we identify with the starting vertices of two blocks in which we use \(\mathcal{A}_{d-1}\), i.e., \(u_\mathrm{\small Alg}\) is incident to four edges of weight \(k^{d-1}\). From here, we build two chains of blocks starting from \(u_\mathrm{\small Alg}\), i.e., whenever the agent traverses for the first time an exit edge of a block, we present it with a new block, where we identify the exit vertex of the previous block with the starting vertex of the new block. In each of these blocks, we apply strategy \(\mathcal{A}_{d-1}\). Note that we use here property [block-property:weights] to be able to build these chains. In the chain, we say that a block is explored if the agent has traversed its exit edge. This procedure stops if either (1) the agent travels back to \(s\) or (2) one of the two chains consists of \((k/2)-1\) explored blocks.
In case (1), let \(B_i', \dots, B_1', u_\mathrm{\small Alg}, B_1, \dots, B_j\) be the chains of blocks, where \(1\leq i, j\leq (k/2)-1\) and all blocks except for \(B_i', B_j\) are explored (but \(B_i', B_j\) have been entered at some point). When the case is triggered, the agent is located at vertex \(s\). Then we complete block \(B_i'\) to some valid block constructed by \(\mathcal{A}_{d-1}\) and connect its two exit edges both to the same vertex \(u_\mathrm{\small Opt}\), which we define to be the optimal entry vertex. The chain of blocks \(u_\mathrm{\small Alg}, B_1, \dots, B_j\) is extended into a chain of \((k/2)-1\) blocks. Importantly, we only fix here the number of these blocks but do not reveal the structure of the new blocks to the agent. This will be determined when the agent traverses them, where we will again use strategy \(\mathcal{A}_{d-1}\). The two exit edges of block \(B_{(k/2)-1}\) are then connected to a vertex \(w\), and \(w\) is connected to a vertex \(u_\mathrm{Ex}\) by an edge of weight \(k^{d-1}\), which we define to be the exit vertex.
In case (2), let \(B_i', \dots, B_1', u_\mathrm{\small Alg}, B_1, \dots, B_{(k/2)-1}\) be the chains of blocks, where \(i\leq (k/2)-1\) and all blocks but \(B_i'\) are explored. The case is triggered when the agent traverses an exit edge of block \(B_{(k/2)-1}\). Then we let both exit edges of \(B_{(k/2)-1}\) lead to the same vertex \(w\). This is connected by an edge of weight \(k^{d-1}\) to the exit vertex \(u_\mathrm{Ex}\). Block \(B_i'\) is completed to some valid block constructed by \(\mathcal{A}_{d-1}\) and both of its exit edges lead to the same vertex \(u_\mathrm{\small Opt}\), which we define to be the optimal entry vertex. Additionally, we introduce an edge of weight \(k^d\) between \(u_\mathrm{\small Opt}\) and \(u_\mathrm{Ex}\). The case \(d=1\) is illustrated in 2.
Block properties and analysis. Note that [block-property:weights] is obviously fulfilled in the construction and one can observe from 5 that the constructed block is planar, using that, by induction, the blocks constructed by \(\mathcal{A}_{d-1}\) are planar as well. Using [obs:chains-of-blocks] and that blocks constructed by \(\mathcal{A}_{d-1}\) fulfill properties [block-property:length]-[block-property:weights], we obtain that a shortest path from \(s\) to \(u_\mathrm{Ex}\) is given by first traversing the algorithmic entry edge, then blocks \(B_1, \dots, B_{(k/2)-1}\) and then the edges to \(w\) and \(u_\mathrm{Ex}\). We obtain \[\label{eq:lB-rec} l_B=k^d+\sum\limits_{j=1}^{(k/2)-1} l_{B_j}+2k^{d-1}=k^d + (k/2)\cdot 2k^{d-1}=2k^d,\tag{1}\] so that property [block-property:length] is fulfilled (note that, in case (2), the existence of the additional edge \(\{u_\mathrm{\small Opt}, u_\mathrm{Ex}\}\) does not lead to a shorter path). In both cases (1) and (2), observe that \[\label{eq:opt-level-2} \mathrm{\small Opt}_B \leq k^d + \sum\limits_{j=1}^i \mathrm{\small Opt}_{B_j'} + k^{d-1} + \sum\limits_{j=1}^{(k/2)-1} \mathrm{\small Opt}_{B_j} + 2k^{d-1}.\tag{2}\] Using that \(\mathrm{\small Opt}_{B_j}\leq (d+1)k^{d-1}\), we obtain \[\begin{align} \mathrm{\small Opt}_B&\leq k^d + \left(i+\frac{k}{2}-1\right)\cdot (d+1)k^{d-1}+3k^{d-1}\\ \overset{3\leq 2(d+1)}&{\leq} k^d + \left(i+\frac{k}{2}+1\right)\cdot (d+1)k^{d-1} \overset{i\leq \frac{k}{2}-1}{\leq} k^d+ (d+1) k^d= (d+2)k^d, \end{align}\] so that property [block-property:opt] is fulfilled as well. By definition, we have \(z_B=\mathrm{\small Opt}_B-l_B\) and plugging in our findings from 1 and 2 , we obtain \[\begin{align} z_B&\leq \sum\limits_{j=1}^{(k/2)-1} (\mathrm{\small Opt}_{B_j}-l_{B_j})+\sum\limits_{j=1}^{i} \mathrm{\small Opt}_{B_j'} + k^{d-1} =\sum\limits_{j=1}^{(k/2)-1} z_{B_j} + \sum\limits_{j=1}^{i} (z_{B_j'}+l_{B_j'}) + k^{d-1}.\label{eq:zB-level-2} \end{align}\tag{3}\]
Next, we analyze the cost incurred by the agent. We say that a block is backtracked if the agent traverses it — either from \(s\) to \(u_\mathrm{Ex}\) or in the other direction — after the block was explored. In case (1), the agent traverses three times an entry edge of weight \(k^d\) and, before the case was triggered, it explores and backtracks the blocks \(B_1', \dots, B_{i-1}'\). To reach \(u_\mathrm{Ex}\), \(\mathrm{\small Alg}\) also has to traverse the blocks \(B_1, \dots, B_{(k/2)-1}\), where we use that the edge \(\{u_\mathrm{\small Opt}, u_\mathrm{Ex}\}\) is not present in this case. Traversing the exit edge of \(B_{(k/2)-1}\) and \(\{w, u_\mathrm{Ex}\}\), the agent incurs another cost of \(2k^{d-1}\). Using our findings for chains ([obs:chains-of-blocks]), we obtain \[\label{eq:Alg-recursive-cost} \mathrm{\small Alg}_B \geq 3k^d + \sum\limits_{j=1}^{(k/2)-1} \mathrm{\small Alg}_{B_j}+\sum\limits_{j=1}^{i-1}(\mathrm{\small Alg}_{B_j'}+l_{B_j'})+ 2k^{d-1}.\tag{4}\] In case (2), the agent traverses one entry edge, explores and backtracks the blocks \(B_1', \dots, B_{i-1}'\) and explores blocks \(B_1, \dots, B_{(k/2)-1}\) before the case was triggered. Then, the agent is located at \(w\) and, by property [property:exploration-restriction-nochoice], the agent is not able to traverse an exit edge before exploring \(u_\mathrm{\small Opt}\). Traveling from \(w\) to \(u_\mathrm{\small Opt}\) and then to \(u_\mathrm{Ex}\) costs at least \(2k^d+k^{d-1}\). Therefore, we obtain the same bound 4 for case (2) as in case (1). By 3 and 4 , we obtain a core cost of \[\begin{align} \mathrm{\small AlgC}_B&=\mathrm{\small Alg}_B-z_B \geq 3k^d + \sum\limits_{j=1}^{(k/2)-1} (\mathrm{\small Alg}_{B_j}-z_{B_j})+\sum\limits_{j=1}^{i}(\mathrm{\small Alg}_{B_j'}-z_{B_j'})\nonumber\\ &- \mathrm{\small Alg}_{B_i'}- \underbrace{l_{B_i'}}_{=2k^{d-1}}+ k^{d-1}\nonumber\\ &= 3 k^d + \sum\limits_{j=1}^{(k/2)-1} \mathrm{\small AlgC}_{B_j} + \sum\limits_{j=1}^{i} \mathrm{\small AlgC}_{B_j'} - \mathrm{\small Alg}_{B_i'} - k^{d-1}\nonumber\\ &\geq 3 k^d + \sum\limits_{j=1}^{(k/2)-1} \mathrm{\small AlgC}_{B_j} + \sum\limits_{j=1}^{i} \mathrm{\small AlgC}_{B_j'} - (3d+4) k^{d-1},\label{eq:algc-level-2} \end{align}\tag{5}\] where we have used for the last inequality that \(\mathrm{\small Alg}_{B_i'}\leq 3 \mathrm{\small Opt}_{B_i'}\leq 3(d+1) k^{d-1}\) because otherwise, the statement of the lemma is clear.
Ratio analysis. For \(d\geq 1\), we obtain using 2 and 5 that \[\begin{align} r_d&\geq \frac{3 k^d + \sum_{j=1}^{(k/2)-1} \mathrm{\small AlgC}_{B_j} + \sum_{j=1}^{i} \mathrm{\small AlgC}_{B_j'} - (3d+4) k^{d-1}}{k^d + \sum_{j=1}^{(k/2)-1} \mathrm{\small Opt}_{B_j} + \sum_{j=1}^i \mathrm{\small Opt}_{B_j'} + 3k^{d-1}}\\ &\geq \frac{3 k^d + r_{d-1} \left(\sum_{j=1}^{(k/2)-1} \mathrm{\small Opt}_{B_j} + \sum_{j=1}^{i} \mathrm{\small Opt}_{B_j'}\right) - (3d+4) k^{d-1}}{k^d + \sum_{j=1}^{(k/2)-1} \mathrm{\small Opt}_{B_j} + \sum_{j=1}^i \mathrm{\small Opt}_{B_j'} + 3k^{d-1}}\\ &\geq \frac{3k^d + r_{d-1}k (d+1) k^{d-1}- (3d+4) k^{d-1}}{k^d+k(d+1)k^{d-1}+3k^{d-1}} = \frac{3 + r_{d-1}(d+1) - (3d+4)/k}{1+(d+1)+3/k}, \end{align}\] where we have used for the inequality in the last line that \(\mathrm{\small Opt}_{B_j}\leq (d+1) k^{d-1}\) by [block-property:opt], \(i<k/2\), and the fact that \(\frac{x+z}{y+z}\leq \frac{x}{y}\) for \(x\geq y\geq 0\) and \(z\geq 0\). From this recursive expression, it is easy to see that, if \(k\in \Omega(d^2)\) and we let \(d\to \infty\) (and therefore also \(k\to \infty\)), we have \(r_d\to 3\). (This can be seen from the fact that the terms with \(k\) in the denominator can be neglected and \(r=3\) is the only solution of \(r=(3+r(d+1))/(1+d+1)\).) ◻
Choosing \(d\) large enough in the Lemma, we obtain 1.
6 Block arrangement↩︎
Now that we have established the necessary preliminaries on block traversal, we turn to proving our main result ([thm:4-lower-bound]) in this section. For this, we use the same block arrangement as in [3], but we give a refined analysis using our stronger results on the block traversal problem.
![Figure 6: The block arrangement from [3] used here in the proof of [thm:4-lower-bound]. Rectangle shapes represent blocks and circle shapes represent single vertices. All drawn edges have weight k^d, where we have omitted edges inside the blocks. Pairs of edges beginning at the same point inside a block are its exit edges and a pair of edges leading to two different points in a block are its entry edges.](/article/2607.15113/_pdflatex/kvimpafh.png "fig:")
Proof of [thm:4-lower-bound]. As a first step, we give the construction for the block arrangement as in [3].
Construction. Let \(\varepsilon>0\) be arbitrary and choose \(d,k\) large enough (depending on \(\varepsilon\)) with \(k\in\Omega(d^2)\). Fix an online graph exploration algorithm \(\mathrm{\small Alg}\). Whenever we refer to a block in this proof, we mean a block constructed by \(\mathcal{A}_d\) as in 1. Moreover, let \(M\) and \(N\) be a
large enough integers.
We construct a graph \(G\) (adaptively depending on the behavior of \(\mathrm{\small Alg}\)) as follows (see 6). Let \(v_\mathrm{s}\) denote the starting position and identify it with the starting vertices of two blocks, i.e., \(v_\mathrm{s}\) is incident to four boundary edges of weight \(k^d\) and the first two such traversed boundary edges are the algorithmic entry edges of two different blocks. Whenever the agent successfully explores and leaves a block, its exit vertex is identified with the starting vertex of a new block, so that we obtain two chains of blocks \(P_1\) and \(P_1'\) and, in each block, we employ strategy \(\mathcal{A}_d\). This procedure ends when one of the chains consists of \(M\) blocks constructed by \(\mathcal{A}_d\) and we assume w.l.o.g. that this occurs for chain \(P_1\). We let the exit edges of the last explored block lead to a vertex \(v_\mathrm{1}\). This vertex is identified with the starting vertex of three further blocks, i.e., \(v_1\) is incident to 8 edges of weight \(k^d\) (two exit edges and 6 entry edges). The agent starts exploring these and, similarly as before, we build chains of blocks. Let \(M'\) denote the number of blocks in \(P_1'\), i.e., \(P_1'\) consists of \(M'-1\) explored blocks and one partially explored block. Let \(M''\) be the maximum number of blocks contained in any of the three chains starting from \(v_1\). We stop the process when \(M'+M''=M\) and the agent traverses a new exit edge. Let \(P_1''\) be the chain starting from \(v_1\) of length \(M''\). When the process stops, there is exactly one block that was entered, but not explored: If the last block that was traversed is in \(P_1'\), this partially explored block is in \(P_1''\), and if the last block that was explored is in \(P_1''\), the partially explored block is in \(P_1'\). We complete it to some valid block that \(\mathcal{A}_d\) constructs (for some algorithm) and call this block \(B_1^*\). We let the edges of the last blocks in \(P_1'\) and \(P_1''\) lead to the same vertex \(u_\mathrm{1}\).
We obtain a cycle of blocks consisting of \(P_1, P_1', P_1''\), which we refer to as \(C_1\) and, from vertex \(v_1\), there are two chains of
blocks with unexplored ends of length less than \(M\). We iterate the procedure by ignoring the explored cycle \(C_1\) and interpreting \(v_1\) as the new
starting vertex \(v_s\). This is repeated until we obtain \(N\) such cycles of blocks. Then, we have two chains of blocks with unexplored ends beginning from \(v_N\). As soon as their total numbers of blocks sum up to \(2M\), we let the exit edges of the last blocks in these chains be connected to a closing vertex \(v_\mathrm{t}\). We call this last cycle of blocks between \(v_N\) and \(v_\mathrm{t}\) cycle \(C^*\). Observe that the
construction is planar using that the blocks constructed by \(\mathcal{A}_d\) are planar.
Analysis. First, note that every block, except for the blocks \(B_i^*\) for each \(i\), was only entered via an entry edge before it was explored. For each of these
blocks \(B\), the agent incurs a cost of \(\mathrm{\small Alg}_B\) during the first exploration. Next, we will argue that almost every block will be traversed a second time. More precisely,
we claim the following, where we use that all blocks have the same block length \(2k^d\).
Claim 2. The agent incurs a total cost of at least \(N(2M-1)\cdot 2k^d\) for backtracking blocks.
Proof. We only argue that the algorithm incurs a cost of \((2M-1)\cdot 2k^d\) for backtracking in \(C_1\) and it will be clear that this holds similarly for all other cycles \(C_2, \dots, C_N\) (but not for \(C^*\)). We distinguish two cases: \(M'+M''=M\) was triggered by (1) exploration of a block in \(P_1'\) or (2) by exploration of a block in \(P_1''\).
In case (1), observe that the agent already backtracked all \(M\) blocks in \(P_1\) at the time when \(M'+M''=M\) was triggered, so that it incurred a cost of at least \(M\cdot 2k^d\). Then, the agent has to travel to \(v_1\) to reach cycle \(C_2\). Since it has to return to the starting position when all vertices were explored, it needs to traverse a path from \(v_1\) to \(v_s\) at the end. A shortest such path is to again traverse all blocks in \(P_1\) so that the agent incurs another cost of \(M\cdot 2k^d\) for backtracking in \(C_1\).
In case (2), observe that the agent backtracked all blocks in \(P_1'\setminus \{B_1^*\}\) at the time when \(M'+M''=M\) was triggered. To proceed with the exploration, the agent has to travel to \(v_1\) and the shortest way for this is by backtracking all blocks in chain \(P_1''\), so we can charge this cost by assuming that these blocks were backtracked. At the end, the agent has to return to the starting position, for which it needs to travel from \(v_1\) to \(v_\mathrm{s}\) and the shortest way for this is by backtracking all blocks in chain \(P_1\). Together, we obtain that, in either case, we can assume that the agent backtracks all blocks in \(C_1\setminus \{B_1^*\}\) and we have \(|C_1\setminus \{B_1^*\}|=(2M-1)\). ◻
The claim implies that, for every block, except for \(B_i^*\) (\(i\in\{1, \dots, N\}\)) and the blocks in \(C^*\), the agent incurs a cost of \(\mathrm{\small Alg}_B\) for the first traversal, and a cost of \(2k^d=l_B\) for backtracking. We obtain \[\begin{align} \mathrm{\small Alg}(G, v_s)&\geq\sum\limits_{j=1}^N\sum\limits_{B \in C_j\setminus \{B_j^*\}}\mathrm{\small Alg}_B+l_B =\sum\limits_{j=1}^N\sum\limits_{B \in C_j\setminus \{B_j^*\}}\mathrm{\small AlgC}_B+\mathrm{\small Opt}_B\nonumber\\ &\geq (4-\varepsilon)\cdot \sum\limits_{j=1}^N\sum\limits_{B \in C_j\setminus \{B_j^*\}}\mathrm{\small Opt}_B,\label{eq:alg-lower-bound-final} \end{align}\tag{6}\] where we have used 1 and that \(k\) and \(d\) are large enough (depending on \(\varepsilon\)).
At the same time, in the offline optimum, the agent only needs to explore every block once and never backtracks a block. We obtain \[\begin{align} \mathrm{\small Opt}(G)&\leq\sum\limits_{j=1}^{N}\left(3k^d+\sum\limits_{B \in C_j}\mathrm{\small Opt}_B\right) + \sum\limits_{B \in C^*}\mathrm{\small Opt}_B + 2k^d\nonumber \\ &\leq \sum\limits_{j=1}^{N} \left(\sum\limits_{B \in C_j\setminus\{B_j^*\}}\mathrm{\small Opt}_B \right)+ (2N+2M+1)(d+2)k^{d}\label{eq:opt-lower-bound-final}, \end{align}\tag{7}\] where, for the last inequality, we have estimated each of \(\mathrm{\small Opt}_B, 3k^d, 2k^d\) by \((d+2)k^d\) (for \(B=B_j^*\) and \(B\in C^*\)) and used that \(C^*\) consists of \(2M\) blocks.
Note that \[\begin{align} &\frac{(2N+2M+1)(d+2)k^d}{\mathrm{\small Alg}(G, v_s)} \leq \frac{(2N+2M+1)(d+2)k^d}{N\cdot (2M-1)2k^d} \to 0 (M,N \to \infty), \end{align}\] where we have used the safe lower bound \(\mathrm{\small Alg}(G, v_s)\geq N(2M-1)l_B=N(2M-1)2k^d\).
By 6 and 7 , we obtain together with the last inequality for the competitive ratio that \(\liminf_{M,N\to\infty}\mathrm{\small Alg}(G, v_s)/\mathrm{\small Opt}(G)\geq (4-\varepsilon)\). Since \(\varepsilon>0\) was chosen arbitrarily, we obtain that the competitive ratio is at least 4 on planar graphs. Combining with the fact that any planar construction can be made subcubic ([cor:exploration-restrictions]), this completes the proof of [thm:4-lower-bound]. ◻
Last, we remark that our analysis for the constructed graph is tight. To see this, one can easily verify that depth-first search (ignoring edge weights) is 4-competitive on our construction.
6.0.0.1 Acknowledgements.
I thank Yann Disser for valuable feedback on the writeup of this paper.
References↩︎
Email: jbaligacs@gmail.com↩︎