Graph Exploration: The Impact of a Distance Constraint

Exploring an unknown environment is a fundamental task with numerous applications, including target localization, data gathering, and map construction. The considered environments can vary considerably in type: they may be terrains, networks, three-dimensional spaces, etc. In hazardous situations, it is generally more appropriate to delegate exploration to a mobile artificial entity, hereinafter referred to as an agent, which could be an autonomous robot or a vehicle remotely controlled by a human.

In this paper, we focus our attention on the task of exploration by a mobile agent of a network modeled as a graph, and more specifically on a variant where the agent must always know a path from its initial node to its current node that does not exceed a given upper bound. This requirement finds its justification in applications where the agent needs to always keep the possibility of returning quickly to its base or to always maintain a certain distance to ensure ongoing communication with its base.

An agent is assigned the task of exploring a simple¹¹1In [15], where the task of distance-constrained exploration that we will study has been introduced, the authors do not mention explicitly whether they consider simple graphs or multigraphs. A closer look at their work can reveal, though, that their results hold for multigraphs. However, it is important to note that, in the context of the impossibility proof that we will conduct, the choice of focusing only on simple graphs does not lead to a loss of generality. In fact, it broadens the scope of our result, ensuring that it holds for both simple graphs and multigraphs. finite undirected graph $G=(V,E)$, starting from a node $s$, called the source node. The exploration requires visiting (resp. traversing) at least once every node (resp. every edge). Thus, $G$ is supposed to be connected. We denote by $\mathrm{𝚍𝚎𝚐}(v)$ the degree of a node $v$ in $G$, and by $|V|$ (resp. $|E|$) the order (resp. size) of $G$.

We make the same assumption as in [15] which states that the agent has unbounded memory and can recognize already visited nodes and traversed edges. This is formalized as follows. Nodes of $G$ have arbitrary pairwise distinct labels that are positive integers. The label of $s$ will be denoted by $l_s$. Distinct labels, called port numbers and ranging from $0$ to $\mathrm{𝚍𝚎𝚐}(v)-1$, are arbitrarily assigned locally at each node $v$ to each of its incident edges. Hence, each edge has two ports, one per endpoint, and there is no a priori relationship between these two ports. At the beginning, the agent located at node $s$ learns only its degree and its label. To explore the graph, the agent applies a deterministic algorithm that makes it act in steps: at each step, the algorithm selects a port number $p$ at the current node $v$ (on the basis of all information that has been memorized so far by the agent) and then asks the agent to traverse the edge having port $p$ at $v$. At that point, the agent traverses the given edge at any finite positive speed and, once it enters the adjacent node, it learns (only) its degree, its label as well as the incoming port number. Afterwards, the agent starts the next step, unless the algorithm has terminated.

Roughly speaking, the memory of the agent is the total information it has collected since the beginning of its exploration. We formalize it as follows: the memory of the agent, after the first $t$ edge traversals, is the sequence $(M_0,M_1,\mathrm{\dots },M_t)$, where $M_0$ is the information of the agent at its start and $M_i$ is the information acquired right after its $i$th edge traversal. Precisely, the initial memory $M_0$ is represented by the 4-tuple $(l_0,d_0,-1,-1)$, where $l_0$ and $d_0$ correspond to the label of the source node and its degree respectively. Then, if $i\ge 1$, $M_i$ is the 4-tuple $(l_i,d_i,p_i,q_i)$ where $l_i$ is the identifier of the occupied node after the $i$th edge traversal, $d_i$ the degree of that node, $p_i$ is the port by which the agent has left the node $l_{i-1}$ to make the $i$th edge traversal, and $q_i$ the port by which the agent entered node $l_i$ via its $i$th edge traversal.

Without any constraint on the moves, the task of exploration in the above model is called unconstrained exploration. However, in this paper, we study a variant introduced in [15] and called distance-constrained exploration. In this variant, the agent must deal with the additional constraint of always knowing a path (i.e., a sequence of already explored edges) of length at most $D$ from its current location to node $s$. The value $D$ is fixed to $(1+\alpha )r$, where $r$ and $\alpha$ respectively correspond to the eccentricity of node $s$ and an arbitrary positive real constant. In [15], two scenarios are considered: one where both $r$ and $\alpha$ are initially known to the agent, and another where only $\alpha$ is known. In this paper, we adopt the more challenging scenario from a proof-of-impossibility perspective, where both $r$ and $\alpha$ are initially known to the agent, in order to give our result a greater impact.

