On the Complexity of Fundamental Problems for DAG-Compressed Graphs
This addresses graph compression efficiency for computational geometry and algorithm design, with incremental contributions to existing compression methods.
The paper tackles the problem of compressing graphs using DAG structures, proving they can achieve better compression than tree compressions and showing that Kruskal's algorithm for minimum spanning trees can work directly on compressed graphs. It also proves that computing minimum-size DAG compressions is NP-hard, even in dynamic settings with edge updates.
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 reachable sinks in a directed acyclic graph (DAG). They generalize tree compressions, where the clusters form a tree-like hierarchy, and we give the first proof that DAG compressions can achieve better compressions than tree compressions. Our interest in DAG compression stems from the fact that several simple standard algorithms, like breadth-first search on graphs, can be implemented so that they work directly on the compressed rather than on the original graph and so that, crucially, the runtime is relative to the (typically small) size of the compressed graph. We add another entry to the list of algorithms where this is possible, by showing that Kruskal's algorithm for computing minimum spanning trees can be adapted to work directly on DAG compressions. On the negative side, we answer the central open problem from previous work, namely how hard it is to compute a minimum-size DAG compression for a given graph: This is NP-hard; and this is even the case for the dynamic setting, where we must update the DAG compression optimally when a single edge is added or deleted in the input graph.