Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety and diameter Conference Paper


Author(s): Chatterjee, Krishnendu; Dvorák, Wolfgang; Henzinger, Monika; Loitzenbauer, Veronika
Title: Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety and diameter
Title Series: SODA
Affiliation IST Austria
Abstract: A model of computation that is widely used in the formal analysis of reactive systems is symbolic algorithms. In this model the access to the input graph is restricted to consist of symbolic operations, which are expensive in comparison to the standard RAM operations. We give lower bounds on the number of symbolic operations for basic graph problems such as the computation of the strongly connected components and of the approximate diameter as well as for fundamental problems in model checking such as safety, liveness, and coliveness. Our lower bounds are linear in the number of vertices of the graph, even for constant-diameter graphs. For none of these problems lower bounds on the number of symbolic operations were known before. The lower bounds show an interesting separation of these problems from the reachability problem, which can be solved with O(D) symbolic operations, where D is the diameter of the graph. Additionally we present an approximation algorithm for the graph diameter which requires Õ(n/D) symbolic steps to achieve a (1 +ϵ)-approximation for any constant > 0. This compares to O(n/D) symbolic steps for the (naive) exact algorithm and O(D) symbolic steps for a 2-approximation. Finally we also give a refined analysis of the strongly connected components algorithms of [15], showing that it uses an optimal number of symbolic steps that is proportional to the sum of the diameters of the strongly connected components.
Keywords: model checking; Symbolic algorithms; Refined analysis; approximation algorithms; Strongly connected component; Exact algorithms; Model of computation; Reachability problem; Symbolic computation; Symbolic operations
Conference Title: 29th Annual ACM SIAM Symposium on Discrete Algorithms SODA 2018
Conference Dates: January 7 - 10, 2018
Conference Location: New Orleans, LA, USA
ISBN: 9781611975031
Publisher: ACM  
Date Published: 2018-01-01
Start Page: 2341
End Page: 2356
DOI: 10.1137/1.9781611975031.151
Notes: All authors are partially supported by the Vienna Science and Technology Fund (WWTF) through project ICT15-003. K. C. is partially supported by the Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE) and an ERC Start grant (279307: Graph Games). V. L. is partially supported by the ISF grant #1278/16 and an ERC Consolidator Grant (project MPM). For W. D. and M. H. the research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 340506.
Open access: no
IST Austria Authors
Related IST Austria Work