An instance of the problem is defined as the tuple $(G,l_s,\alpha )$. We will denote by $ℐ(\alpha ,r)$ the set of all instances $(G,l_s,\alpha )$ such that the eccentricity of the source node $s$ (of label $l_s$) in $G$ is $r$.

An important notion involved in this paper is that of penalty incurred during exploration. First discussed by Pelc and Panaite in [20], the penalty of an exploration algorithm running in $G$ is the number of edge traversals in excess of $|E|$ made by the mobile agent. In their seminal paper [20], Panaite and Pelc gave an algorithm for solving unconstrained exploration, which is guaranteed to work in every connected graph $G$ with a (small) penalty of $𝒪(|V|)$. In the light of this result, an intriguing question naturally arises:

Would it be possible to design a distance-constrained exploration algorithm working in every graph $G$ with a penalty of $𝒪(|V|)$?

In this paper, we provide a negative answer to the above question. This negative answer is strong as we show that for any positive real $\alpha$ and every integer $r\ge 6$, there is no algorithm that can solve distance-constrained exploration for every instance $(G,l_s,\alpha )$, where $G=(V,E)$ is a connected simple graph, of $ℐ(\alpha ,r)$ with a penalty of $𝒪(|V|)$.

Moreover, we observe that the impossibility result remains true for another variant of constrained exploration studied in the literature, known as fuel-constrained exploration. In this variant, which was introduced by Betke et al. in [6], the context remains the same, except that now the agent must face a slightly different constraint: it has a fuel tank of limited size that can be replenished only at its starting node $s$. The size of the tank is $B=2(1+\alpha )r$, where $\alpha$ is any positive real constant and $r$ is the eccentricity of $s$. The tank imposes an important constraint, as it forces the agent to make at most $\lfloor B\rfloor$ edge traversals before having to refuel at node $s$, otherwise the agent will be left with an empty tank and unable to move, preventing further exploration of the graph. The underlying graph and node $s$ are chosen so that $r\alpha \ge 1$ (if not, fuel-constrained exploration is not always feasible).

Through our two impossibility results, we show a fundamental separation with the task of unconstrained exploration. We also solve an open problem posed by Duncan et al. in [15], who asked whether distance-constrained or fuel-constrained exploration could be achieved with a penalty of $𝒪(|V|)$ in every graph.²²2In [15], the authors also investigated a third variant known as rope-constrained exploration, but they did not include it in their open problem. This point is further detailed at the end of the related work section.

Due to lack of space, many technical results and formal proofs have been omitted. All details are available in the full version of the paper [12].

The problem of exploring unknown graphs has been the subject of extensive research for many decades. It has been studied in scenarios where exploration is conducted by a single agent and in scenarios where multiple agents are involved. In what follows, we focus only on work related to the former case (for the latter case, a good starting point for the curious reader is the survey of Das [10]).

In the context of theoretical computer science, the exploration problem was initially approached by investigating how to systematically find an exit in a maze (represented as a finite connected subgraph of the infinite 2-dimensional grid in which the edges are consistently labeled North, South, East, West). In [22], Shannon pioneered this field with the design of a simple finite-state automaton that can explore any small maze spanning a $5\times 5$ grid. More than twenty years later, Budach [8] significantly broadened the scope of study by showing that no finite-state automaton can fully explore all mazes. Blum and Kozen showed in [7] that this fundamental limitation can be overcome by allowing the automaton to use only two pebbles. The same authors naturally raise the question of whether one pebble could suffice. A negative answer to this question is provided by Hoffmann in [17].

In the following decades, much of the attention shifted to the exploration of arbitrary graphs, for which the solutions dedicated to mazes become obsolete. Studies on the exploration of arbitrary graphs can be broadly divided into two types: those assuming that nodes in the graph have unique labels recognizable by the agent, and those assuming anonymous nodes.

