BDD-Based Algorithm for SCC Decomposition of Edge-Coloured Graphs

Edge-coloured directed graphs provide an essential structure for modelling and computing complex problems arising in many scientific disciplines. The size of edge-coloured graphs appearing in practice can be enormous in the number of both vertices and colours. An important fundamental problem that needs to be solved over edge-coloured graphs is detecting strongly connected components. The problem becomes challenging for large graphs with a large number of colours. In this paper, we describe a novel symbolic algorithm that computes all the monochromatic strongly connected components of an edge-coloured graph. In the worst case, the algorithm performs $O(p \cdot n \cdot \log n)$ symbolic steps, where $p$ is the number of colours and $n$ is the number of vertices. We evaluate the algorithm using an experimental implementation based on Binary Decision Diagrams (BDDs) and large (up to $2^{48}$) coloured graphs produced by models appearing in systems biology.