Sequential metric dimension for random graphs

Gergely Ódor, Patrick Thiran

Research output: Contribution to journalArticlepeer-review

Abstract (may include machine translation)

In the localization game on a graph, the goal is to find a fixed but unknown target node with the least number of distance queries possible. In the jth step of the game, the player queries a single node and receives, as an answer to their query, the distance between the nodes and. The sequential metric dimension (SMD) is the minimal number of queries that the player needs to guess the target with absolute certainty, no matter where the target is. The term SMD originates from the related notion of metric dimension (MD), which can be defined the same way as the SMD except that the player's queries are non-adaptive. In this work we extend the results of Bollobás, Mitsche, and Prałat [4] on the MD of ErdÅ's-Rényi graphs to the SMD. We find that, in connected ErdÅ's-Rényi graphs, the MD and the SMD are a constant factor apart. For the lower bound we present a clean analysis by combining tools developed for the MD and a novel coupling argument. For the upper bound we show that a strategy that greedily minimizes the number of candidate targets in each step uses asymptotically optimal queries in ErdÅ's-Rényi graphs. Connections with source localization, binary search on graphs, and the birthday problem are discussed.

Original languageEnglish
Pages (from-to)909-951
Number of pages43
JournalJournal of Applied Probability
Volume58
Issue number4
DOIs
StatePublished - 2 Dec 2021
Externally publishedYes

Keywords

  • binary search on graphs
  • expansion properties of ErdÅ's-Rényi graphs
  • Source detection

Fingerprint

Dive into the research topics of 'Sequential metric dimension for random graphs'. Together they form a unique fingerprint.

Cite this