ON CERTIFICATES AND LOOKAHEAD IN DYNAMIC GRAPH PROBLEMS

Recent work in dynamic graph algorithms has led to efficient algorithm s for dynamic undirected graph problems such as connectivity. However, no efficient deterministic algorithms are known for the dynamic versi ons of fundamental directed graph problems like strong connectivity an d transitive closure, as well as some undirected graph problems such a s maximum matchings and cuts. We provide some explanation for this lac k of success by presenting quadratic lower bounds on the certificate c omplexity of the seemingly difficult problems, in contrast to the know n linear certificate complexity for the problems which have efficient dynamic algorithms. In many applications of dynamic (di)graph problems , a certain form of lookahead is available. Specifically, we consider the problems of assembly planning in robotics and the maintenance of r elations in databases. These give rise to dynamic strong connectivity and dynamic transitive closure problems, respectively. We explain why it is reasonable, and indeed natural and desirable, to assume that loo kahead is available in these two applications. Exploiting lookahead to circumvent their inherent complexity, we obtain efficient dynamic alg orithms for strong connectivity and transitive closure.