Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter

Krishnendu Chatterjee, Wolfgang Dvorák, Monika Henzinger, Veronika Loitzenbauer

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 symbolic operations, which are expensive in comparison to standard RAM operations. This paper establishes the first unconditional lower bounds for symbolic graph algorithms, proving that fundamental tasks like finding strongly connected components (SCCs) or checking safety properties require at least $\Omega(n)$ operations. These lower bounds reveal a significant separation between these problems and the reachability problem, which can be solved in $O(D)$ operations, where $D$ is the graph diameter. Additionally, the authors present a novel $(1+\epsilon)$-approximation algorithm for the graph diameter and provide a refined analysis of existing SCC algorithms.

The Symbolic Model and the Reachability Paradox

In the formal analysis of reactive systems (such as microprocessors or flight controllers), the state space is often astronomical. Symbolic algorithms handle this by manipulating sets of states using operations like Binary Decision Diagrams (BDDs) rather than individual vertices. The primary computational cost is measured in "symbolic steps"—operations like finding the predecessors or successors of a set.

For decades, a "Reachability Paradox" has been observed: while reachability (can I get from A to B?) takes $O(D)$ steps, its dual problem, Safety (do I always stay in a good set?), appeared to take $O(n)$ steps. This research proves that this gap is inherent and unavoidable, even for graphs with constant diameter.

Key Results: The Complexity Gap

The paper provides a definitive table of bounds for symbolic operations. The most striking finding is that while Reachability depends on the diameter ($D$), problems like SCC, Safety, and Liveness depend on the number of vertices ($n$).

Table 1: Summary of symbolic operation bounds for reachability, SCC, safety, and Büchi/coBüchi properties.

Furthermore, the authors show that the state-of-the-art SCC algorithm by Gentilini et al. is actually optimal, with a complexity proportional to the sum of the diameters of the individual strongly connected components.

Methodology: Communication Complexity

To prove these lower bounds, the authors link symbolic computation to Communication Complexity. They use a reduction from the Set Disjointness problem, a well-known problem where two parties must determine if their sets share elements using minimal communication. By constructing specific "gadget" graphs where symbolic operations can be simulated with few bits of communication, they demonstrate that a sub-linear symbolic algorithm would contradict established communication complexity limits.

Approximating Graph Diameter

While exact diameter computation is shown to require $\Omega(n)$ steps, the paper introduces a new approximation strategy. The authors found that a $(1 + \epsilon)$-approximation can be achieved much faster than the naive $O(n \cdot D)$ approach by using a greedy "dominating set" strategy adapted for symbolic sets.

Table 2: Upper and lower bounds for exact and approximate diameter computation in the symbolic model.

This new algorithm achieves a $(1 + \epsilon)$-approximation in $\tilde{O}(n\sqrt{D})$ symbolic steps, bridging the gap between the efficient 2-approximation and the costly exact calculation.

Conclusion

This work provides a theoretical breakthrough by establishing the fundamental limits of symbolic algorithms. By proving linear lower bounds for safety and SCC problems, it justifies the observed performance of existing verification tools. Future research may focus on closing the remaining gaps in diameter approximation thresholds and exploring the impact of BDD size on these complexity bounds.

Summary updated

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 co-liveness. 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 $\tilde{O}(n \sqrt{D})$ symbolic steps to achieve a $(1+\epsilon)$-approximation for any constant $\epsilon > 0$. This compares to $O(n \cdot 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 Gentilini et al., showing that it uses an optimal number of symbolic steps that is proportional to the sum of the diameters of the strongly connected components.
BibTeX
@inproceedings{chatterjee2018lower,
  author = {Krishnendu Chatterjee and Wolfgang Dvorák and Monika Henzinger and Veronika Loitzenbauer},
  title = {{Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter}},
  booktitle = {SODA},
  year = {2018},
  doi = {10.1137/1.9781611975031.151},
}
Figure