As for mazes, exploration of anonymous graphs has been investigated under the scenario in which the agent is allowed to use pebbles [5, 9, 13, 14]. In [14], Dudek et al. showed that a robot provided with a single movable pebble can explore any undirected anonymous graph using $𝒪(|V|\cdot |E|)$ moves. If the pebble is not movable and can only be used to mark the starting node of the agent, it is shown in [9] that exploration is still possible using a number of edge traversals polynomial in $|V|$. In [13], the authors investigated the problem in the presence of identical immovable pebbles, some of which are Byzantine (a Byzantine pebble can be unpredictably visible or invisible to the agent whenever it visits the node where the pebble is located) and designed an exploration algorithm working in any undirected graph provided one pebble always remains fault-free. In the case where the graph is directed, exploration becomes more challenging due to the impossibility of backtracking and may even be sometimes infeasible if the graph is not strongly connected. However, in the scenario where the agent evolves in strongly connected directed graphs, Bender et al. proved that $\mathrm{\Theta }(\log \log |V|)$ movable pebbles are necessary and sufficient to achieve a complete exploration.

When no marking of nodes is allowed, exploration of undirected anonymous graphs becomes obviously more difficult, and detecting the completion of the task cannot be always guaranteed without additional assumptions. If randomization is allowed, we know from [2] that a simple random walk of length $𝒪({\mathrm{\Delta }}^2{|V|}^3\log |V|)$ can cover, with high probability, all nodes of an undirected graph $G=(V,E)$ of maximal degree $\mathrm{\Delta }$. Such a random walk can thus be used to fully explore a graph (and eventually stop), by initially providing the agent with an upper bound on $|V|$ and by making it go back and forth over each edge incident to a node of the random walk. If randomization is not allowed, all nodes of an undirected anonymous graph can still be visited, using universal exploration sequences (known as UXS) introduced in [19]. Formally, a sequence of integers $x_1,x_2,\mathrm{\dots },x_k$ is said to be a UXS for a class $𝒢$ of graphs, if it allows an agent, starting from any node of any graph $G\in 𝒢$, to visit at least once every node of $G$ in $k+1$ steps as follows. In step $1$, the agent leaves its starting node $v_1$ by port $0$ and enters some node $v_2$. In step $2\le i\le k+1$, the agent leaves its current node $v_i$ by port $q=(p+x_{i-1})mod\mathrm{𝚍𝚎𝚐}(v_i)$, where $p$ is the port by which it entered $v_i$ in step $i-1$, and enters some node $v_{i+1}$. In [21], it is proven that for any positive integer $n$, a UXS of polynomial length in $n$, for the class of graphs of order at most $n$, can be computed deterministically in logarithmic space and in time polynomial in $n$. As with random walks, this can be used to fully explore a graph, by initially providing the agent with an upper bound $n$ on $|V|$ and by instructing it to traverse each edge incident to a node visited by a UXS for the class of graphs of order at most $n$. Therefore, whether deterministically or not, it can be easily shown from [2, 21] that an agent can explore any undirected anonymous graph of order at most $n$ even without the ability to mark nodes as long as it has a memory of size $𝒪(\log n)$: in [16] Fraigniaud et al. gave a tight lower bound by showing that a memory of size $\mathrm{\Omega }(\log n)$ is necessary.

The exploration of labeled graphs was a subject of research in [1, 3, 4, 6, 11, 15, 20], with a particular focus on minimizing the number of edge traversals required to accomplish the task.

In [11], Deng and Papadimitriou showed an upper bound of ${𝔇}^{𝒪(𝔇)}|E|$ moves to explore any labeled directed graph that is strongly connected, where $𝔇$, called the deficiency of the graph, is the minimum number of edges that have to be added to make the graph Eulerian. This is subsequently improved on by Albers and Henzinger in [1], who gave a sub-exponential algorithm requiring at most ${𝔇}^{𝒪(\log 𝔇)}|E|$ moves and showed a matching lower bound of ${𝔇}^{\mathrm{\Omega }(\log 𝔇)}|E|$. For arbitrary labeled undirected graphs, the fastest exploration algorithm to date is the one given by Panaite and Pelc in [20], which allows an agent to traverse all edges using at most $|E|+𝒪(|V|)$ moves. Their algorithm thus entails at most a linear penalty in $|V|$, which is significantly better than other classic strategies of exploration (for instance, the standard Depth-First Search algorithm, which takes $2|E|$ moves, has a worst-case penalty that is quadratic in $|V|$). This upper bound of $𝒪(|V|)$ is asymptotically tight as the penalty can be in $\mathrm{\Omega }(V)$, even in some semi-Eulerian graphs (for which $𝔇=1$). In particular, it is the case when an agent is required to explore a simple line made of an odd number $|V|\ge 3$ of nodes, by starting from the median node: the penalty is then necessarily at least $\frac{|V|-1}{2}$ (this also holds even if the agent initially knows the graph and its position in it).

