Strategy Repair in Reachability Games via a Graph Quotientation

Reachability over graphs is a fundamental problem in Computer Science [6]. It serves as a modeling paradigm and as a solution technique for many aspects of Formal Methods, in particular for Automata Theory and Model Checking [2, 5, 15].

One of its basic formulations consists, for a given directed graph, to find the vertices from which there exists a path to a designated set of target vertices.

Such a setting can be used to model the behavior of an agent navigating within a closed system, that is, whose behavior is fully determined by the agent itself. However, in modern computing, we mostly deal with open systems, whose behavior is dependent on the interaction between the controlling agent and an external entity. To adapt the modeling to this scenario, reachability problems are generalized to Reachability Games (RGs) [11].

In an RG, some vertices in the directed graph are not controlled by the agent but by an external entity, e.g., the environment or another agent, whose nature is adversarial, i.e., whose aim is to prevent reaching a target vertex, if possible. In this scenario, it is not sufficient to find a path connecting the source vertex to the target, as the adversarial agent might deviate from the path through uncontrolled vertices. Therefore, solving a reachability game requires finding a winning strategy, that is, a function that prescribes to the agent the arc to traverse from each controlled vertex in such a way that, regardless of the adversarial decisions, a target vertex is guaranteed to be reached. This is a well-known and widely studied problem in Synthesis [3, 4, 8, 9, 16] and Planning [7, 13].

The solution to an RG, i.e., a winning strategy ${\sigma }_0$ of the game, can be used to model the behavior of an agent acting in an open system. However, as noted in [12], at execution-time, models might deviate from the actual trajectory that stems from strategy execution. Also, there might be situations where the target vertices change to accommodate a modeling update. As a result, the strategy ${\sigma }_0$ computed as the solution to the RG might become inapplicable to the problem, leaving the agent unable to take appropriate actions to achieve its correct behavior. In other words, ${\sigma }_0$ is no longer winning for the game in place.

For this reason, the authors of [12] introduced Strategy Repair (SR), designed to address the problem of adjusting a given strategy to make it winning. Such an adjustment involves reconfiguring the strategy to select different arcs for the minimum number of vertices. This minimization requirement is motivated by the fact that every modification to the strategy incurs an implementation cost that must be kept limited. In addition to formally defining Strategy Repair in its basic form, the authors of [12] present theoretical and practical results related to it. First, they show that the problem is NP-complete via a reduction from Vertex Cover. Next, they introduce two algorithmic approaches. The first one provides an optimal solution to the problem and runs in time exponential in the input size. The second one provides an approximated solution and runs in time polynomial in the input size.

Despite extensive investigation of the problem from theoretical and practical standpoints, the work in [12] fails to fully exploit the graph-theoretical aspects of RGs and strategies. Their approach first identifies a set of vertices from which the repair algorithm must operate, then repairs the broken vertices, aiming to minimize the number of modifications.

Our paper contributes by working between these two steps. It does so by introducing a new notion of quotient over the set of vertices that depends on the strategy ${\sigma }_0$ that needs to be repaired. In doing so, it allows us to identify and collapse vertices that are equivalent from the perspective of Strategy Repair. As a result, we are able to introduce a quotient game, whose set of vertices is more compact compared to the original, but also equivalent in terms of solutions to the SR problem. Therefore, this allows us to solve an instance of SR by solving its quotient, whose size is reduced due to this compactification.

In addition to proving its theoretical properties, we conducted experiments comparing Strategy Repair algorithms with and without the quotient transformation, showing improvements in running time and accuracy for the approximated approaches.

As a by-product of this construction, we observed in the experiments that adopting the quotient game approach also improves the effect of $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$, an optimization condition introduced in [12]. Therefore, we also briefly discuss this effect from a theoretical perspective.

We here introduce the basic notions and definitions related to reachability games.

