Average sensitivity of breadth-first search algorithm on grids

The average sensitivity of a graph algorithm is a measure that calculates the stability of the algorithm when the input graph undergoes perturbations. The perturbation is represented by removing some of the edges of the input graph, and the stability is quantified using the Earth mover's distance between the algorithm's outputs on the original and perturbed graphs. In this thesis, we investigate the average sensitivity of the Breadth-first search(BFS) algorithm with BFS trees as outputs. It is known that for an arbitrary graph G(V, E), the average sensitivity of the BFS algorithm is Θ(|V(G)|). We prove that when the input graph G is an m × n grid graph, there is a BFS algorithm with an average sensitivity of at most 2. We also prove that for specific starting nodes, the randomization of the BFS algorithm reduces its average sensitivity.