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 constantdiameter 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 2approximation. 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:

20180101

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 ICT15003. K. C. is partially supported by the Austrian Science Fund (FWF) NFN Grant No S11407N23 (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/20072013) / ERC Grant Agreement no. 340506.

Open access: 
no 