A 2-player arena, or simply an arena, is a directed graph $𝒜=(V,\mathrm{E})$ whose vertex set is partitioned into the two sets $V_0$ and $V_1$, where $V_0$ and $V_1$ are the sets of vertices controlled by Player 0 and Player 1, respectively. Moreover, every vertex is assumed to have at least one outgoing arc. A reachability game (or simply game) $𝒢=⟨𝒜,T⟩$ is a perfect-information 2-player turn-based game played on an arena $𝒜$, where the players are provided with a set $T\subseteq V$ of vertices, called terminal vertices. A token is initially placed on a vertex, and the player controlling the vertex hosting the token is asked to select an arc from that vertex and move the token along it. The aim of Player 0 is to bring the token to a vertex in $T$. Before formally specifying the objectives for the two players, we need to introduce additional notation.

A play of $𝒜$ is walk, i.e., an infinite sequence of vertices $\pi ={\pi }_0{\pi }_1{\pi }_2\mathrm{\dots }$ such that $({\pi }_i,{\pi }_{i+1})\in \mathrm{E}$, for every $i\in \mathbb{N}$. A partial play of $\pi$ is a finite subsequence ${\pi }_i\mathrm{\dots }{\pi }_j$, for some integers $i$ and $j$ with $i\le j$.

A strategy (for Player 0) is a function $\sigma :V_0\to \mathrm{E}$ mapping Player 0 vertices to arcs, such that, for each $v\in V_0$, $\sigma (v)$ is an arc outgoing from $v$. Intuitively, a strategy describes which arc Player 0 selects whenever it is its turn. A play $\pi$ is a consistent with a strategy $\sigma$ if $\sigma ({\pi }_i)=({\pi }_i,{\pi }_{i+1})$ for each ${\pi }_i\in V_0$.

We define a very natural distance between two strategies $\sigma$ and ${\sigma }^{\prime }$ over the same game, that is

It is proven in [12] that $\mathrm{𝖽𝗂𝗌𝗍}$ is in fact a distance.

A strategy $\sigma$ is called winning from $v$ if every play starting from $v$ consistent with $\sigma$ reaches a vertex in $T$. We say that a vertex $v$ is winning if there exists a strategy winning from $v$. By $\mathrm{Win}(𝒢)$, we denote the set of winning vertices $v$. A strategy $\sigma$ is winning if it is winning from all vertices in $\mathrm{Win}(𝒢)$.

Notice that we use strategies known as memoryless strategies, but more general strategies can be found in the literature, where the next arc is chosen based on the current partial play rather than solely on the current vertex. This restriction is without loss of generality, since for every reachability game there exists a memoryless winning strategy, which is computable in polynomial time [10, 11, 18].

An example of a reachability game is depicted in Figure 1.

For a given game $𝒢$ and strategy $\sigma$, we define $\mathrm{Win}(𝒢,\sigma )$ as the set of vertices from which $\sigma$ is winning for Player 0. Clearly, it always holds that $\mathrm{Win}(𝒢,\sigma )\subseteq \mathrm{Win}(𝒢)$, with $\mathrm{Win}(𝒢,\sigma )=\mathrm{Win}(𝒢)$ if and only if $\sigma$ is winning for Player 0.

Given a game $𝒢$ and a (not necessarily winning) strategy ${\sigma }_0$, a strategy $\sigma$ is a closest winning strategy with respect to ${\sigma }_0$, or simply closest winning when ${\sigma }_0$ is clear from the context, if it is winning in $𝒢$ and minimizes $\mathrm{𝖽𝗂𝗌𝗍}({\sigma }_0,\sigma )$ among all winning strategies in $𝒢$.

We are finally ready to define the central problem of this work.

This problem requires minimizing the number of modifications that are required to turn a strategy ${\sigma }_0$ into a winning strategy $\sigma$ for a given reachability game $𝒢$. The corresponding decision problem, instead, consists in fixing a given threshold $k\in \mathbb{N}$ and checking whether there exists a winning strategy $\sigma$ with $\mathrm{𝖽𝗂𝗌𝗍}({\sigma }_0,\sigma )\le k$, and is NP-complete [12].

