<p>The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong regularities has long been recognized. For instance, Galperin &amp; Wigderson (1983), Papadimitriou &amp; Yannakakis (<em>A Note on Succinct Representations of Graphs</em>, 1986) explored the question of graphs whose adjacency matrix is represented by a Boolean formula answering whether or not (i,j) is an edge given the binary representation of the node numbers i and j. Under some commonly satisfied constraints on reductions, P-complete problems for explicit graphs become PSPACE-complete for this representation, NP-complete problems become NEXPTIME-complete, etc.</p>

<p>A natural approach to such regular graphs is to represent the Boolean formula using a ROBDD; the difficulty is that classical algorithms tend to enumerate nodes one by one, which incurs exponential cost on such a representation and thus is to be avoided. There have been papers published on classical problems being solved using such a representation, e.g. Gentilini et al. (<em>Computing strongly connected components in a linear number of symbolic steps</em>), Woelfel (<em>Symbolic topological sorting with OBDDs</em>).</p>

<p>I'm wondering whether there is some survey of such techniques, because it's inconvenient to dredge the literature in such of the state of the art...</p>

<ds.algorithms><reference-request><graph-theory><survey><binary-decision-diagrams>
Algorithms on graphs represented using BDDs
David Monniaux
# Algorithms on graphs represented using BDDs

(Asked by: username_0 on 2012-06-02)

The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong regularities has long been recognized. For instance, Galperin & Wigderson (1983), Papadimitriou & Yannakakis (*A Note on Succinct Representations of Graphs*, 1986) explored the question of graphs whose adjacency matrix is represented by a Boolean formula answering whether or not (i,j) is an edge given the binary representation of the node numbers i and j. Under some commonly satisfied constraints on reductions, P-complete problems for explicit graphs become PSPACE-complete for this representation, NP-complete problems become NEXPTIME-complete, etc.

A natural approach to such regular graphs is to represent the Boolean formula using a ROBDD; the difficulty is that classical algorithms tend to enumerate nodes one by one, which incurs exponential cost on such a representation and thus is to be avoided. There have been papers published on classical problems being solved using such a representation, e.g. Gentilini et al. (*Computing strongly connected components in a linear number of symbolic steps*), Woelfel (*Symbolic topological sorting with OBDDs*).

I'm wondering whether there is some survey of such techniques, because it's inconvenient to dredge the literature in such of the state of the art...

**Tags:** ds.algorithms, reference-request, graph-theory, survey, binary-decision-diagrams

---

## 0 answers

