This work focuses on cycles, a simple graph class which nevertheless captures a key difficulty of online exploration, and develops a randomized algorithm for online exploration of cycles, giving the first provable advantage of randomization in online graph exploration.
Abstract
In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting position, while the graph is revealed only locally at visited vertices. Although the problem has attracted considerable attention, previous work has focused exclusively on deterministic algorithms. Randomized strategies are often substantially harder to analyze because of a fundamental challenge inherent to exploration. In this work, we give the first positive result showing that randomization can improve competitive guarantees in online graph exploration. To this end, we focus on cycles, a simple graph class which nevertheless captures a key difficulty of online exploration. Our main contribution is \(\textsc{RandHeavyTest}\), a randomized algorithm for online exploration of cycles whose competitive ratio we prove to be at most 1.315. This establishes a strict separation from the deterministic setting, where the optimal competitive ratio is $\thickapprox 1.366$, and thus gives the first provable advantage of randomization in online graph exploration. A key step towards this result is a new, simplified optimal deterministic algorithm, \(\textsc{HeavyTest}\), whose formulation naturally suggests the randomized variant. We complement our upper bounds with lower bounds of 1.115 for arbitrary randomized algorithms and 1.207 for the natural class of so-called forward-greedy algorithms, which includes \(\textsc{RandHeavyTest}\).
The Gold Grabbing Game is a combinatorial game on vertex-weighted graphs in which two players alternately remove vertices while maintaining graph connectivity, aiming to maximize the total collected weight. Although the literature has primarily focused on strategies that guarantee victory, the question of optimality --- i.e., maximizing total gain --- remains less explored. In this work, we investigate the behavior of the greedy strategy in this setting. We show that this approach is not optimal for general split graphs, highlighting structural limitations of this class. On the other hand, we prove that for complete split graphs $CS_{(2,n)}$, the greedy strategy yields a sequence of moves that maximizes the game value. As a consequence, the first player does not lose when the number of vertices is even. These results contribute to a better understanding of the structural conditions that ensure the optimality of simple strategies in graph-based combinatorial games.
Heitor Melo de Lucas Brandão, H. C. Silva, J. Nascimento· 0 citations
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.
In this work, we consider combinatorial games in which two players alternately choose vertices from a finite graph until a winning condition is achieved. Specifically, we focus our investigation on the well-known game Kayles, in which the selected vertices must form an independent set, and the player who makes the last valid move wins (i.e., the player who chooses a vertex that completes a maximal independent set). Zermelo's Theorem guarantees that, in this scenario, one of the players has a winning strategy---that is, a sequence of moves that ensures a win regardless of the opponent's choices. Given a graph, the typical decision problem associated with this type of game consists of determining which player has a winning strategy. Answering this question means solving the game. We first consider Kayles played on caterpillars. Since caterpillars are interval graphs, an O(n3)-time algorithm for solving Kayles on this graph class is already known [Bodlaender and Kratsch, 2002]. However, we investigate scenarios in which this time complexity can be reduced to O(1) by extending the periodicity property presented in [Guignard and Sopena, 2009] to caterpillars. We prove that the nimber of any caterpillar is equal to the nimber of an equivalent reduced caterpillar, obtained by appropriately removing certain leaves from the original graph. By partitioning these reduced caterpillars into classes, we show that a period of 34 emerges in each investigated class, allowing the computation of nimbers to scale to graphs with a large number of vertices. We present a sufficient condition for a class of caterpillars to exhibit periodicity 34, using it to identify many periodic classes and to calculate the nimber of their caterpillars in O(1) time. Furthermore, we present an O(n2)-time dynamic programming algorithm for solving Kayles on powers of paths, improving upon the O(n4)-time complexity given in [Bodlaender and Kratsch, 2002]for graphs with an asteroidal number of at most 2. Finally, we show how this same O(n2)-time algorithm can be adapted to solve Kayles on powers of cycles, thereby reducing the O(n3)-time complexity previously established in [Bodlaender and Kratsch, 2002] for circular-arc graphs.
Marcos Felipe Medeiros-de-Souza, Felipe Eizo Hanada, F. Protti· Journal of the Brazilian Com...· 0 citations
We study stochastic multi-armed bandits on dynamic graphs, where arms correspond to the vertices of a network with time-varying edges. In this setting, the learner is restricted to local movement, selecting only its current node or an immediate neighbor at each round. This constraint decouples best-arm identification from exploitation: even after the optimal arm is identified, the learner may remain unable to reach it through the evolving topology. We identify a process-agnostic structural condition, based on sliding-window mixing, that ensures the graph's intrinsic walk remains stable for both exploration and navigation. Under this regime, we analyze a family of local explore-then-commit algorithms and establish sublinear expected regret. Our framework includes a reward-aware strategy, for which we prove a worst-case safety theorem and a separate performance gain theorem.
Sourav Chakraborty, Amit Kiran Rege, C. Monteleoni et al.· 0 citations
P-SAPST Lite replaces peeling with a degree order and provides a lower latency order choice within the same framework and complements edge oblivious streaming APST by addressing an offline regime in which structural plans can be reused.
Rong Fu, Yongtai Liu, Xiaowen Ma et al.· 0 citations
ABSTRACT We address the Positive Influence Dominating Set problem (PIDS), which involves identifying the smallest group of vertices in a given network that maximizes influence throughout the network. Formally, given a graph G = (V, E), representing the network, we look for a subset of vertices P ⊆ V such that each vertex v i ∈ V \ P has at least ρ deg G (v i ) neighbors in P, where deg G (v i ) is the degree of v i , and 0 < ρ < 1. The problem is known to be NP-hard in general graphs and remains NP-hard even when restricted to certain particular classes, such as chordal graphs. In this paper, we develop an exact algorithm based on the Branch and Bound approach for solving PIDS on chordal graphs. The effectiveness of the proposed algorithm is demonstrated through numerical experiments conducted on various randomly generated chordal graphs.
Y A Bekhti, M. Lalou, Méziane Aïder et al.· Pesquisa Operacional· 0 citations