Note that reaching any vertex in $\mathrm{Win}(𝒢,{\sigma }_0)$ guarantees reaching $T$ as well. So, given a reachability game $𝒢=⟨𝒜,T⟩$, the aim of the Strategy Repair problem is to change ${\sigma }_0$ into another strategy $\sigma$ which guarantees to reach any vertex in $\mathrm{Win}(𝒢,{\sigma }_0)$ from every other vertex in $\mathrm{Win}(𝒢)\setminus \mathrm{Win}(𝒢,{\sigma }_0)$. Therefore, the set $\mathrm{Win}(𝒢,{\sigma }_0)$ acquires the meaning of a new target set. For this reason, we denote from now on $\mathrm{Win}(𝒢,{\sigma }_0)$ by $T^{\prime }$. Moreover, we define $\mathrm{Fr}(T^{\prime })$ as the subset of arcs in the cut from $\mathrm{Win}(𝒢)\setminus T^{\prime }$ to $T^{\prime }$ and coming out from a vertex in $V_0$. An arc in $\mathrm{Fr}(T^{\prime })$ is called a frontier arc and the origin of a frontier arc is called a frontier vertex. Observe that for an arc $(u,v)\in \mathrm{Fr}(T^{\prime })$, it holds that ${\sigma }_0(u)\ne (u,v)$ since $u\notin T^{\prime }$.

In this section, we introduce a new notion of quotient game of an instance $(𝒢,{\sigma }_0)$ of SR. We then proceed by proving that such a quotient identifies the vertices of $𝒢$ that are equivalent from the perspective of repairing ${\sigma }_0$. Such a result is summarized in the statement of Theorem 4, whose proof is obtained by the application of some lemmas introduced here. Finally, we discuss the effect of the quotient construction on $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$: a selection condition introduced in [12] as an optimization for their algorithmic approach. We show that the quotient construction increases the number of times $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$ is triggered across all algorithmic approaches, thereby improving performance. We start by providing some useful notation and definitions.

Given a strategy $\sigma$, a vertex $u\in V_0$ and an arc $(u,v)$ outgoing from $u$, we define the strategy ${\sigma }_{(u,v)}$ exactly the same as $\sigma$ except in $u$, where ${\sigma }_{(u,v)}(u)=(u,v)$.

To iteratively repair ${\sigma }_0$ to a winning strategy, a frontier arc $(u,v)$ at the time must be selected to replace ${\sigma }_0(u)$. Such replacement ensures that $u$ enters the winning set of the modified strategy $\sigma _0^{}{}_{(u,v)}{}^{}$. A key part of the repair process is deciding which frontier arc to select. The aim of the construction introduced in this work is to facilitate this selection.

When a frontier arc $(u,v)$ is selected to replace ${\sigma }_0(u)$, the vertex $u$ might not be the only one that becomes winning for the modified strategy, since some vertices from which every play consistent with ${\sigma }_0$ leads to either $u$ or $T^{\prime }$ could exist. For this reason, we consider the repair set of $u$, denoted $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)$ and defined as the set of vertices that indirectly become winning when ${\sigma }_0$ is modified, changing ${\sigma }_0(u)$ to a frontier arc. Note that if $u$ is the origin of different frontier arcs, the same set $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)$ is obtained regardless of which frontier arc is chosen. So given any frontier arc $(u,v)$, we can formally define $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)=\mathrm{Win}(𝒢,\sigma _0^{}{}_{(u,v)}{}^{})\setminus T^{\prime }$.

We say that a frontier vertex $u$ is a base if for every frontier vertex $v$, it does not hold that $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)⊊\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(v)$. In other words, $u$ is a base if its repair set is maximal with respect to inclusion among the repair sets of frontier vertices. Two bases $u$ and $u^{\prime }$ are equivalent if and only if $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)=\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u^{\prime })$. Instead of referring to an equivalence class, we elect one base to represent the class itself. Let $\mathrm{𝖡𝖺𝗌𝖾𝗌}$ be the set of elected bases. In the following, we denote by $R$ the union of the repair sets of the bases, i.e., $R={\cup }_{u\in \mathrm{𝖡𝖺𝗌𝖾𝗌}}\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)$.

