Reachability in graph timelines
Jakub Łącki, Piotr Sankowski · 2013
In this paper we consider the problem of maintaining information about graphs with history -- so called graph timeline. A graph timeline is a sequence of graphs G1,..., Gt, in which consecutive graphs are obtained from previous ones by small modifications, e.g., by adding or removing a single edge. We aim to devise algorithms that after some preprocessing are able to efficiently answer queries about the existence of paths in the entire timeline of the graph, or within some time interval. We consider two types of queries: [forall (u,v,a,b)] --- query that checks if there exists a path from u to v in each of Ga,..., Gb; [exists(u,v,a,b)] --- query that checks if there exists a path from u to v in any of Ga,...,Gb. Our study is motivated by the recent intensive study of the evolution of graphs, and the question whether information about history can be efficiently aggregated. We show that for path queries this is, somewhat astonishingly, true. In some cases it is possible to preprocess graph timeline and answer such queries in almost optimal time.