Lower Bounds for Symbolic Computation on Graphs:
Strongly Connected Components, Liveness, Safety, and Diameter
Krishnendu Chatterjee1 , Wolfgang Dvořák2 , Monika Henzinger3 , and
Veronika Loitzenbauer3,4
1

IST Austria
TU Wien, Institute of Information Systems, Vienna, Austria
3
University of Vienna, Faculty of Computer Science, Vienna, Austria
4
Bar-Ilan University

arXiv:1711.09148v1 [] 24 Nov 2017

2

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
√
Õ(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 [GPP08], showing that it uses an optimal number of symbolic steps
that is proportional to the sum of the diameters of the strongly connected components.

1

Introduction

Graph algorithms are central in the formal analysis of reactive systems. A reactive system consists
of a set of variables and a state of the system corresponds to a set of valuations, one for each of
these variables. This naturally induces a directed graph: Each vertex represents a state of the system
and each directed edge represents a state transition that is possible in the system. As the number of
vertices is exponential in the number of variables of the system, these graphs are huge and, thus, they
are usually not explicitly represented during their analysis. Instead they are implicitly represented
using e.g., binary-decision diagrams (BDDs) [Bry86, Bry92]. To avoid considering specifics of the
implicit representation and their manipulation, an elegant theoretical model for algorithms that work
on this implicit representation has been developed, called symbolic algorithms (see e.g. [Bur+ 90,
Cla+ 96, Som99, CGP99, Cla+ 03, GPP08, Cha+ 13]). In this paper we will give novel upper and
(unconditional) lower bounds on the number of operations required by a symbolic algorithm for
solving classic graph-algorithmic questions, such as computing the strongly connected components
and the (approximate) diameter, as well as for graph-algorithmic questions that are important in the
analysis of reactive systems, such as safety, liveness, and co-liveness objectives. Our lower bounds
are based on new reductions of problems from communication complexity to symbolic algorithms.
Symbolic algorithms. A symbolic algorithm is allowed to use the same mathematical, logical,
and memory access operations as a regular RAM algorithm, except for the access to the input graph:
It is not given access to the input graph through an adjacency list or adjacency matrix representation
but instead only through two types of symbolic operations:
1. One-step operations Pre and Post: Each predecessor (Pre) (resp., successor (Post)) operation
is given a set X of vertices and returns the set of vertices Y with an edge to (resp., edge from)
some vertex of X.
2. Basic set operations: Each basic set operation is given one or two sets of vertices and performs
a union, intersection, or complement on these sets.
An initial set of vertices is given as part of the input, often consisting of a single vertex.
Symbolic operations are more expensive than the non-symbolic operations and thus one is mainly
interested in the number of symbolic operations of such an algorithm (and the exact number of
non-symbolic operations is often neglected). Moreover, as the symbolic model is motivated by the
compact representation of huge graphs, we aim for symbolic algorithms that only store O(1) or
O(log n) many sets of vertices as otherwise algorithms become impractical due to the huge space
requirements. Additionally, every computable graph-algorithmic question can be solved with 2n
symbolic one-step operations when storing O(n) many sets (and allowing an unbounded number of
non-symbolic operations): For every vertex v perform a Pre and a Post operation, store the results,
which represent the full graph, and then compute the solution on this graph, using only non-symbolic
operations. Note, however, that our lower bounds do not depend on this requirement, i.e., they
also apply to symbolic algorithms that store an arbitrary number of sets. Furthermore the basic set
operations (that only require vertices, i.e., the current state variables) are computationally much less
expensive than the one-step operations (that involve both variables of the current and of the next
state). Thus, to simplify the analysis of symbolic algorithms, we only analyze the number of one-step
operations in the lower bounds that we present. For all upper bounds in prior work and in our work
the number of basic-set operations is at most linear in the number of one-step operations.
There is an interesting relationship between the two types of symbolic operations and Boolean
matrix-vector operations: Interpreting the edge relationship as a Boolean matrix and a vertex set
as a Boolean vector, the one-step operations correspond to (left- and right-sided) matrix-vector
multiplication, where the matrix is the adjacency matrix, and basic set operations correspond to basic

1

vector manipulations. Thus, an equivalent way of interpreting symbolic algorithms is by saying that
the access to the graph is only allowed by performing a Boolean matrix-vector multiplication, where
the vector represents a set of vertices and the matrix is the adjacency matrix.
Note also that there is a similarity to the CONGEST and the LOCAL model in synchronous
distributed computation, as in these models each vertex in a synchronous network knows all its
neighbors and can communicate with all of them in one round (exchanging O(log n) bits in the
CONGEST model), and the algorithmic complexity is measured in rounds of communication. While
in these models all neighbors of every individual vertex, i.e., all edges of the graph, can be determined
in one round of communication, in the symbolic model this might require n Pre and n Post operations,
each on an singleton set. Thus, determining (and storing) all edges of a symbolically represented
graph is expensive and we would ideally like to have algorithms that use sub-linear (in the number of
vertices) many symbolic one-step operations.
Objectives. First we formally introduce the most relevant graph-algorithmic questions from the
analysis of reactive systems [MP92]. Given a graph G = (V, E) and a starting vertex s ∈ V , let Ps
be the set of infinite paths in G starting from s. Each objective corresponds to a set of requirements
on an infinite path and the question that needs to be decided by the algorithm is whether there is a
path in Ps that satisfies these requirements, in which case we say the path satisfies the objective. An
objective A is the dual of an objective B if a path satisfies A iff it does not satisfy B.
Let T ⊆ V be a set of target vertices given as input. The most basic objective is reachability
where an infinite path satisfies the objective if the path visits a vertex of T at least once. The dual
safety objective is satisfied by infinite paths that only visit vertices of T . The next interesting objective
is the liveness (aka Büchi) objective that requires an infinite path to visit some vertex of T infinitely
often. The dual co-liveness (aka co-Büchi) objective requires an infinite path to eventually only visit
vertices in T . Verifying these objectives are the most fundamental graph-algorithmic questions in the
analysis of reactive systems.
Computing the strongly connected components (SCCs) is at the heart of the fastest algorithms for
liveness and co-liveness: For example, there is a reduction from liveness to the computation of SCCs
that takes symbolic steps in the order of the diameter of the graph. Thus, determining the symbolic
complexity of SCCs also settles the symbolic complexity of liveness.
Furthermore, the diameter computation plays a crucial role in applications such as bounded
model-checking [Bie+ 03], where the goal is to analyze the system for a bounded number of steps,
and it suffices to choose the diameter of the graph as bound. Second, in many scenarios, such as in
hardware verification, the graphs have small diameter, and hence algorithms that can detect if this is
the case and then exploit the small diameter are relevant [Bie+ 03]. Motivated by these applications,
we define the diameter of a graph as the largest finite distance in the graph, which coincides with the
usual graph-theoretic definition on strongly connected graphs and is more general otherwise.
Note that linear lower bounds for the number of symbolic operations are non-trivial, since a
one-step operation can involve all edges. For example, to determine all the neighbors of a given
vertex v takes one symbolic operation, while it takes O(deg(v)) many operations in the classic
setting. In the following we use n to denote the number of vertices of a graph G and D(G) = D to
denote its diameter.
Previous results. To the best of our knowledge, no previous work has established lower bounds for
symbolic computation.
There is some prior work on establishing upper bounds on the number of symbolic operations:
In [GPP08] a symbolic algorithm that computes the SCCs with O(n) symbolic operations is presented.
This algorithm leads to an algorithm for liveness and co-liveness with O(n) symbolic operations and
improves on earlier work by [BGS06], which requires O(n log n) symbolic operations.

2

Table 1: Bounds on the number of required symbolic operations for different tasks. Θ(n) bounds
hold even for graphs with constant diameter D.
Reach(T )

SCC

Safe(T )

Büchi(T )

coBüchi(T )

Θ(D)

Θ(n)

Θ(n)

Θ(n)

Θ(n)

Table 2: Bounds on the number of symbolic operations for approximating the diameter of a graph.
The lower bounds even hold for strongly connected graphs with constant diameter D.
approx.
upper bound
lower bound

exact
O(n · D)
Ω(n)

1+ε
√
e
O(n
D)
Ω(n)

3/2 − ε
√
e
O(n
D)
Ω(n)

2
O(D)

Note that for the reachability objective the straightforward algorithm requires O(D) symbolic
operations: Starting from the set containing only the start vertex s, repeatedly perform a Postoperation until T is reached. For safety the straightforward algorithm takes O(n) symbolic operations:
Iteratively remove from F vertices that do not have an outgoing edge to another vertex of F , i.e.,
vertices of F \ Pre(F ), until a fixed point is reached.
Finally, there is a trivial algorithm for computing the diameter of the graph: Simply determine the
depth of a breadth-first search from every vertex and output the maximum over all depths. Computing
the depth of a breadth-first search can be done with O(D) many symbolic steps, thus this requires
O(nD) many symbolic steps in total. In a strongly connected graph a 2-approximation of the
diameter of the graph can be obtained by computing one breadth-first search from and one to some
arbitrary vertex and output the sum of the depths. This takes O(D) symbolic steps.
Our contributions. Our main contributions are novel lower bounds for the number of symbolic
operations for many of the above graph-algorithmic questions, leading to an interesting separation
between seemingly similar problems.
1. For reachability objectives, the basic symbolic algorithm requires O(D) symbolic operations.
Quite surprisingly, we show that such diameter-based upper bounds are not possible for its
dual problem, namely safety, and are also not possible for liveness and co-liveness objectives.
Specifically, we present tight lower bounds to show that, even for constant-diameter graphs,
Ω(n) one-step symbolic operations are required for safety, liveness, and co-liveness objectives.
In addition we establish tight bounds for symbolic operations required for the computation
of SCCs, showing a lower bound of Ω(n) for constant-diameter graphs. See Table 1 for a
summary of these results.
2. We show that even for strongly-connected constant-diameter graphs approximating the diameter
requires Ω(n) symbolic steps. More precisely, any (3/2 − ε)-approximation algorithm requires
Ω(n) symbolic one-step operations, even for undirected and connected graphs with constant
diameter. We also give a novel upper√bound: We present a (1 + ε)-approximation algorithm
e
for any constant ε > 0 that takes O(n
D) symbolic steps. This can be compared to the trivial
O(D) 2-approximation algorithm and the O(nD) exact algorithm. Notice that for explicitly
represented graphs the approximation of the diameter is already hard for constant-diameter
graphs while in the symbolic model there exists a trivial O(n) upper bound in this case, thus
showing a lower bound of Ω(n) is non-trivial. See Table 2 for a summary of these results.
3. Finally we give a refined analysis of the number of symbolic steps required for computing
strongly connected components based on a different problem parameter. Let SCCs(G) be

3

the set of all SCCs of G and DC the diameter of the strongly connected component C.
WePgive matching upper and lower bounds showing P
that the SCCs can be computed with
Θ( C∈SCCs(G) (DC + 1)) symbolic steps. Note that C∈SCCs(G) (DC + 1) can be a factor
n larger than D(G).
Key technical contribution. Our key technical contribution is based on the novel insight that lower
bounds for communication complexity can be used to establish lower bounds for symbolic computation. We feel that this connection is of interest by itself and might lead to further lower bounds for
symbolic algorithms.
Our lower bounds are by two kinds of reductions, both from the communication complexity
problem of Set Disjointness with k elements. First, we give reductions that construct graphs such that
one-step operations can be computed with O(1) bits of communication between Alice and Bob and
thus allow for linear lower bounds √
on the number symbolic operations.
Second, we give a reduction
√
that constructs a graph with only k many vertices, i.e., n = k, but allows one-step operations
to require O(n) bits of communication. This again results in linear lower bounds on the number of
symbolic operations.

2

Preliminaries

Symbolic Computation. We consider symbolic computation on graphs. Given an input graph
G = (V, E) and a set of vertices S ⊆ V , the graph G can be accessed only by the following two
types of operations:
1. Basic set operations like ∪, ∩, \, ⊆, and =;
2. One-step operations to obtain the predecessors or successors of the vertices of S in G. In
particular we define the operations
Pre(S) = {v ∈ V | ∃s ∈ S : (v, s) ∈ E} and Post(S) = {v ∈ V | ∃s ∈ S : (s, v) ∈ E} .
In the applications the basic set operations are much cheaper as compared to the one-step operations.
Thus we aim for lower bounds on the number of one-step operations, while not accounting for
set operations. In all our upper bounds the number of set operations is at most of the same order
as the number of one-step operations. Note that there is a one-to-one correspondence between a
one-step operation and a Boolean matrix-vector multiplication with the adjacency matrix and that for
undirected graphs Pre and Post are equivalent.
Communication Complexity Lower Bound for Set Disjointness. Our lower bounds are based on
the known lower bounds for the communication complexity of the Set Disjointness problem. The
classical symmetric two-party communication complexity model is as follows [KN97]. There are
three finite sets X, Y, Z, the former two are possible inputs for a function f : X × Y → Z, where
the actual input x ∈ X is only known by Alice, and the actual input y ∈ Y is only known by Bob.
Alice and Bob want to evaluate a function f (x, y) while sending as few bits as possible to each other.
The communication happens according to a fixed protocol, known to both players beforehand, that
determines which player sends which bits when, and when to stop.
Set Disjointness. In the Set Disjointness problem we have a universe U = {0, 1, . . . , k − 1} of
k elements and both sets X, Y contain all bit vectors of length k, i.e., they represent all possible
subsets of U and are of size 2k . Alice has a vector x ∈ X and Bob has a vector y ∈ Y , and the
function f is defined as f (x, y) = 1 if for all 0 ≤ i ≤ k − 1 either xi = 0 or yi = 0, and f (x, y) = 0
otherwise. We will sometimes use Sx and Sy to denote the sets corresponding to the vectors x and

4

v0,0

v0,1

v0,2

v1,0

v1,1

v1,2

Figure 1: Reduction 3.1 for k = 4, ` = 2, Sx = {2, 3}, Sy = {0, 1, 3}
y, i.e., Sx = {i | xi = 1} and Sy = {i | yi = 1} and f (x, y) = 1 iff Sx ∩ Sy = ∅. We next state a
fundamental lower bound for the communication complexity of the Set Disjointness problem which
will serve as basis for our lower bounds on the number of symbolic operations.
Theorem 2.1 ([KS92, Raz92, Bar+ 04, HW07, KN97]). Any (probabilistic bounded error or deterministic) protocol for the Set Disjointness problem sends Ω(k) bits in the worst case over all
inputs.

3

Lower Bounds

In this section we present our lower bounds, which are the main results of the paper.

3.1

Lower Bounds for Computing Strongly Connected Components

We first consider the problem of computing the strongly connected components (SCCs) of a symbolically represented graph. The best known symbolic algorithm is by Gentilini et al. [GPP08] and
computes the SCCs of a Graph G with O(min(n, D · |SCCs(G)|)) symbolic one-step operations
and thus matches the linear running time of the famous Tarjan algorithm [Tar72] in the non-symbolic
world.
We provide lower bounds showing that the algorithm is essentially optimal, in particular we show
that O(D) algorithms are impossible. These lower bounds are by reductions from the communication
complexity problem of Set Disjointness to computing SCCs in a specific graph. In particular, we
show that any algorithm that computes SCCs with o(n) symbolic one-step operations would imply a
communication protocol for the Set Disjointness problem with o(k) communication.
Reduction 3.1. Let (x, y) be an instance of Set Disjointness and let w.l.o.g. k = ` · k̄ for some
integers `, k̄. We construct a directed graph G
= (V, E) with n = k + ` vertices and O(n2 ) edges as
S`−1
follows. (1) The vertices are given by V = i=0 Vi with Vi = {vi,0 , . . . , vi,k̄ }. (2) There is an edge
from vi,j to vi0 ,j 0 if either i < i0 or i = i0 and j < j 0 . (3) For 0 ≤ i < `, 0 ≤ j < k̄ there is an edge
from vi,j+1 to vi,j iff xi·k̄+j = 0 or yi·k̄+j = 0.
In our communication protocol both Alice and Bob compute the number of SCCs on the graph
from Reduction 3.1, according to a given algorithm. While both know all the vertices of the graph,
they do not know all the edges (some depend on both x and y) and thus whenever such an edge is
relevant for the algorithm, Alice and Bob have to communicate with each other. We show that the
graph is constructed such that for each subset S ⊆ V the operations Pre(S) and Post(S) can be
computed with only four bits of communication between Alice and Bob.
Theorem 3.2. Any (probabilistic bounded error or deterministic) symbolic algorithm that computes
the SCCs of graphs with n vertices needs Ω(n) symbolic one-step operations. Moreover, for a graph
with the set SCCs(G) of SCCs and diameter D any algorithm needs Ω(|SCCs(G)| · D) symbolic
one-step operations.

5

We first show that Reduction 3.1 is a valid reduction from the Set Disjointness problem to an
SCC problem. The missing proofs are given in Section 6.1.
Lemma 3.3. f (x, y) = 1 iff the graph constructed in Reduction 3.1 has exactly ` SCCs.
The critical observation for the proof of Theorem 3.2 is that any algorithm that computes SCCs
with N many symbolic one-step operations implies the existence of a communication protocol for
Set Disjointness that only requires O(N ) communication.
Lemma 3.4. For any algorithm that computes SCCs with N symbolic one-step operations there is a
communication protocol for Set Disjointness that requires O(N ) communication.
Proof. In our communication protocol both Alice and Bob consider the graph from Reduction 3.1.
We call edges of the graph that are present independently of x and y definite edges and edges whose
presence depends on x and y possible edges.
Both Alice and Bob execute the given symbolic algorithm to decide whether the graph has `
SCCs (cf. Lemma 3.3). As both know all the vertices, they can execute set operations without
communicating. Communication is only needed when executing symbolic one-step operations, since
for these some of the possible edges might affect the outcome.
We next argue that each symbolic one-step operations can be executed with a constant number
of bits of communication. First notice that as both Alice and Bob execute the same algorithm
simultaneously, they both know the input set to an operation and they only need communication
about the possible edges that can change the output. Both can independently identify these possible
edges and they can decide whether such an edge exists by sending one bit each. We next argue that
for each one-step operation we need to consider at most two possible edges. For this we consider the
vertices vi,j in their linear ordering given by i · (k̄ + 1) + j, e.g., v0,0 = v0 and v`−1,k̄ = vk+`−1 .
Post operation: Let S be the input set and let vmin the vertex with the minimum index in S. Then
we have {vmin +1 , . . . vk+`−1 } ⊆ Post(S) and potentially also vmin and vmin −1 can be in Post(S),
but no other vertices. That is, we have {vmin +1 , . . . vk+`−1 } ⊆ Post(S) ⊆ {vmin −1 , . . . vk+`−1 }.
To decide whether vmin is in Post(S), we first check whether vmin +1 ∈ S and if so we check
whether the edge (vmin +1 , vmin ) is present. To decide vmin −1 ∈ Post(S), we check whether the
edge (vmin , vmin −1 ) is present. That is, to compute Post(S) we only access two possible edges.
Pre operation: Let S be the input set and let vmax the vertex with the maximum index in S.
Then we have {v0 , . . . vmax −1 } ⊆ Pre(S) and potentially also vmax and vmax +1 can be in Pre(S),
but no other vertices. That is, we have {v0 , . . . vmax −1 } ⊆ Pre(S) ⊆ {v0 , . . . vmax +1 }. To decide
whether vmax is in Pre(S), we first check whether vmax −1 ∈ S and if so we check whether
the edge (vmax , vmax −1 ) is present. To decide if vmax +1 ∈ Pre(S), we check whether the edge
(vmax +1 , vmax ) is present. That is, we can compute Pre(S) with accessing only two possible edges.
By the above we have that a symbolic algorithm with N one-step operations gives rise to a
communication protocol for Set Disjointness with O(N ) bits of communication.
By Lemma 3.4 we have that any algorithm computing SCCs with o(n) symbolic one-step
operations would contradict Theorem 2.1. Now inspecting the graph of Reduction 3.1, we observe
that its diameter is equal to k̄, which leads to the following lower bounds. For ` = k/2 the graph has
diameter 2 and thus the Ω(n) holds even for graphs of constant diameter. On the other side, for ` = 1
disjoint sets Sx and Sy correspond to strongly connected graphs and thus the Ω(n) lower bounds
also holds for graphs with a√bounded number of SCCs, i.e., there are no O(|SCCs(G)|) symbolic
algorithms. Finally for ` = k we obtain a Ω(|SCCs(G)| · D) lower bound.

6

v0

v1

v2

v3

v4

Figure 2: Reduction 3.6 for k = 4, ` = 2, Sx = {2, 3}, Sy = {0, 1, 3}
Remark 3.5. By the above no algorithm can compute SCCs with f (D)·no(1) or f (|SCCs(G)|)·no(1)
symbolic one-step operations for any function f . In contrast, if we consider both parameters
simultaneously, there is an O(|SCCs(G)| · D) symbolic algorithm.
The above lower bounds for computing SCCs match the O(min(n, D · |SCCs(G)|)) bound by
the algorithm of Gentilini et al. [GPP08]. One way to further improve the algorithm is to not consider
the diameter of the whole graph but the P
diameter DC of each single SCC C. In that direction the
previous reduction
already
gives
us
an
Ω(
and we will next improve
C∈SCCs(G) (DC )) lower bound
P
P
it to an Ω( C∈SCCs(G) (DC + 1)) lower bound (i.e., it is Ω(n) even if C∈SCCs(G) (DC ) ∈ O(1)).
These two bounds differ if the graph has a large number of trivial SCCs. Thus we next give a
reduction that constructs a graph that has only trivial SCCs if Sx and Sy are disjoint.
Reduction 3.6. Given an instance (x, y) of Set Disjointness, we construct a directed graph G =
(V, E) with n = k + 1 vertices and O(n2 ) edges as follows. (1) The vertices are given by V =
{v0 , v1 , . . . , vk }. (2) There is an edge from vi to vj for i < j. (3) For 0 ≤ j ≤ k − 1 there is an edge
from vj+1 to vj iff xj = 1 and yj = 1.
error or deterministic) symbolic algorithm that computes
Theorem 3.7. Any (probabilistic bounded
P
the SCCs needs Ω(|SCCs(G)| + C∈SCCs(G) DC ) symbolic one-step operations.

3.2

Lower Bounds for Liveness, Reachability, and Safety Objectives

In this section we extend our lower bounds for SCC computation to Liveness, Reachability, and
Safety Objectives on graphs.
Lower Bounds for Reachability. The lower bounds for Reachability are an immediate consequence
from our lower bounds for SCC computation in Theorem 3.2. When setting ` = 1 in Reduction 3.1
then the vertex v0,0 is reachable from all vertices iff the graph is strongly connected iff the sets Sx
and Sy are disjoint.
Theorem 3.8. Any (probabilistic bounded error or deterministic) symbolic algorithm that solves
Reachability in graphs with diameter D requires Ω(D) symbolic one-step operations.
Lower Bounds for Liveness. To show an Ω(n) lower bound for Liveness objectives which holds even
for graphs of bounded diameter, we introduce another reduction. This reduction is again from the Set
Disjointness Problem and also constructs a graph such that Pre and Post operations can be executed
with a constant number of bits of communication between Alice and Bob.
Reduction 3.9. Given an instance (x, y) of Set Disjointness, we construct a directed graph G =
(V, E) with n = k + 1 vertices and O(n2 ) edges as follows. (1) The vertices are given by V =
{v0 , v1 , . . . , vk }. (2) There is an edge from vi to vj for i < j and there is a loop edge (vk , vk ). (3)
For 0 ≤ j ≤ k − 1 there is a loop edge (vj , vj ) iff xj = 1 and yj = 1.

7

v0

v1

v2

v3

v4

Figure 3: Reduction 3.9 for k = 4, ` = 2, Sx = {2, 3}, Sy = {0, 1, 3}
Notice that the graph in Reduction 3.9 has diameter D = 1 and thus allows to show the lower
bounds stated in Theorem 3.10 when considering T = {v0 , v1 , . . . , vk−1 }, with the exception of (2)
which is by Reduction 3.1 and T = {v0 }.
Theorem 3.10. For any (probabilistic bounded error or deterministic) symbolic algorithm that solves
Büchi(T ) the following lower bounds on the required number of symbolic one-step operations hold:
(1) Ω(n) even for instances with constant D; (2) Ω(D) even for instances with P
|T | = 1; (3) Ω(|T |)
even for instances with constant D; (4) Ω(|T | + D); and (5) Ω(|SCCs(G)| + C∈SCCs(G) DC ).
Lower Bounds for co-Liveness and Safety. The following lower bounds are by Reduction 3.9 (and
variations of it) and the set of safe vertices T = {v0 , v1 , . . . , vk−1 }.
Theorem 3.11. For any (probabilistic bounded error or deterministic) symbolic algorithm that solves
Safe(T ) or coBüchi(T ) the following lower bounds on the required number of symbolic one-step
operations hold: (1)PΩ(n) even for constant diameter graphs; (2) Ω(|T |) even for constant diameter
graphs; and (3) ω( C∈SCCs(G) (DC + 1)) even for constant diameter graphs.
Notice that the parameters diameter, number of SCCs, or diameters of SCCs do not help in
the case of Safety. This is because every graph can be reduced to a strongly connected graph with
diameter 2 without changing the winning set as follows: Add a new vertex v that has an edge to and
an edge from all original vertices but do not add v to the safe vertices T .
We complete this section with a Ω(D) lower bound for coBüchi(T ) which is by a variant of
Reduction 3.1.
Proposition 3.12. Any (probabilistic bounded error or deterministic) symbolic algorithm that solves
coBüchi(T ) on graphs with diameter D needs Ω(D) symbolic one-step operations.

3.3

Lower Bound for Approximate Diameter

The Approximate Diameter Problem. Let G = (V, E) be a directed graph with n vertices V and
m edges E. Let d(u, v) denote the shortest distance from u ∈ V to v ∈ V in G, i.e., the smallest
number of edges of any path from u to v in G. Recall that we define the diameter of G as the
maximum of d(u, v) over all pairs u, v for which u can reach v in G. 1 We consider the problem of
e
approximating the diameter D of a graph by a factor c, where the goal is to compute an estimate D
e
such that D/c ≤ D ≤ D. As undirected graphs are special cases of directed graphs, the lower bound
is presented for undirected graphs and the upper bound for directed graphs (see Section 4), i.e., both
hold for undirected and directed graphs.
1

Usually the diameter is defined over all pairs of vertices, not just the reachable ones, and is therefore ∞ if G is not
strongly connected. Our definition is more general since determining whether the graph is strongly connected takes only
O(D) symbolic steps and additionally our definition is more natural in the symbolic setting as it provides an upper bound
on the number of one-step operations needed until a fixed point is reached, which is an essential primitive in symbolic
graph algorithms.

8

u

t

a0

b0

c0

a1

b1

c1

a2

b2

c2

Figure 4: Reduction 3.13 for k = 9, s = 3, Sx = {2, 4, 8}, Sy = {1, 3, 5}.
Result. We show a lower bound of Ω(n) on the number of symbolic steps needed to distinguish
between a diameter of 2 and a diameter of 3, even in an undirected connected graph. The basic
symbolic algorithm for computing the diameter exactly takes O(n · D) many symbolic steps. Thus
our lower bound is tight for constant-diameter graphs.
Outline Lower Bound. We show how to encode an instance of the Set
√ Disjointness Problem with
a universe of size k in an (undirected, connected) graph with Θ( k) vertices and Θ(k) edges
such
√ that 1) in a communication protocol any symbolic one-step operation can be simulated with
Θ( k) bits and 2) the graph has diameter 2 if the two sets are disjoint and diameter 3 otherwise.
Thus the communication
complexity lower bound of Ω(k) for Set Disjointness implies a lower
√
bound of Ω( k) = Ω(n) for the number of symbolic one-step operations to compute a (3/2 − ε)approximation of the diameter of a graph with n vertices.
√
Reduction 3.13. Let (x, y) be an instance of the Set Disjointness problem of size k and let s = k.
We construct an undirected graph G = (V, E) with n = 3s + 2 vertices and O(k) edges as follows.
(1) There are three sets A, B, C with s vertices each and two auxiliary vertices u and t. We denote
the i-th vertex of each of A, B, C with a lowercase letter indicating the set and subscript i. (2) There
is an edge between u and t and between u and each vertex of A and B and between t and each vertex
of C. (3) For each 0 ≤ i < s there is an edge between ai ∈ A and bi ∈ B. (4) For 0 ≤ ` < k let
i, j < s be such that ` = i · s + j. There is an edge between ai ∈ A and cj ∈ C iff x` = 0 and there
is an edge between bi ∈ B and cj ∈ C iff y` = 0.
We first show that this graph has diameter 2 if Sx and Sy are disjoint and diameter 3 otherwise
and then show how Alice can obtain a communication protocol for the Set Disjointness problem from
any symbolic algorithm that can distinguish these two cases.
Lemma 3.14. Let G = (V, E) be the graph given by Reduction 3.13 and let D denote its diameter.
If Sx ∩ Sy = ∅, then D = 2, otherwise D = 3.
In the graph G = (V, E) given by Reduction 3.13 Alice knows all the vertices of the graph
and all the edges except those who are constructed based on y, i.e., Alice does not know the edges
between B and C. To take into account the edges between B and C, Alice has to communicate
with Bob. To show a lower bound on the number of symbolic steps, we show next an upper bound
on the number of bits of communication between Alice and Bob needed to simulate a symbolic
one-step operation on G. With the simulation of the one-step operations, the symbolic algorithm can
be used as a communication protocol for distinguishing whether G has diameter 2 or 3 and thus by
Lemma 3.14 to solve the Set Disjointness problem. Whenever the symbolic algorithm performs a Pre

9

or Post operation (which are equivalent on undirected graphs) for a set S that contains vertices of B
or C, then Alice can simulate this one-step operation by specifying the vertices of B and C that are in
S with a bit vector of size 2s, where Bob answers with a bit vector, again of size 2s, that indicates all
vertices that are adjacent to (B ∪ C) ∩ S. Thus the communication protocol can simulate a symbolic
algorithm that performs T one-step operations with at most 4sT bits of communication. Hence
we have by Theorem 2.1 that 4sT ≥ Ω(k) = Ω(s2 ) and thus T ≥ Ω(s) = Ω(n). Together with
Lemma 3.14, this proves the following theorem. Note that any (3/2 − ε)-approximation algorithm
for the diameter of a graph can distinguish between diameter 2 and 3.
Theorem 3.15. Any (probabilistic bounded error or deterministic) symbolic algorithm that computes
a (3/2 − ε)-approximation of the diameter of an undirected connected graph with n vertices needs
Ω(n) symbolic one-step operations.

4

Upper Bounds

In this work we present the following upper bounds.

4.1

Upper Bounds for Computing Strongly Connected Components

We revisit the symbolic algorithm of Gentilini et al.P
[GPP08] that computes the SCCs and present
a refined analysis to show that it only requires O( C∈SCCs(G) (DC + 1)) symbolic operations,
improving the previously known O(min(n, D · |SCCs(G)|)) bound and matching the lower bound
of Theorem 3.7 (details in Section 6.4).
Theorem 4.1. ThePalgorithm of Gentilini et al. [GPP08] computes the SCCs of a graph G with
O(|SCCs(G)| + C∈SCCs(G) DC ) symbolic operations.

4.2

Upper Bounds for Liveness, Reachability, and Safety Objectives

The upper bounds for Reachability, Safety, Liveness, and co-Liveness, are summarized in the
following proposition, which is straightforward to obtain as discussed below.
Proposition 4.2. Let SCC be the number of symbolic steps required to compute the SCCs of
the graph and let T be the set of target/safe vertices. Then Reach(T ) can be solved with O(D)
symbolic operations; Büchi(T ) can be solved with O(min(SCC + D, |T | · D)) symbolic operations;
coBüchi(T ) can be solved with O(|T | + D) symbolic operations; and Safe(T ) can be solved with
O(|T |) symbolic operations.
Algorithm for Reachability. Given a target set T , we can easily compute the vertices that can reach T
by iteratively applying Pre operations until a fixed-point is reached. By the definition of diameter,
this requires only O(D) symbolic operations.
Algorithms for Liveness. A simple algorithm for Liveness first starts an algorithm for computing
SCCs and whenever an SCC is reported it tests whether the SCC contains one of the target vertices
and if so adds all vertices of the SCC to the winning set. Finally, after all SCCs have been processed,
the algorithm computes all vertices that can reach the current winning set and adds them to the
winning set. That is, in total the algorithm only needs O(SCC + D) many symbolic operations
where SCC is the number of symbolic operations required by the SCC algorithm. An alternative
algorithm for Liveness with O(|T | · D) symbolic operations is as follows. For each v ∈ T check

10

with O(D) symbolic one-step operations whether the vertex can reach itself and if not remove the
vertex from T . Then do a standard reachability with the updated set T as target, again with O(D)
symbolic one-step operations.
Algorithm for co-Liveness. Given a set T of safe vertices, an algorithm for co-Liveness first restricts
the graph to the vertices of T ; in the symbolic model this can be done by intersecting the outcome of
each Pre and Post operation with T . One then uses an SCC algorithm and whenever a non-trivial
SCC is reported, all its vertices are added to the winning set. Finally, after all SCCs have been
processed, all vertices that can reach the current winning set in the original graph are added to the
winning set. That is, in total the algorithm only needs O(|T | + D) many symbolic operations, where
|T | comes from the linear number of symbolic operations required by the SCC algorithm for the
modified graph.
Algorithm for Safety. Given a set T of safe vertices, an algorithm for safety first restricts the graph
to the vertices of T . One then uses an SCC algorithm and whenever a non-trivial SCCs is reported,
all its vertices are added to the winning set. Finally, after all SCCs have been processed, all vertices
that can reach, within T , the current winning set are added to the winning set. That is, in total the
algorithm only needs O(|T |) symbolic operations as both the SCC algorithm for the modified graph
and reachability in the modified graph are in O(T ). Also notice that reachability is not bounded by
O(D) as restricting the graph to vertices of T can change the diameter.
Notice that none of the above algorithms stores all the SCCs, but processes one SCC at a time.
That is, the algorithms themselves only need a constant number of sets plus the sets stored in the
algorithm for computing SCCs (which can be done with O(log n) many sets).

4.3

Upper Bounds for Approximate Diameter

We present
a (1 + ε)-approximation algorithm for the diameter (for any constant ε > 0) that takes
√
e
e
O(n
D) symbolic operations (the O-notation
hides logarithmic factors).
Theorem 4.3. A (1 + )-approximation
of the diameter of a directed graph for any constant  > 0
√
e
D) symbolic operations, using O(1) many sets.
can be obtained with O(n
Technical Overview (1 + ε)-Approximation Algorithm. The symbolic algorithm is based on the
3/2-approximation algorithm by Aingworth et al. [Ain+ 99] for explicit graphs, we give a high-level
overview of the differences here. An expensive step in the algorithm of [Ain+ 99] is the computation
of s-partial BFS trees that contain s vertices closest to a root vertex v and can be determined with
O(s2 ) explicit operations (this part was later replaced and improved upon by [RW13, Che+ 14]). In
the symbolic model computing s-partial BFS trees would be less efficient, however, we can compute
all vertices with distance at most x from v with only O(x) many symbolic operations. The limitation
of the approximation ratio c to 3/2 in the algorithm of [Ain+ 99] comes from having to deal with
vertices for which less than s vertices are within distance at most D/(2c). In the symbolic model we
do not have to consider this case since with a budget of O(x) operations we can always reach at least
x vertices (assuming for now that the graph is strongly connected and x < D). Thus the algorithm
simplifies to the second part of their algorithm, whose core part is to find a vertex within distance at
most x for each vertex of the graph by using a greedy approximation algorithm for dominating set.
However, in the symbolic model storing a linear number of sets is too costly, hence we inherently use
that we can recompute vertices at distance at most x efficiently when needed. Details are presented
in Section 6.5.

11

5
5.1

Discussion
SCCs and Verification Objectives

First, our results show that the symbolic SCC algorithm by Gentilini et al. [GPP08]
is essentially optiP
mal. That is, we have the three upper bounds of O(n), O(|SCCs(G)·D|) and O( C∈SCCs(G) (DC +
lower bounds of Ω(n) (Theorem 3.2), Ω(|SCCs(G)| · D) (Theorem 3.2), and
1)) and matching
P
Ω(|SCC| + C∈SCCs(G) DC ) (Theorem 3.7).
Table 3: Results
number of symbolic operations
SCC

Θ(n)

Θ(|SCCs(G)| · D)

P

Θ(

C∈SCCs(G) (DC

+ 1))

Our results for the different kinds of verification objectives are summarized in Table 4. We
have an interesting separation between the reachability objective and the other objectives in terms
of the diameter D. While reachability can be solved with O(D) symbolic operations, all the other
objectives require Ω(n) symbolic one-step operation on graphs of constant diameter.
When considering the diameters DC of the SCCs
we get another separation. There we have that
P
Liveness and Reachability can be solved with O( C∈SCCs(G) (DC + 1)) many symbolic operations,
while Safety and co-Liveness requires Ω(n) symbolic one-step operations on strongly connected
graphs with constant diameter. This reflects the fact that in the standard algorithm for Safety and
co-Liveness the SCC computation is performed on a modified graph.

5.2

Approximate Diameter

e √n)
For explicitly represented graphs a 3/2-approximation of the diameter can be computed in O(m
time [RW13, Che+ 14], while under the strong exponential time hypothesis no O(n2−o(1) ) time
algorithm exists to distinguish graphs of diameter 2 and 3 (i.e., no (3/2 − ε)-approximation can be
e
obtained) [RW13]. The fastest exact algorithms take O(mn)
time. While for explicitly represented
graphs small, constant diameters are a hard case, the current results suggest that in the symbolic
model the diameter of graphs with constant diameter can be determined more efficiently than for large
diameters, as both the upper bound for exact and approximate computation of the diameter depend
on the diameter of the graph and are linear when the diameter is constant. While the threshold of an
approximation ratio of 3/2 appears in our (linear) lower bound, the current symbolic upper bounds do
not show this behavior. Several interesting open questions remain: Is there a o(n) c-approximation
algorithm when c ∈ [3/2, 2)? Is there a linear (1 + ε)-approximation algorithm for graphs with
super-constant diameter? Or are there better lower bounds?

6
6.1

Detailed Proofs
Proofs of Section 3.1

Proof of Lemma 3.3. We have to show that f (x, y) = 1 iff the graph constructed in Reduction 3.1
has exactly ` SCCs.
First notice that there are no edges from a set Vj to a set Vi if i < j and thus there are at least `
SCCs, independently of the actual values of x and y.

12

Table 4: Results
Objective
n
Reach(T)
Safe(T)
Büchi(T)
coBüchi(T)

Θ(n)
Θ(n)
Θ(n)
Θ(n)

number of symbolic operations in terms of
D & |T |
DC
Θ(D)
Θ(|T |)
O(|T | · D) / Ω(|T | + D)
Θ(|T | + D)

Θ(D)
P
ω( C∈SCCs(G) (DC + 1))
P
Θ( C∈SCCs(G) (DC + 1))
P

ω(

C∈SCCs(G) (DC

+ 1))

⇒: If f (x, y) = 1 then all possible edges exists and it is easy to verify that the SCCs of the graphs
are exactly the sets Vi for 0 ≤ i < `.
⇐: If f (x, y) = 0 then there are 0 ≤ j ≤ k̄, 0 ≤ i < ` such that there is no edge from vi,j+1 to vi,j .
Now the set Vi splits up in at least two SCCs and thus there are at least ` + 1 SCCs.
Proof of Theorem 3.7. We have to show that any (probabilistic bounded
error or deterministic)
P
symbolic algorithm that computes the SCCs needs Ω(|SCCs(G)| + C∈SCCs(G) DC ) symbolic
one-step operations.
P
First consider Reduction 3.1 and notice P
that for the constructed graph C∈SCCs(G) DC ∈ Θ(n).
Then by Theorem 3.2 we already have a Ω( C∈SCCs(G) (DC )) bound. Now consider Reduction 3.6
and notice that the constructed graph has n SCCS iff x and y are disjoint. Now we can use the same
argument as in the proof of Theorem 3.2 that each symbolic one-step operations
just needs constant
P
communication. The instances where x and y are disjoint have n SCCs and C∈SCCs(G) DC = 0.
Hence an algorithm with o(|SCCs(G)|) symbolic one-step operations would imply a communication
protocol with o(k) communication, a contradiction
to Theorem 2.1. By combining the two lower
P
bounds we get the desired Ω(|SCCs(G)| + C∈SCCs(G) DC ) bound.

6.2

Proofs of Section 3.2

Proof of Theorem 3.8. We have to show that any (probabilistic bounded error or deterministic)
symbolic algorithm that solves Reachability in graphs with diameter D requires Ω(D) symbolic
one-step operations.
Consider the graph from Reduction 3.1 with parameter ` = 1. We have that v0 is reachable from
all vertices iff the graph is strongly connected. From the proof of Theorem 3.2 we have that testing
whether the graph is strongly connected requires Ω(k) symbolic one-step operations. Now notice that
(a) the graph is strongly connected iff vk can reach v0 and that (b) if the graph is strongly connected
then D = k.
Proof of Theorem 3.10. For (1) & (3) consider the graph constructed in Reduction 3.9 and the target
set T = {v0 , v1 , . . . , vk−1 }. We have a valid reduction from the Set Disjointness problem as the vertex
v0 is winning for Büchi(T ) iff there is a loop for one of the vertices in T iff Sx ∩ Sy 6= ∅. By the same
argument as in the proof of Theorem 3.2 we have that each symbolic one-step operations just needs
constant communication. Hence an algorithm with o(n), o(|T |) or o(|SCCs(G)|) symbolic one-step
operations would imply a communication protocol with o(k) communication, a contradiction.
For (2) consider the graph constructed in Reduction 3.1 with ` = 1 and the target set T = {v0 }.
It is easy to verify that the vertex vk is winning if it can reach
T . Thus the Ω(D) lower bound for
P
reachability also applies here. Notice that this also gives a Ω( C∈SCCs(G) DC ) lower bound.

13

The Ω(|T |+D) lower bound in (4) is a direct consequence of the Ω(D) lower bound for instances
with constant size target sets T , and the Ω(|T |) lower bound for instances with constant
diameter D.
P
Finally, (5) is by the Ω(|SCCs(G)|) bound from Reduction 3.9 and the Ω( C∈SCCs(G) DC )
bound by Reduction 3.1 with ` = 1.
Proof of Theorem 3.11. 1) & 2) Consider the graph constructed in Reduction 3.9 and the set of safe
vertices T = {v0 , v1 , . . . , vk−1 }. We have a valid reduction from the Set Disjointness problem as the
vertex v0 is winning for Safe(T ) iff there is a loop for one of the vertices in T iff Sx ∩ Sy 6= ∅. By the
same argument as in the proof of Theorem 3.2 we have that each symbolic one-step operations just
needs constant communication. Thus an algorithm with o(n) or o(|T |) symbolic one-step operations
would imply a communication protocol with o(k) communication, a contradiction.
3) Consider the graph constructed in Reduction 3.9 but replace the edge (vk , vk ) by the edge
(vk , v0 ). When considering the set of safe vertices T = {v0 , v1 , . . . , vk−1 } the same arguments as
above apply and thus we get a Ω(n)P
lower bound. However, the graph is strongly connected and has
diameter 2 and thus |SCCs(G)| + C∈SCCs(G) DC = O(1).
Proof of Proposition 3.12. Consider the graph constructed in Reduction 3.1 with ` = 1, add an
additional loop edge (v0 , v0 ), and consider the set T = {v0 } of safe vertices, i.e., v0 is the only safe
vertex. It is easy to verify that the vertex vk is winning in coBüchi(T ) if it can reach T . Thus the
Ω(D) lower bound for reachability also applies here.

6.3

Proofs of Section 3.3

Proof of Lemma 3.14. Let G = (V, E) be the graph given by Reduction 3.13 and let D denote its
diameter. We have to show that if Sx ∩ Sy = ∅, then D = 2, otherwise D = 3.
First note that through the edges adjacent to the auxiliary vertices the diameter of G is at most 3.
Furthermore we have for all 0 ≤ i, j < s that d(ai , bj ) ≤ 2, d(u, cj ) = 2, and d(t, cj ) = 1, for
all i 6= j additionally d(ai , aj ) = d(bi , bj ) = d(ci , cj ) = 2, and for all v ∈ A ∪ B it holds that
d(u, v) = 1 and d(t, v) = 2. Thus whether D is 2 or 3 depends only on the maximum over all
0 ≤ i, j < s of d(ai , cj ) and d(bi , cj ).
If Sx ∩ Sy = ∅, then for each pair of indices 0 ≤ i, j < s at least one of the edges (ai , cj ) and
(bi , cj ) exists. Since (ai , bi ) ∈ E, we have for all 0 ≤ j < s and all v ∈ A ∪ B that d(v, cj ) ≤ 2 and
hence D = 2.
If Sx ∩ Sy 6= ∅, let ` ∈ Sx ∩ Sy and let 0 ≤ i, j < s be such that ` = i · s + j. Then neither the
edge (ai , cj ) nor the edge (bi , cj ) exists. Thus the vertex ai , and analogously the vertex bi , has edges
to the following vertices only: the auxiliary vertex u, the vertex bi , and vertices cj 0 ∈ C with j 0 6= j.
The vertex cj has edges only to the auxiliary vertex t and to vertices ai0 ∈ A and bi0 ∈ B with i0 6= i.
Hence none of the vertices adjacent to ai , and respectively for bi , is adjacent to cj and thus we have
D = d(ai , cj ) = d(bi , cj ) = 3.

6.4

An Improved Upper Bound for Strongly Connected Components

Result. Gentilini et al. [GPP08] provide a symbolic algorithm for computing the strongly connected
components (SCCs) and show a bound of O(min(n, D · |SCCs(G)|)) on the number of its symbolic
operations for a directed graph with n vertices, diameter D, and |SCCs(G)| many SCCs. Let DC
be the diameter of an P
SCC C. We give a tighter analysis of the algorithm of [GPP08] that shows
an upper bound of O( C∈SCCs(G)
(DC + 1)) symbolic operations that matches
our lower bound
P
P
(Theorem 3.7). We have both C∈SCCs(G) (DC +1) ≤ (D+1)·|SCCs(G)| and C∈SCCs(G) (DC +

14

1) ≤ n + |SCCs(G)| ≤ 2n and thus our upper bound is always at most the previous one. We
additionally observe that the algorithm can be implemented with O(log n) many sets (when the
SCCs are output immediately and not stored). We first explain the intuition behind the algorithm of
[GPP08] and then present the improved analysis of its number of symbolic steps.
Symbolic Breadth-First Search. While explicit algorithms for SCCs are based on depth-first search
(DFS), DFS is impractical in the symbolic model. However, breadth-first search (BFS) from a set
U ⊆ V can be performed efficiently symbolically, namely proportional to its depth, as defined below.
Definition 6.1 (Symbolic BFS). A forward search from a set of vertices U = U0 is given by a
sequence of Post operations such that Ui = Ui−1 ∪ Post(Ui−1 ) for i > 0 until we have Ui = Ui−1 .
We call Ui \ Ui−1 the i-th level of the forward search and the index of the last non-empty level the
→
−
→
depth B (U ) of the forward search. Let F W (U ) = U−
be the forward set, which is equal to
B (U )
←
−
the vertices reachable from U . Analogously we define the backward search of depth B (U ) and the
backward set BW (U ) for Pre operations. We denote a singleton set U = {u} by u.
There is a simple algorithm for computing the SCCs symbolically with BFS that takes O(D ·
|SCCs(G)|) many symbolic steps: Start with an arbitrary vertex v. Compute the SCC containing
v by taking the intersection of F W (v) and BW (v), remove the obtained SCC from the graph, and
repeat.
Skeleton-based Ordering. The importance of DFS for SCCs lies in the order in which the SCCs are
computed. Starting from a vertex v that lies in an SCC without outgoing edges (i.e. a sink in the
DAG of SCCs of the graph), the forward search does not leave the SCC and for computing SCCs the
backward search can be restricted to the vertices of F W (v), i.e., the SCC of v can be determined
with proportional to the diameter of the SCC many symbolic steps. The DFS-based SCC algorithm of
[Tar72] finds such an SCC first. The algorithm of [GPP08] is based on an ordering obtained via BFS
that achieves a DFS-like ordering suitable for computing SCCs symbolically. Our tighter analysis
essentially shows that their approach achieves the best ordering we can hope for. The ordering is
given by so-called skeletons.
Definition 6.2. A pair (S, v) with v ∈ V and S ⊆ V is a skeleton of F W (u) for u ∈ V if v has
maximum distance from u and the vertices of S form a shortest path from u to v.
Let SCC(v) denote the SCC containing v ∈ V . The SCCs of the vertices of S will be computed in
the following order: First SCC(u) is computed by performing a backward search from u within
F W (u). The remaining SCCs of of the vertices of S are then computed in the reverse order of the
path induced by S, starting with SCC(v). We now describe the overall algorithm, where in addition
to SCC(S, v) the SCCs of V \ F W (u) are computed (potentially using a different, previously
computed skeleton).
The Algorithm. The pseudo-code of the algorithm is given in Algorithm SCC-Find, the pseudo-code
for the sub-procedure for computing a forward set including a skeleton in Algorithm Skel-Forward.
Processing a graph G, the algorithm proceeds as follows: it starts from some vertex v and computes
the set of reachable vertices, i.e, the forward set F W (v), including a skeleton that includes exactly
one vertex of each level of the forward search and forms a shortest path in G. It then starts a backward
search starting from v in the subgraph induced by F W (v). Clearly the SCC of v is given by the
vertices that are reached by the backward search. The algorithm returns this SCC as an SCC of G and
recurses on (a) the subgraph GV \F W (v) induced by the vertices of V \ F W (v) and (b) the subgraph

15

Algorithm SCC-Find: Symbolic SCC Algorithm
Input : Graph G = (V, E), Skeleton (S, v)
1
2
3
4

5

if V = ∅ then
return ∅;
if S = ∅ then
v ← P ick(V ) ;
vertex

// If there is no skeleton, pick arbitrary

(F W, S 0 , v 0 ) ← Skel_Forward(V, E, v) ;
skeleton

8

/* Compute the SCC containing v
SCC ← {v};
while (Pre(SCC) ∩ F W ) \ SCC 6= ∅ do
SCC ← SCC ∪ (Pre(SCC) ∩ F W )

9

output SCC as an SCC;

6
7

// Forward search incl.

11

/* Recursive calls
SCC-Find(GV \F W , (S \ SCC, (pre(SCC ∩ S) \ SCC) ∩ S));
SCC-Find(GF W \SCC , (S 0 \ SCC, v 0 ));

12

return SCCs;

10

*/

*/

GF W (v)\SCC(v) induced by the vertices of F W (v) \ SCC(v). For the recursion on (a) we update a
potentially already existing skeleton by removing all vertices that are in the current SCC (initially
we have an empty skeleton) while for the recursion on (b) we use the skeleton computed by the
forward search (but also remove vertices of the current SCC). The skeleton is then used to select the
starting vertex in the consecutive steps of the algorithm: when the algorithm is called with skeleton
(S, v), then the forward search is started from v; when the skeleton was computed in a forward search
from a vertex u, then this corresponds to the vertex of the skeleton that is furthest away from u and
contained in this recursive call.
A Refined Analysis. The correctness of the algorithm is by [GPP08]. Notice that the algorithm would
be correct even without the usage of skeletons but the skeletons are necessary to make it efficient, i.e.,
to avoid unnecessarily long forward searches. We show the following theorem.
Theorem 6.3 (RestatementP
of Theorem 4.1). With input (G, ∅) Algorithm SCC-Find computes the
SCCs of G and requires O( C∈SCCs(G) (DC + 1)) symbolic operations.
The analysis of [GPP08] of the number of symbolic steps of Algorithm SCC-Find uses that (1) each
vertex is added to at most two skeletons, (2) the steps of the forward searches can be charged to the
vertices in the skeletons, and (3) backward searches are only performed to immediately identify an
SCC and thus can be charged to the vertices of the SCC; hence both the steps of the forward and of
the backward searches can be bounded with O(n). For the backward searches it can easily be seen
that the number of Pre operations to identify the SCC C is also bounded by DC + 1. For the forward
searches we show that each part of the skeleton (that in turn is charged for the forward search) can be
charged to DC + 1 for some SCC C; this in particular exploits that skeletons are shortest paths (in
the graph in which they are computed).

16

Algorithm Skel-Forward: Skeleton Forward Search Algorithm
Input : Graph G = (V, E), Node v
Output : F W Set of vertices reachable from v;
(S 0 , v 0 ) Skeleton for F W
1

F W ← ∅; i ← 0; LEVEL[0] ← {v};
/* Forward Search
while LEVEL[i] 6= ∅ do
F W ← F W ∪ LEVEL[i];
i ← i + 1;
LEVEL[i] ← Post(LEVEL[i − 1]) \ F W ;

*/

*/

11

/* Compute Skeleton
i ← i − 1;
v 0 ← P ick(LEVEL[i]);
S 0 ← {v 0 };
while i ≥ 1 do
i ← i − 1;
S 0 ← S 0 ∪ {P ick(Pre(S 0 ) ∩ LEVEL[i])};

12

return (F W, S 0 , v 0 );

2
3
4
5

6
7
8
9
10

Lemma 6.4 ([GPP08]). For each recursive call of SCC-Find with input G, (S, v) we have that S is
a set of vertices that induces a shortest path in the graph G and v is the last vertex of this path.
We first recall the result from [GPP08] that shows that the number of symbolic operations in an
execution of Skel-Forward is proportional to the size of the computed skeleton.
Lemma 6.5 ([GPP08]). Skel-Forward only requires O(S 0 ) symbolic operations, i.e., is linear in the
output, and can be implemented using only constantly many sets.
Proof. For each level of the forward search we need one Post operation in the first while loop and
one Pre operation in the second while loop, and the number of set operations is in the order of
one-step operations. As for each level we add one vertex to S 0 , the result follows. Moreover, there is
no need to explicitly store all the levels as they can be easily recomputed from the next level when
needed, increasing the number of symbolic operations only by a constant factor.
Remark 6.6. Given Lemma 6.5 we can implement SCC-Find using O(log n) many sets at a time by
recursing on the smaller of the two sub-graphs GV \F W and GF W \SCC first.
We split the cost of O(S 0 ) symbolic operations for Skel-Forward into two parts: the part S 0 ∩
SCC(v) where SCC(v) is the SCC identified in this level of recursion and the part S 0 \ SCC(v)
that is passed to one of the recursive calls. The following lemma shows that the first part and the
subsequent backward search can be charged to DSCC(v) + 1, using that S 0 is a shortest path in
F W (v).
Lemma 6.7. Without accounting for the recursive calls, each call of SCC-Find takes O(DSCC(v) +
1 + |S 0 \ SCC(v)|) symbolic operations, where S 0 is the new skeleton computed by Skel-Forward.

17

Proof. By Lemma 6.5, the call to Skel-Forward takes O(|S 0 |) symbolic operations. In the i-th
iteration of the while loop (Line 7) we add those vertices of SCC(v) that can reach v in i steps.
That is, the loop terminates after DSCC(v) iterations and thus only requires O(DSCC(v) + 1) many
symbolic operations. All the other steps just need a constant number of symbolic operations. That
is, we have an upper bound of O(DSCC(v) + 1 + |S 0 |). Now as S 0 induces a path starting at
v in F W (v), we have that whenever a vertex u 6= v of S 0 can reach v, then also all vertices
on the path from v to u can reach v and are therefore in the same SCC as v. Since the path is
a shortest path, also every sub-path is a shortest path and thus we have that |S 0 ∩ SCC(v)| ≤
DSCC(v) + 1, i.e., |S 0 | ∈ O(DSCC(v) + 1 + |S 0 \ SCC(v)|). Hence we obtain the desired bound of
O(DSCC(v) + 1 + |S 0 \ SCC(v)|) for the number of symbolic operations.
Note that at each level of recursion we only charge the diameter of the SCC that is output and
the vertices of the newly computed skeleton. Thus we do not charge vertices of a skeleton again
until they are contained in an SCC that is identified. The following lemma shows that in this case we
can charge the symbolic steps that were charged to the vertices of the skeleton to DC + 1, where C
is the SCC the part of the skeleton belongs to. Notice that S \ SCC(v) is the skeleton for the first
recursive call and S 0 \ SCC(v) is the skeleton for the second recursive call, i.e., all vertices of a
skeleton
are finally assigned to an SCC. That is, we can bound the total number of symbolic steps by
P
O( C∈SCCs(G) (DC + 1)).
Lemma 6.8. Whenever SCC-Find is called for a graph H and a skeleton (S, v), then |S∩SCC(v)| ≤
DSCC(v) + 1 .
Proof. By Lemma 6.4 the set S induces a shortest path in H that ends at v. Thus if v can reach a
vertex u 6= v of S, then it can also reach all vertices of S that are on the path from u to v and all
vertices on this sub-path are in the same SCC as v. Furthermore, the sub-path is a shortest path as
well and thus the vertices |S ∩ SCC(v)| form a shortest path in SCC(v) and hence the diameter
DSCC(v) of SCC(v) is at least |S ∩ SCC(v)| − 1.

√
f
6.5 (1 + ε)-Approximation of Diameter with O(n
D) Symbolic Operations
→
−
Notation. Given a vertex u ∈ V , let N x (u) denote the vertices with distance at most x from u and let
←
−
→
−
N y (u) be the set of vertices with distance at most y to u. We have that {u} ∪ Post({u}) = N 1 (u)
→
−
→
−
→
−
and N x (u) ∪ Post( N x (u)) = N x+1 (u). The maximum distance from the vertex u to any other
→
−
→
−
→
−
vertex v ∈ V is given by the smallest x for which N x (u) ∪ Post( N x (u)) = N x (u). Note
that x is at most D and that computing x in this way corresponds to performing a breadth-firstsearch (BFS) from x on explicitly represented graphs; thus following [Ain+ 99], we denote the
→
−
→
−
→
−
→
−
smallest x for which N x (u) ∪ Post( N x (u)) = N x (u) with B (u) and the smallest y for which
←
−
←
−
←
−
←
−
N y (u) ∪ Pre( N y (u)) = N y (u) with B (u). The set of vertices reachable from u ∈ V is given by
→
−
→
N−
(u).
B (u)
The Basic Exact Algorithm. The maximum d(u, v) over all pairs u, v ∈ V for which u can reach v
→
−
→
−
can be computed by taking the maximum of B (u) over all u ∈ V . Computing B (u) for all u ∈ V
takes O(n · D) many Post operations. To obtain only the value of D, only a constant number of sets
have to be stored. Note that this basic algorithm only uses a linear number of symbolic operations for
graphs with constant diameter. See Section 3.3 for a matching lower bound for this case.

18

A Simple 2-Approximation Algorithm. If the graph G is strongly connected, then a 2-approximation
→
−
←
−
of D is given by ( B (u) + B (u))/2 for any vertex u ∈ V . This follows from the triangle inequality
and takes O(D) many symbolic steps to compute.
e
Result. We present an algorithm that computes an
√estimate D of the diameter D of the input graph G
e
such that D ∈ [D − x, D] for a parameter
log n) symbolic steps and
√x ≤ D and takes O(n · D/x √
uses a constant number of sets. For x = D this implies a bound of O(n D log n) on the number
of symbolic steps and an approximation
√ guarantee that is better than a (1 + ε)-approximation for
any constant ε > 0 (here we assume D ≥ (1 + ε)/ε; otherwise D is constant anyway and thus the
exact algorithm only takes O(n) symbolic steps). To pick the parameter x correctly, one can use the
2-approximation algorithm if the graph is strongly connected or use doubling search at the cost of an
additional factor of log n.
Searching from Neighborhood. Let a and b be two vertices with maximum distance in G, i.e.,
d(a, b) = D. We start with the simple observation that it is sufficient to determine the depth of a BFS
from a vertex with distance at most x from a to obtain an estimate that is at most x smaller than D.
→
−
Observation 6.9 (see also [Ain+ 99]). Let a, b ∈ V be such that d(a, b) = D. Then B (v) ≥ D − x
→
−
←
−
←
−
for v ∈ N x (a) and B (u) ≥ D − y for u ∈ N y (b).
→
−
Thus to obtain an estimate for the diameter, it is certainly sufficient to find a vertex u in N x (v) for
→
−
every vertex v ∈ V and compute B (u) for all these vertices. If the graph is not strongly connected,
→
−
it can happen that some vertices v can not reach x vertices and hence N x (v) might contain less than
→
−
→
−
x vertices. In this case we know that B (v) < D. Thus it also suffices to find a vertex u in N x (v) for
→
−
every vertex v ∈ V for which | N x (v)| ≥ x; we denote this set of vertices with Vx .
→
−
Corollary 6.10. Let S be a set of vertices such that S ∩ N x (v) 6= ∅ for all v ∈ Vx for x < D. Let
−
e = maxu∈S →
e ∈ [D − x, D]. Given S, computing D
e takes O(|S| · D) symbolic
D
B (u). Then D
operations and storing O(1) many sets.
Dominate each Neighborhood. An out-dominating set for a set of vertices A ⊆ V contains for each
→
−
vertex of A either the vertex or one of its successors. Finding a set S ⊆ V such that S ∩ N x (v) 6= ∅
for all v ∈ Vx is equivalent to find an out-dominating set for all vertices with degree at least x
in the following graph: Let Ĝ be the graph obtained from G by adding an edge from v to each
→
−
vertex of N x (v) \ {v} for all v ∈ V . In Ĝ every vertex of Vx has out-degree at least x. Thus
→
−
an out-dominating set for Vx in Ĝ contains a vertex of N x (v) for all v ∈ Vx , i.e., for all vertices
→
−
v ∈ V with | N x (v)| ≥ x. We adopt the classical greedy algorithm for dominating set to compute
an out-dominating set in Ĝ with the following guarantees. We prove Lemma 6.11 in the following
subsection.
Lemma 6.11. An out-dominating set S for the vertices of Vx in Ĝ with |S| ∈ O(n/x · log n) can be
found with O(n · x · log n) symbolic operations on G, storing O(1) many sets.
Overall Algorithm. Hence our algorithm is as follows. First we find a set S of size O(n/x · log n)
→
−
that contains a vertex of N x (v) for every v ∈ Vx in O(n · x · log n) symbolic steps (Lemma 6.11).
→
−
Then we compute B (u) for all u ∈ S with O(n · D/x · log n) many symbolic steps and return the
→
−
maximum value of B (u) that was found (Corollary 6.10). Together with the observations at the
e
beginning of this section we obtain the following theorem. The O-notation
hides the logarithmic
factors.

19

Algorithm Dominating Set: Algorithm for Out-Dominating Set in Ĝ
Input : Graph G = (V, E), parameter x
→
−
→
−
Output : Set S ⊆ V that contains a vertex of N x (v) for all v with | N x (v)| ≥ x
1
2
3
4

5
6
7
8
9
10
11

S ←∅;
/* dominating set */
C ←∅;
/* covered vertices */
j ← blog2 nc ;
/* size threshold */
for v ∈ V do
/* don’t have to cover vertices that reach < x
vertices */
→
−
if | N x (v)| < x then
C ← C ∪ {v};
while j ≥ 0 do
for v ∈ V \ S do
←
−
if | N x (v) \ C| ≥ 2j then
S ← S ∪ {v};
←
−
C ← C ∪ N x (v);
j ← j − 1;

12
13

return S;

Theorem 6.12 (Restatement of Theorem 4.3). A (1 + )-approximation
of the diameter of a directed
√
e
graph for any constant  > 0 can be obtained with O(n
D) symbolic operations, using O(1) sets.
6.5.1

Proof of Lemma 6.11

A fractional out-dominating set of a set A ⊆ V is a function that assigns a weight wv ∈ [0, 1] to each
v ∈ V such that for every v ∈ A the sum of the weights over v and its successors is at least one.
The size of a fractional out-dominating set is the sum of all weights wv . For Lemma 6.11 we want
to obtain an out-dominating set of Vx . The vertices of Vx have out-degree at least x in Ĝ. Thus a
fractional out-dominating set of Vx in Ĝ is obtained by assigning each vertex a weight of 1/x. The
size of this fractional out-dominating set is O(n/x). We show a greedy algorithm that finds an outdominating set of Vx in Ĝ of size within a logarithmic factor of the optimal fractional out-dominating
set, i.e., of size O(n/x · log n). The greedy algorithm is given in Algorithm Dominating Set and
is a modification of the greedy algorithm by [Joh74, Lov75, Chv79] using an idea from [BV14].
We first describe the algorithm and show that it takes O(n · x · log n) symbolic steps to output an
out-dominating set of Vx and then prove that the size of the obtained out-dominating set for Vx is
within O(log n) of the optimal fractional solution.
Algorithm Dominating Set takes the graph G = (V, E) and the parameter x as input. Constructing
→
−
the graph Ĝ, i.e., storing the sets N x (v) for all v ∈ V , is too costly. Note that there is a one-to-one
correspondence between the edges of Ĝ and the paths of length ≤ x in G and that the union of a
→
−
vertex v with its successors in Ĝ is given by N x (v) and the union of a vertex v with its predecessors
←
−
←
−
in Ĝ is given by N x (v). We recompute the sets N x (v) in O(x) symbolic steps per set when needed
by the algorithm.
←
−
Observe that the set S is an out-dominating set of Vx in Ĝ if and only if ∪v∈S N x (v) ⊇ Vx . We

20

←
−
say that the vertices of ∪v∈S N x (v) are covered by the set S. In the algorithm the set S denotes
the set of vertices added to the out-dominating set so far and the set C denotes the vertices that are
covered by S; we additionally add the vertices of V \ Vx to C, as they do not have to be covered
(lines 4–6).
The main part of the algorithm consists of a while-loop with O(log n) many iterations. The
variable j is initialized with blog2 nc and is decreased after each iteration of the while-loop; in the
last iteration of the while-loop we have j = 0. In each iteration every vertex that is not yet in S
←
−
is considered one after the other. For each vertex v ∈ V \ S the set N x (v) is computed and the
←
−
vertex is added to S if the set N x (v) contains more than 2j vertices that are not yet covered. When
←
−
a vertex v is added to S, the vertices of N x (v) are marked as covered by adding them to C. In the
last iteration we have 2j = 1 and thus all vertices of Vx that were not covered yet are added to S.
Hence the returned set S is an out-dominating set of Vx . In each iteration of the while-loop O(n · x)
symbolic operations are used, thus the algorithm takes O(n · x log n) symbolic steps in total, storing
O(1) many sets at a time.
It remains to show that the size of S is within a factor of O(log n) of the size of an optimal
fractional out-dominating set S ∗ of Vx in Ĝ with weights wv ∈ [0, 1] for all v ∈ V . The outline of
the proof is as follows: For each vertex v that the greedy algorithm adds to S, we charge a total
cost ≥ 1 to the weights wu and show that the total cost charged to wu for each u ∈ V is at most
2 · H∆u · wu , where Hi ∈ O(log i) is the i-th harmonic number and ∆u is the in-degree of u in Ĝ.
This implies that the number of vertices in S is bounded by the sum of 2 · wu · Hn over all u ∈ V ,
which proves the claim.
We charge the weights when adding v to S in Algorithm Dominating Set as follows: For each
←
−
vertex of N x (v) \ C (i.e. the newly covered vertices) we consider all vertices u that contribute
←
−
to the cover of this vertex and charge them wu /| N x (v) \ C|. Note that all vertices of V \ Vx are
←
−
←
−
contained in C and thus N x (v) \ C ⊆ Vx , hence each vertex of N x (v) \ C is covered by the optimal
←
−
fractional out-dominating set with a weight of at least one. Thus this charges at least 1/| N x (v) \ C|
←
−
per vertex of N x (v) \ C and hence at least one per vertex added to S. We have that for a fractional
←
−
out-dominating set the set N x (u) is the set of vertices to whose covering the weight wu contributes.
Thus the charge for vertex u when adding v is given by
←
−

 ←
−
N x (v) \ C ∩ N x (u)
· wu .
←
−
N x (v) \ C

We finally show that each vertex v is charged at most wv · Hn+1 . Let j 0 be the value of j when v
←
−
0
is added to S, i.e., | N x (v) \ C| ≥ 2j . Note that if a vertex u is charged a non-zero amount, then it is
not contained in C and therefore not in S. Hence we have that u was not added to S in the previous
←
−
0
iteration of the while-loop and thus by the greedy condition | N x (u) \ C| ≤ 2j +1 . Hence whenever
u is charged for a vertex v, we have
←
−
−
1 ←
N x (v) \ C ≥
N x (u) \ C ,
2
and thus

←
−

 ←
←
 ←
−
−
−
N x (v) \ C ∩ N x (u)
2 · N x (v) \ C ∩ N x (u)
· wu ≤
· wu .
←
−
←
−
N x (v) \ C
N x (u) \ C

21

Now consider the vertex u over the whole algorithm. The vertex u is charged for each vertex in
←
−
←
−
N x (u) at most once. By the above it is charged at most 2wu /| N x (u)| for the first vertex it is charged
←
−
←
−
for, at most 2wu /(| N x (u)| − 1) for the second vertex, and at most 2wu /(| N x (u)| − i + 1) for the
←
−
i-th vertex. Thus a vertex u with | N x (u)| = ∆u is charged at most 2wu · H∆u ∈ O(wu log(∆u )),
and hence we obtain an O(log(n)) approximation of S ∗ .
Acknowledgements. 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.

References
[Ain+ 99]

D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. “Fast Estimation of Diameter and Shortest
Paths (Without Matrix Multiplication)”. In: SIAM J. Comput. 28.4 (1999). Announced at SODA’96,
pp. 1167–1181 (cit. on pp. 11, 18, 19).

[BV14]

A. Badanidiyuru and J. Vondrák. “Fast algorithms for maximizing submodular functions”. In:
SODA. 2014, pp. 1497–1514 (cit. on p. 20).

[Bar+ 04]

Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar. “An information statistics approach to
data stream and communication complexity”. In: J. Comput. Syst. Sci. 68.4 (2004). Announced at
FOCS’02, pp. 702–732 (cit. on p. 5).

[Bie+ 03]

A. Biere, A. Cimatti, E. M. Clarke, O. Strichman, and Y. Zhu. “Bounded model checking”. In:
Advances in Computers 58 (2003), pp. 117–148 (cit. on p. 2).

[BGS06]

R. Bloem, H. N. Gabow, and F. Somenzi. “An Algorithm for Strongly Connected Component
Analysis in n log n Symbolic Steps”. In: Form. Methods Syst. Des. 28.1 (2006). Announced at
FMCAD’00, pp. 37–56 (cit. on p. 2).

[Bry86]

R. E. Bryant. “Graph-Based Algorithms for Boolean Function Manipulation”. In: IEEE Trans.
Comput. C-35.8 (1986), pp. 677–691 (cit. on p. 1).

[Bry92]

R. E. Bryant. “Symbolic Boolean Manipulation with Ordered Binary-decision Diagrams”. In:
ACM Comput. Surv. 24.3 (1992), pp. 293–318 (cit. on p. 1).

[Bur+ 90]

J. R. Burch, E. M. Clarke, K. L. McMillan, D. L. Dill, and L. J. Hwang. “Symbolic Model
Checking: 10ˆ20 States and Beyond”. In: LICS. 1990, pp. 428–439 (cit. on p. 1).

[Cha+ 13]

K. Chatterjee, M. Henzinger, M. Joglekar, and N. Shah. “Symbolic algorithms for qualitative
analysis of Markov decision processes with Büchi objectives”. In: Form. Methods Syst. Des. 42.3
(2013). Announced at CAV’11, pp. 301–327 (cit. on p. 1).

[Che+ 14]

S. Chechik, D. H. Larkin, L. Roditty, G. Schoenebeck, R. E. Tarjan, and V. Vassilevska Williams.
“Better Approximation Algorithms for the Graph Diameter”. In: SODA. 2014, pp. 1041–1052
(cit. on pp. 11, 12).

[Chv79]

V. Chvatal. “A Greedy Heuristic for the Set-Covering Problem”. In: Mathematics of Operations
Research 4.3 (1979), pp. 233–235 (cit. on p. 20).

[Cla+ 96]

E. M. Clarke, K. L. McMillan, S. V. Aguiar Campos, and V. Hartonas-Garmhausen. “Symbolic
Model Checking”. In: CAV. 1996, pp. 419–427 (cit. on p. 1).

22

[Cla+ 03]

E. Clarke, O. Grumberg, S. Jha, Y. Lu, and H. Veith. “Counterexample-guided Abstraction
Refinement for Symbolic Model Checking”. In: J. ACM 50.5 (Sept. 2003). Announced at CAV’00,
pp. 752–794 (cit. on p. 1).

[CGP99]

E.M. Clarke, O. Grumberg, and D. Peled. “Symbolic Model Checking”. In: Model Checking. MIT
Press, 1999. ISBN: 9780262032704 (cit. on p. 1).

[GPP08]

R. Gentilini, C. Piazza, and A. Policriti. “Symbolic Graphs: Linear Solutions to Connectivity
Related Problems”. In: Algorithmica 50.1 (2008). Announced at SODA’03, pp. 120–158 (cit. on
pp. 1, 2, 5, 7, 10, 12, 14–17).

[HW07]

J. Håstad and A. Wigderson. “The Randomized Communication Complexity of Set Disjointness”.
In: Theory of Computing 3.1 (2007), pp. 211–219 (cit. on p. 5).

[Joh74]

D. S. Johnson. “Approximation algorithms for combinatorial problems”. In: J. Comput. System
Sci. 9 (1974), pp. 256–278 (cit. on p. 20).

[KS92]

B. Kalyanasundaram and G. Schnitger. “The Probabilistic Communication Complexity of Set
Intersection”. In: SIAM J. Discrete Math. 5.4 (1992), pp. 545–557 (cit. on p. 5).

[KN97]

E. Kushilevitz and N. Nisan. Communication Complexity. New York, NJ, USA: Cambridge
University Press, 1997 (cit. on pp. 4, 5).

[Lov75]

L. Lovász. “On the ratio of optimal integral and fractional covers”. In: Discrete Math. 13 (1975),
pp. 383–390 (cit. on p. 20).

[MP92]

Z. Manna and A. Pnueli. The Temporal Logic of Reactive and Concurrent Systems: Specification.
New York: Springer-Verlag, 1992 (cit. on p. 2).

[Raz92]

A. A. Razborov. “On the Distributional Complexity of Disjointness”. In: Theor. Comput. Sci. 106.2
(1992), pp. 385–390 (cit. on p. 5).

[RW13]

L. Roditty and V. Vassilevska Williams. “Fast approximation algorithms for the diameter and
radius of sparse graphs”. In: STOC. 2013, pp. 515–524 (cit. on pp. 11, 12).

[Som99]

F. Somenzi. “Binary Decision Diagrams”. In: Calculational System Design. Ed. by M. Broy and
R. Steinbrüggen. F]: [Nato ASI series. IOS Press, 1999, pp. 303–366 (cit. on p. 1).

[Tar72]

R. E. Tarjan. “Depth First Search and Linear Graph Algorithms”. In: SIAM Journal of Computing
1.2 (1972), pp. 146–160 (cit. on pp. 5, 15).

23