Note that the repair sets of vertices in $\mathrm{𝖡𝖺𝗌𝖾𝗌}$ are a partition of $R$. Indeed, suppose, by contradiction, there is a vertex $v\in \mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)\cap \mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u^{\prime })$, for two non-equivalent $u$ and $u^{\prime }$ in $\mathrm{𝖡𝖺𝗌𝖾𝗌}$. It is impossible that $u^{\prime }$ lies on a partial play consistent with ${\sigma }_0$ from $v$ to $u$ (and vice versa), because in this case it would be $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u^{\prime })\subseteq \mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)$, so either $u$ or $u^{\prime }$ would not be a base.

We now construct a reachability game $𝒬(𝒢,{\sigma }_0)$ induced from $𝒢$ and ${\sigma }_0$, where each of these repair sets is represented by a single vertex. To avoid confusion, vertices of the quotient game are denoted by $q_u$, where $u$ is a vertex of $𝒢$.

Strictly speaking, $𝒬(𝒢,{\sigma }_0)$ also depends on the elected bases: in particular, the frontier arcs of $𝒬(𝒢,{\sigma }_0)$ may vary depending on which base we elect for each equivalence class. Nevertheless, note that this detail does not imply substantial changes to the execution or quality of the proposed approach.

For every $u\in V$, we say that $q_u$ represents $u$ in $𝒬(𝒢,{\sigma }_0)$ if $q_u\in V^q$ while $q_v$ represents $u$ if $v\in \mathrm{𝖡𝖺𝗌𝖾𝗌}$ and $u\in \mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(v)$.

A strategy $\sigma$ in $𝒢$ is compatible with $𝒬(𝒢,{\sigma }_0)$ if it is equal to ${\sigma }_0$ when restricted to $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)\setminus \{u\}$, for every base $u$, i.e., $\sigma (v)={\sigma }_0(v)$ for every $v\in V_0\cap (\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)\setminus \{u\})$. Let $\sigma$ be a strategy compatible with $𝒬(𝒢,{\sigma }_0)$, we define the projected strategy ${\sigma }^q$ in $𝒬(𝒢,{\sigma }_0)$ as follows: for each $q_u\in V_0^{}{}_{}{}^q$ with $\sigma (u)=(u,v)$, then ${\sigma }^q(q_u)=(q_u,q_{v^{\prime }})$, where $q_{v^{\prime }}$ represents $v$ in $𝒬(𝒢,{\sigma }_0)$.

Intuitively, if $\sigma (u)=(u,v)$ is an arc entering the set $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(v^{\prime })$, the projected strategy directly takes the arc $(q_u,q_{v^{\prime }})$ since $q_{v^{\prime }}$ represents the set $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(v^{\prime })$ which has been collapsed in $𝒬(𝒢,{\sigma }_0)$. We say that a strategy $\sigma$ in $𝒢$ compatible with $𝒬(𝒢,{\sigma }_0)$ is an elevation of a strategy ${\sigma }^q$ in $𝒬(𝒢,{\sigma }_0)$ if ${\sigma }^q$ is the projection of $\sigma$. Note that an elevation of a strategy in $𝒬(𝒢,{\sigma }_0)$ is not necessarily unique.

Figure 2 shows an example of the construction of a quotient game, where ${\sigma }_0^q$ is the projected strategy of ${\sigma }_0$ and, reciprocally, ${\sigma }_0$ is an elevation of ${\sigma }_0^q$.

Similarly to what has been done with strategies, we now define the projection and elevation for plays.

We say that a play $\pi$ in $𝒢$ is compatible with $𝒬(𝒢,{\sigma }_0)$ if it is consistent with ${\sigma }_0$ within the set $\mathrm{𝖱𝖾𝗉𝖺𝗂𝗋}(u)\setminus \{u\}$, for every base $u$. Let $\pi$ be a play compatible with $𝒬(𝒢,{\sigma }_0)$, we define the projected play ${\pi }^q$ in $𝒬(𝒢,{\sigma }_0)$ obtained from $\pi$ as follows: for every integer $i$, the partial play ${\pi }_i{\pi }_{i+1}$ is replaced by

• $\mathrm{■}$

  $q_u{q}_v$, where $q_u$ represents ${\pi }_i$ and $q_v$ represents ${\pi }_{i+1}$, if $u\ne v$;