The papers [3, 4, 6, 15] are the closest to our work. As mentioned in Section 1.3, the problem of fuel-constrained exploration of a labeled graph was introduced by Betke et al. in [6]. In this paper, the authors gave fuel-constrained algorithms using $𝒪(|E|+|V|)$ moves but for some classes of graphs only. This line of study was then continued in [3] (resp. in [4]) in which is provided an $𝒪(|E|+|V|{\log }^2|V|)$ algorithm (resp. an $𝒪(|E|+{|V|}^{1+o(1)})$ algorithm) working in arbitrary labeled graphs. Finally, Duncan et al. [15] obtained solutions requiring at most $𝒪(|E|+|V|)$ edge traversals for solving fuel-constrained and distance-constrained explorations. Precisely, the authors did not directly work on these two variants, but on a third one called rope-constrained exploration, in which the agent is tethered to its starting node $s$ by a rope of length $L\in \mathrm{\Theta }(r)$ that it unwinds by a length of $1$ with every forward edge traversal and rewinds by a length of $1$ with every backward edge traversal. Hence, they designed an $𝒪(|E|+|V|)$ algorithm for rope-constrained exploration which can be transformed into algorithms solving the two other constrained exploration problems with the same complexity. However, these algorithms all carry a worst-case penalty proportional to $|E|$ even when $|E|\in \mathrm{\Theta }({|V|}^2)$. As an open problem, Duncan et al. then asked whether we could obtain algorithms for solving constrained explorations with a worst-case penalty linear in $|V|$, as shown in [20] when there is no constraint on the moves. Precisely, Duncan et al. explicitly raised the question for fuel-constrained and distance-constrained explorations and not for rope-constrained exploration. This is certainly due to the following straightforward observation: at any point of a rope-constrained exploration, the difference between the number of forward edge traversals and the number of backward edge traversals can never exceed $L$. Thus, the penalty of any rope-constrained exploration algorithm executed in any graph $G=(V,E)$ is always at least $|E|$-$L$, which can be easily seen as not belonging to $𝒪(|V|)$ in general, since $L$ belongs to $\mathrm{\Theta }(r)$ and thus to $𝒪(|V|)$.

In this subsection, we first give a formalization of the adversary’s behavior that forms the basis of the first stage outlined in Section 3.1, along with additional explanations. In the full version of the paper [12] this formalization is then followed by our complete impossibility proof. Due to space constraints, in this current short version, the formalization will be only followed by the main theorem of our impossibility proof and its corollary.

Before going any further, we need to introduce some extra notations. Let $\alpha$ (resp. $r$) be any positive real (resp. any positive integer). Let $A(\alpha ,r)$ be an algorithm solving distance-constrained exploration for all instances of $ℐ(\alpha ,r)$ and let $(G,l_s,\alpha )$ be an instance of $ℐ(\alpha ,r)$. We will denote by $\mathrm{𝚌𝚘𝚜𝚝}(A,(G,l_s,\alpha ))$ the number of edge traversals prescribed by $A(\alpha ,r)$ with instance $(G,l_s,\alpha )$. Moreover, for every integer $0\le i\le \mathrm{𝚌𝚘𝚜𝚝}(A,(G,l_s,\alpha ))$, we will denote by $𝙼(A,(G,l_s,\alpha ),i)$ (resp. $𝙴(A,(G,l_s,\alpha ),i)$) the memory of the agent (resp. the set of edges that have been traversed by the agent) after the first $i$ edge traversals prescribed by $A(\alpha ,r)$ with instance $(G,l_s,\alpha )$. We will also denote by $\overline{𝙴(A,(G,l_s,\alpha ),i)}$ the set of edges of $G$ that are not in $𝙴(A,(G,l_s,\alpha ),i)$. Finally, for every integer $1\le i\le \mathrm{𝚌𝚘𝚜𝚝}(A,(G,l_s,\alpha ))$, we will denote by $\mathrm{𝚗𝚘𝚍𝚎}(A,(G,l_s,\alpha ),i)$ (resp. $\mathrm{𝚎𝚍𝚐𝚎}(A,(G,l_s,\alpha ),i)$) the node of $G$ that is occupied after the $i$th edge traversal (resp. the edge of $G$ that is explored during the $i$th edge traversal) prescribed by $A(\alpha ,r)$ with instance $(G,l_s,\alpha )$. By convention, the source node will be sometimes denoted by $\mathrm{𝚗𝚘𝚍𝚎}(A,(G,l_s,\alpha ),0)$.

