On the Complexity of Fundamental Problems for DAG-Compressed Graphs

Florian Chudigiewitsch, Till Tantau, Felix Winkler

A DAG compression of a (typically dense) graph is a simple data structure that stores how vertex clusters are connected, where the clusters are described indirectly as sets of reac…