一句话：为边着色图提出基于 BDD 的符号 SCC 分解算法，最坏 O(p·n·log n) 符号步。
边着色有向图广泛用于特征系统、基因调控网络等复杂系统的建模与分析，其强连通分量（SCC）检测是基本问题。实际图中顶点和颜色数量可能极大，显式算法（如 Tarjan）难以扩展，而已有符号 SCC 算法又难以处理大量颜色。本文提出一种新的符号算法，能够计算边着色图中的所有单色强连通分量。该算法在最坏情况下执行 O(p·n·log n) 个符号步，其中 p 为颜色数、n 为顶点数。作者基于二元决策图（BDD）实现了该算法，并在来自布尔网络、规模最高达 2^48 的大量着色图上进行了实验评估，验证了其有效性。
Edge-coloured directed graphs provide an essential structure for modelling and analysis of complex systems arising in many scientific disciplines (e.g. feature-oriented systems, gene regulatory networks, etc.). One of the fundamental problems for edge-coloured graphs is the detection of strongly connected components, or SCCs. The size of edge-coloured graphs appearing in practice can be enormous both in the number of vertices and colours. The large number of vertices prevents us from analysing such graphs using explicit SCC detection algorithms, such as Tarjan's, which motivates the use of a symbolic approach. However, the large number of colours also renders existing symbolic SCC detection algorithms impractical. This paper proposes a novel algorithm that symbolically 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). Specifically, we use our implementation to explore the SCCs of a large collection of coloured graphs (up to $2^{48}$) obtained from Boolean networks -- a modelling framework commonly appearing in systems biology.
@article{paperbot1716,
title = {BDD-Based Algorithm for SCC Decomposition of Edge-Coloured Graphs},
author = {Nikola Beneš and Luboš Brim and Samuel Pastva and David Šafránek},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 1},
year = {2022},
doi = {10.46298/lmcs-18(1:38)2022}
}