Algorithm 1 gives the pseudocode of function AdversaryBehavior. It corresponds to the formalization of the adversary’s behavior that underlies our first stage. It takes as input the parameters $r$ and $\alpha$ of the distance-constrained exploration problem, an integer $w$ and an exploration algorithm $A$ solving the problem for all instances of $ℐ(\alpha ,r)$. Under certain conditions (see Lemma 3.3 in the full version of the paper [12]), the function returns a graph $G$ with the following two properties. The first property is that $(G,0,\alpha )$ is an instance of $ℐ(\alpha ,r)$ and $G\in ℱ(\lfloor (1+\alpha )r\rfloor +1,w,r)$. The second property is that the penalty incurred by $A$ on instance $(G,0,\alpha )$, by the time of the first visit of a gadget, is in $\mathrm{\Omega }(w^2)$ (i.e., the target penalty of the first stage). To achieve this, function AdversaryBehavior relies on function GraphModification, whose pseudocode is provided in Algorithm 2.

Conceptually, AdversaryBehavior proceeds in steps $0,1,2,3,$ etc. In step $0$ (cf. line 1 of Algorithm 1), we choose an arbitrary graph $G_0$ of $ℱ(\lfloor (1+\alpha )r\rfloor +1,w,r)$. In step $x\ge 1$ (cf. lines 3 to 7 of Algorithm 1), we begin with a graph $G_{x-1}$ of $ℱ(\lfloor (1+\alpha )r\rfloor +1,w,r)$ for which the first $(x-1)$ edge traversals prescribed by $A$ from the node labeled $0$ are “conformed” with the bad scenario of the first stage. The goal is to ensure that this conformity extends to the first $x$ edge traversals as well. This is accomplished by deriving a graph $G_x$, which also belongs to $ℱ(\lfloor (1+\alpha )r\rfloor +1,w,r)$, from graph $G_{x-1}$. The derivation is handled by function GraphModification that uses as inputs the graph $G_{x-1}$, the index $x-1$, the algorithm $A$ and the parameter $\alpha$. If , then there exists a $(x+1)$th edge traversal in the execution of $A$ from the node labeled $0$ in $G_x$, and thus we can continue the process with step $x+1$. Otherwise, the algorithm stops and returns graph $G_x$.

When we mentioned above that in step $x\ge 1$, we aim at extending the bad scenario till the $x$th edge traversal included, we mean that GraphModification($G_{x-1},\alpha ,A,x-1$) returns a graph $G_x$ such that $(1)$ $𝙼(A,(G_{x-1},0,\alpha ),x-1)=𝙼(A,(G_x,0,\alpha ),x-1)$ (i.e., from the agent’s perspective, there is no difference between the first $x-1$ edge traversals in $G_{x-1}$ and those in $G_x$) and $(2)$, if possible, the $x$th edge traversal in $G_x$ brings the agent closer to the penultimate level (in order to eventually force incrementing the penalty). The first point is particularly important for at least preserving the penalty already incurred, while the second is important for increasing it. However, while the first point will always be guaranteed by GraphModification (cf. Lemma 3.1 in the full version of the paper [12]), the second is not always useful or even achievable. This may happen when the agent is at a node of the last level or has previously explored a red edge (in which cases the goal of the bad scenario should have been already met, as explained in Section 3.1) or when the agent is located at the source node (in which case the next move, if any, is in line with the bad scenario as it can only make the agent go down to a node of level $1$). This may also happen when the agent decides to recross an already explored edge as modifying the traversal would violate the agent’s memory (but, this is not an issue, as it increases the penalty as intended). In all these situations (cf. the test of line 4 of Algorithm 2), no modifications will be made and $G_x=G_{x-1}$. (In the rest of the explanations, all line numbers concern Algorithm 2, which we will omit to mention for the sake of brevity).

