Graph certificates, lookahead in dynamic graph problems, and assembly planning in robotics

摘要

Despite intensive efforts in the area of dynamic graph algorithms, no efficient algorithms are known for the dynamic versions of some basic graph problems such as strong connectivity and transitive closure. We provide some explanation for this lack of success by presenting quadratic lower bounds on the strong certificate complexity of such problems, thereby establishing the inapplicability of the only known general technique for designing dynamic graph algorithms, viz., sparsification. These results also provide evidence of the inherent intractability of such dynamic graph problems. Some of our results are based on a general technique for obtaining lower bounds on the strong certificate complexity for a class of graph properties by establishing a relationship with the witness complexity. In many real applications of dynamic graph problems, a certain amount of lookahead is available. Specifically, we consider the problems of assembly planning in robotics and the maintenance of relations in databases which, respectively, give rise to dynamic strong connectivity and transitive closure. We exploit the (naturally available) lookahead in these two applications to circumvent the inherent complexity of the dynamic graph problems. We propose a variant of sparsification, viz., lookahead based sparsification, and apply it to obtain the first efficient fully dynamic algorithms for strong connectivity and transitive closure.