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

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

TL;DR

This paper establishes fundamental lower bounds on the number of symbolic operations required to solve crucial graph problems in the context of reactive system analysis. It reveals surprising separations between problems like reachability and safety, showing that some problems are inherently more complex in this symbolic computation model, even for graphs with small diameters.

What Problem Does This Paper Address?

Formal analysis of reactive systems often involves reasoning about huge, implicitly represented graphs. Symbolic algorithms provide a theoretical framework for operating on these graphs using restricted "symbolic operations" (like predecessor/successor queries on sets of nodes) instead of direct access to adjacency lists or matrices. The efficiency of these algorithms is measured by the number of these expensive symbolic operations. While upper bounds for many graph problems were known, there was a significant lack of theoretical lower bounds, making it difficult to assess the optimality of existing algorithms. This paper aims to fill this gap by providing unconditional lower bounds for fundamental graph problems, including computing strongly connected components (SCCs), checking for liveness and safety properties, and approximating graph diameter.

Methods

The core technical contribution of this paper is the use of reductions from communication complexity problems, specifically "Set Disjointness," to graph problems solvable by symbolic algorithms. By constructing specific graphs based on instances of Set Disjointness, the authors can translate communication lower bounds into lower bounds on the number of symbolic operations.

  • Reductions from Set Disjointness: The paper constructs graphs where evaluating certain symbolic operations (like Pre or Post on a set of vertices) requires communication between two simulated parties (Alice and Bob) who hold parts of the Set Disjointness instance. This allows them to argue that any symbolic algorithm solving the graph problem would imply a communication protocol for Set Disjointness.
  • Graph Constructions: Various graph constructions are used, carefully designed to have specific properties related to SCCs, diameter, or reachability, depending on the disjointness of the input sets in the Set Disjointness problem.
  • Analysis of Symbolic Operations: The analysis focuses on the number of "one-step" symbolic operations (Pre/Post), as basic set operations are considered much cheaper.

Datasets

Not discussed in the paper. The paper focuses on theoretical lower bounds and algorithms on abstract graphs, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Surprising Separation: Reachability can be solved efficiently with O(D) symbolic operations (where D is the diameter), but its dual problem, safety, requires Ω(n) operations even for constant-diameter graphs. This highlights that problem duality doesn't translate to equivalent complexity in the symbolic model.
  • SCCs are Fundamentally Linear: Computing Strongly Connected Components (SCCs) requires Ω(n) symbolic operations, even for graphs with constant diameter. This implies that algorithms relying on SCC decomposition for other problems will inherit this linear lower bound.
  • Diameter Approximation is Harder Than Expected: Even approximating the graph diameter within a factor of 3/2 requires Ω(n) symbolic operations, even for undirected, connected graphs with constant diameter. This is a significant result, as explicit graph algorithms face similar hardness for small diameters.
  • Diameter of SCCs Matters: The complexity of computing SCCs can be better characterized by the sum of the diameters of the individual SCCs, rather than just the overall graph diameter.

Key Results

  • Lower Bounds:
    • Safety, Liveness, and Co-Liveness objectives require Ω(n) symbolic operations, even for constant-diameter graphs.
  • Computing SCCs requires Ω(n) symbolic operations for constant-diameter graphs.
  • Approximating the graph diameter within a factor of (3/2 - ε) requires Ω(n) symbolic operations for undirected, connected graphs with constant diameter.
  • Reachability requires Ω(D) symbolic operations.
  • Upper Bounds:
    • A (1 + ε)-approximation for the graph diameter can be achieved in O(n√D) symbolic steps.
  • An improved analysis of an existing SCC algorithm shows an upper bound of O(Σc∈SCCs(G)(Dc + 1)) symbolic operations, where Dc is the diameter of SCC c.

Limitations and Future Work

  • Constant Factors and Specific Graph Classes: The lower bounds are often for "probabilistic bounded error or deterministic" algorithms. Further work could explore tighter bounds for specific classes of graphs or deterministic algorithms.
  • Open Questions for Diameter Approximation: The paper poses open questions about whether a o(n) c-approximation exists for c ∈ [3/2, 2) and if a linear (1 + ε)-approximation is possible for graphs with super-constant diameter.
  • Refined SCC Analysis: While an improved upper bound for SCCs is presented, the paper suggests further exploration of the relationship between SCC computation and graph parameters.
  • Practical Implications: While theoretical, these bounds provide crucial insights for designing efficient symbolic algorithms in practice, guiding researchers towards optimal solutions.

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 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 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.
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