• $\mathrm{■}$

  nothing, otherwise.

Moreover, an elevation of a play ${\pi }^q$ in $𝒬(𝒢,{\sigma }_0)$ is a play $\pi$ compatible with $𝒬(𝒢,{\sigma }_0)$ such that the projection of $\pi$ is ${\pi }^q$. An example of all these definitions is shown in Figure 3.

We can now state the main result of this section.

As a consequence of Theorem 4, Strategy Repair on input $(𝒢,{\sigma }_0)$ can be solved in the following way: first, we construct $𝒬(𝒢,{\sigma }_0)$, then we solve Strategy Repair on input $(𝒬(𝒢,{\sigma }_0),{\sigma }_0^q)$, and finally return an elevation of the previously computed solution.

The rest of the section is devoted to introducing auxiliary results useful for proving Theorem 4. We begin with the following lemma, which plays a key role in showing that moving from $(𝒢,{\sigma }_0)$ to the induced quotient game preserves solutions.

In this section, we show that our new quotient game concept can substantially improve the performance of known algorithms for the strategy repair problem, in terms of both running time and accuracy (i.e., the ratio of the cardinalities of the approximate and exact solutions). The algorithms we consider are the (exponential time) exact algorithm, ${𝒜}_{ex}$, and the heuristic ${𝒜}_h$, described in [12], which are the only known in the literature, to the best of our knowledge. Clearly, we need to modify the algorithms so they can operate on the quotient graph. In particular, the quotient graph must be recomputed each time the current solution is updated, but this does not affect the correctness of the resulting solutions, thanks to Theorem 4. In the following, we use ${𝒜}_{ex}^{𝒢}$, ${𝒜}_h^{𝒢}$, ${𝒜}_{ex}^{𝒬}$, and ${𝒜}_h^{𝒬}$ to refer to the original algorithms for the input strategy repair problem and their modifications for the quotient game.

All tests have been run on an Intel Core i7-8700 CPU @ 3.20GHz, with 32GB of RAM and running Ubuntu 20.04.06 LTS.

For all the sets of experiments, we run the algorithms on many values of $|V|$ (reported in the first column of each table) and, for each fixed value of $|V|$, we generated $N$ instances ($N$ is set to 100 by default) either as random instances, or as instances deduced by vertex-cover instances.

Namely, to generate a random instance of a given size, each vertex is first assigned to either $V_0$ or $V_1$ with equal probability (0.5 each). In addition, each vertex is independently included in the target set $T$ with probability 0.05, yielding an expected target size of $5\%$ of $|V|$. For each vertex, its out-degree $d$ is uniformly drawn, and $d$ out-neighbors are then selected uniformly at random. We select $d$ either between $1\%$ and $5\%$ of $|V|$, generating sparse random instances, or between $40\%$ and $50\%$ of $|V|$, generating dense random instances.

The initial strategy ${\sigma }_0$ to be repaired is constructed as follows. For each vertex $v\in V_0$, if $v$ has at least one out-neighbor that does not belong to the target $T$, one such out-neighbor is chosen uniformly. Otherwise, an arbitrary out-neighbor is selected. This construction of ${\sigma }_0$ increases the chances that a number of arcs in ${\sigma }_0$ will require repair.

For the vertex-cover instances, an undirected graph with $|V|$ vertices and edge density of parameter $p$ is generated as follows: for each pair of vertices $\{i,j\}$, the edge $\{i,j\}$ is included independently with probability $p$. The corresponding strategy repair instance is then obtained via the reduction described in [12]. We conducted two series of experiments, one with $p=\frac{2}{|V|}$ and one with $p=0.1$, yielding instances referred as sparse and dense vertex-cover instances, respectively.

We introduced a timeout, set to 15 minutes by default. In all tables, the “No. of timeouts” column records the number of instances that were interrupted by a timeout. Moreover, in all tables, the running times of the algorithms executed on the quotient games also include the time necessary to pass from $𝒢$ to $𝒬$.

