A Clique Partitioning-Based Algorithm for Graph Compression

Abstract

Reducing the running time of graph algorithms is vital for tackling real-world problems such as shortest paths and matching in large-scale graphs, where path information plays a crucial role. This paper addresses this critical challenge of reducing the running time of graph algorithms by proposing a new graph compression algorithm that partitions the graph into bipartite cliques and uses the partition to obtain a compressed graph having a smaller number of edges while preserving the path information. This compressed graph can then be used as input to other graph algorithms for which path information is essential, leading to a significant reduction of their running time, especially for large, dense graphs. The running time of the proposed algorithm is O(mnδ ), where 0 ≤ δ ≤ 1, which is better than O(mnδ log2 n), the running time of the best existing clique partitioning-based graph compression algorithm (the Feder-Motwani (FM) algorithm). Our extensive experimental analysis show that our algorithm achieves a compression ratio of up to 26% greater and executes up to 105.18 times faster than the FM algorithm. In addition, on large graphs with up to 1.05 billion edges, it achieves a compression ratio of up to 3.9, reducing the number of edges up to 74.36%. Finally, our tests with a matching algorithm on sufficiently large, dense graphs, demonstrate a reduction in the running time of up to 72.83% when the input is the compressed graph obtained by our algorithm, compared to the case where the input is the original uncompressed graph.