Assume that the test at line 4 evaluates to true during the execution of GraphModification($G_{x-1},\alpha ,A,x-1$) and denote by $G_{x-1}^{\prime }$ the graph obtained right after the (possible) modifications made to $G_{x-1}$ by lines 5 to 10. When evaluating the test at line 4, the agent is thus located at some node $u$ of some level after the first $x-1$ edge traversals prescribed by $A$ in $G_{x-1}$. At this point, we may face several possible situations, which will be all addressed in the formal proof. But here, one is perhaps more important to pinpoint than the others. It is when the following two predicates are satisfied right before the $x$th edge traversal in $G_{x-1}$. The first predicate, call it $p_1(u,i)$, is that node $u$ is incident to at least one unexplored edge of $ℒ(i,i+1)$ and the second predicate, call it $p_2(i)$, is that there is at least one unexplored green edge in $ℒ(i,i+1)$. This situation is interesting because lines 5 to 10 guarantee that the $x$th edge traversal in $G_{x-1}^{\prime }$ will correspond to a traversal of a green edge leading the agent from node $u$ (of level $i$) to a node $u^{\prime }$ of level $i+1$, as intended in the bad scenario. Note that, if $i+1=\mathrm{\ell }=\lfloor (1+\alpha )r\rfloor +1$ (i.e., the index of the last level in the graph) then algorithm $A$ violates the distance constraint (in view of the fact that no red edge has been yet visited), which is a contradiction. Hence, we have and, according to the bad scenario we aim at forcing the agent into, we want the $(x+1)$th move from node $u^{\prime }$ (of level $i+1$) to lead the agent to level $i+2$ or to be a traversal of a previously explored edge. In the situation where $p_1(u^{\prime },i+1)$ and $p_2(i+1)$ are also satisfied right before the $(x+1)$th edge traversal in $G_{x-1}^{\prime }$, the test at line 12 evaluates to false and $G_{x-1}^{\prime }=G_x$. This is a good situation for the bad scenario. Indeed, if the $(x+1)$th move in $G_x$ is not a traversal of a previously explored edge, then, in the next call to GraphModification, the test at line 4 evaluates to true and lines 5 to 10 will ensure that the $(x+1)$th edge traversal in $G_x$ will correspond to a traversal of a green edge leading the agent to a node $u^{\prime \prime }$ of level $i+2$.

But what if we are not in such a good situation, where both $p_1(u^{\prime },i+1)$ and $p_2(i+1)$ are satisfied right before the $(x+1)$th edge traversal in $G_{x-1}^{\prime }$? In fact, if $p_2(i+1)$ is not satisfied, then there is at least one layer for which at least half the green edges has been explored, which means that the target penalty has already been paid (as explained in Section 3.1 and shown in the proof of Lemma 3.3 in the full version of the paper [12]). Hence, the tricky case is when $p_2(i+1)$ holds but $p_1(u^{\prime },i+1)$ does not, right before the $(x+1)$th edge traversal in $G_{x-1}^{\prime }$. This is exactly where lines 13 to 22 come into the picture (the test at line 12 then evaluates to true during the execution of GraphModification($G_{x-1},\alpha ,A,x-1$)). Using function switch-edges, these lines attempt to reroute the $x$th edge traversal in $G_{x-1}^{\prime }$ towards a node $v$, different from $u^{\prime }$ but also of level $i+1$, such that $p_1(v,i+1)$ holds right before the $(x+1)$th traversal in $G_x$. The feasibility of such rerouting will be guaranteed as long as some conditions are met, particularly that there is no layer for which at least half the green edges has been explored (cf. Lemma 3.2 in the full version of the paper [12]).

The switch performed at line 22 involves two green edges. One of these edges is naturally $\{u,u^{\prime }\}$. The other is a green edge (from the same layer as $\{u,u^{\prime }\}$) resulting from the merge of two red edges achieved by move-gadget, which is performed, right before the switch, at line 17. Proceeding in this way, rather than simply selecting an existing green edge, turns out to be essential to maximize the number of possible reroutings ensuring predicate $p_1$, and thus to get the desired penalty of $\mathrm{\Omega }(w^2)$ before the first exploration of a red edge. Using Algorithms 1 and 2, we get the following theorem, whose proof and the intermediate lemmas on which it relies are available in the full version of the paper [12].

Note that in the statement of Theorem 5, the instance $((V,E),l_s,\alpha )$ can always be chosen so that $r^2\in o(|V|)$. Therefore, we have the following corollary.