We performed a first set of experiments on random instances, comparing the running times of the exact algorithm in its two versions ${𝒜}_{ex}^{𝒢}$ and ${𝒜}_{ex}^{𝒬}$; the results are listed in Table 1. It is quite clear that introducing the quotient approach approximately halves the running time. It is worth noting that, when $|V|=100$ and $|V|=200$, the average time is much higher for ${𝒜}_{ex}^{𝒢}$ than for ${𝒜}_{ex}^{𝒬}$; this particular behavior can be explained with the presence of some particularly time-consuming instances: there are two instances with $|V|=100$ and running times of approximately 38 and 115 seconds, respectively, and two instances with $|V|=200$ whose the running time of the first one is approximately 56 seconds while the second one does not output a solution because it exceeds the timeout.

In a second set of experiments, we also introduced the heuristic to compare the solution’s accuracy, in addition to running times; the results are listed in Table 2. While the running times of ${𝒜}_{ex}^{𝒬}$ and ${𝒜}_h^{𝒬}$ are approximately the same, again they are about halved when running ${𝒜}_h^{𝒬}$ with respect to ${𝒜}_h^{𝒢}$ (see second column of Table 2). For this set of experiments, we used a timeout of 15 minutes, which was reached only by ${𝒜}_h^{𝒢}$ on instances of size $4000$; these instances therefore require the use of the quotient approach.

The third column records the number of times a $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$ condition is exploited, the fourth column represents the distance of the found solution from ${\sigma }_0$, and the fifth column relates the optimal solution (found by ${𝒜}_{ex}$) with the solutions found by the heuristic. The accuracy is, in any case, extremely high, and it tends to increase while $|V|$ grows; the reason is that, when the graph is larger, there are more candidates to find a frontier vertex satisfying the $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$ condition, in which case we are sure not to make an unnecessary modification. We can see this because the number of vertices satisfying the $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$ condition approaches the distance obtained. We observe that ${𝒜}_h^{𝒢}$ takes generally a longer time and finds vertices satisfying the $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$ condition slightly less frequently, inducing sometimes a negligible increase in the distance from the optimal solution.

The next set of experiments is the same as the previous one, but takes as input dense random instances. In this case, we obtain very similar results to the ones for sparse random instances in Table 2, except that the running times are higher: again, the running times are almost the same for ${𝒜}_{ex}^{𝒬}$ and ${𝒜}_h^{𝒬}$, and longer for ${𝒜}_h^{𝒢}$, and the accuracy is 1 for both polynomial algorithms. The results are presented in Table 3.

We changed the instance type for the fourth set of experiments to sparse vertex-cover instances. Table 4 shows that the running times of ${𝒜}_{ex}^{𝒬}$ and ${𝒜}_h^{𝒬}$ are comparable and that the accuracy of ${𝒜}_h^{𝒬}$ is very close to 1, showing a very good performance of our methodology based on the quotient game; on the contrary, a comparison between ${𝒜}_h^{𝒬}$ and ${𝒜}_h^{𝒢}$ highlights that not only ${𝒜}_h^{𝒢}$ is much slower (about one order of magnitude) but its accuracy is lower by a factor which is about 6/7. Note that we did not measure the running times of ${𝒜}_{ex}^{𝒢}$ as most instances reached the timeout without producing a solution.

Our last set of experiments has been run on dense vertex-cover instances, and the results are shown in Table 5.

In this case, the running times are much higher, and we could not run the exact algorithm on instances with more than 70 vertices without timing out. For such small instance sizes, the running times of both heuristics are very similar; however, we can observe a better accuracy for ${𝒜}_h^{𝒬}$. Nevertheless, it is worth noting that ${𝒜}_h^{𝒬}$ shows slightly lower accuracy on dense instances than on sparse ones.

We conclude this section observing that, both in Table 4 and in Table 5, no vertices satisfying the $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$ condition are found when running ${𝒜}_h^{𝒢}$; this is due to a result from [12], stating that the vertex-cover instances do not contain vertices satisfying the $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$ condition. On the contrary, the quotient graph construction generates vertices with the $\mathrm{𝖬𝗎𝗌𝗍𝖥𝗂𝗑}$ condition, therefore improving both the running time and the accuracy of the solution.