אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Dynamic graphs capture systems whose connectivity evolves. As edges are inserted and deleted, recomputing answers after each change becomes impractical, motivating algorithms that maintain information as the graph evolves. We study two counting problems on dynamic directed graphs, considered for every vertex simultaneously: (i) the size of its reachable set and (ii) the number of vertices within distance at most d. We present a simple randomized method that maintains (1±ε) estimates with polylogarithmic update and query times in the incremental model, with analogous guarantees for the decremental model on DAGs. Complementing these algorithms, we prove a conditional limitation, which motivates approximation: under SETH, no partially dynamic algorithm can simultaneously achieve sublinear update and query time for maintaining the exact sizes of reachable sets, even on DAGs and even when the entire update sequence is known in advance.