Sequential metric dimension for random graphs

2020. 02. 13. 16:15
Gergely Ódor (EPFL Lausanne)

For a graph G=(V,E), a subset R of V is a resolving set if for every pair of distinct nodes v_1, v_2 in V there is a (distinguishing) node w in R, for which the distances d(w,v_1) and d(w,v_2) are not equal. An equivalent definition of a resolving set R is that in a two-player localization game, no matter which node v* Player 1 selects, Player 2 can guess v* only from the distance queries d(w_i,v*) for w_i in R. The metric dimension (MD) is defined as the minimum cardinality of R; it can be thought of as the minimum number of prewritten distance queries Player 2 needs to guess any v* in V. In this talk we consider the sequential version of the MD (called SMD), which can be defined using the same localization game, except now the queries can be adaptive. We are interested how much adaptivity can help to reduce the number of required queries in G(n,p) random graphs with p>>log(n)/n. In the first part of the talk, we review the previous results of Bollobas, Mitsche and Pralat (2012) on the MD of G(n,p), including the observation that unlike most graph properties, the MD is not monotonic in p, instead it follows zig-zag behavior. In the second part of the talk, we introduce the main tools that allow us to extend these results to the SMD, and quantify reduction of the SMD compared to the MD. We will discuss connections with source localization of epidemic processes, binary search on graphs and the birthday paradox.

This is joint work with Patrick Thiran.