Speeding-up Graph Algorithms via Clique Partitioning

View PDF HTML (experimental)

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. To address this critical challenge, this paper introduces a graph restructuring algorithm that identifies bipartite cliques and replaces them with tripartite graphs. This restructuring leads to fewer edges while preserving complete graph path information, enabling the direct application of algorithms like matching and all-pairs shortest paths to achieve significant runtime reductions, especially for large, dense graphs. The running time of the proposed algorithm for a graph $G(V,E)$, with $|V| = n$ and $|E| = m$ is~$O(mn^\delta)$, which is better than $O(mn^\delta \log^2 n)$, the running time of the best existing algorithm for speeding-up other graph algorithms (the Feder-Motwani (\textsf{FM}) algorithm), where $0 \leq \delta \leq 1$. Both the \textsf{FM} algorithm and the proposed algorithm are originally formulated for bipartite graphs, but can also be applied to general directed or undirected graphs. Our extensive experimental analysis demonstrates that the proposed algorithm achieves up to 21.26% higher reduction in the number of edges and runs up to 105.18$\times$ faster than the \textsf{FM} algorithm. On large synthetic graphs with up to 1.05 billion edges, it attains a reduction in the number of edges of up to 74.36%. On real-world graphs, it achieves a reduction in the number of edges by up to 46.8%. Furthermore, when used as a preprocessing step, our approach yields up to a 2.07$\times$ speedup for the matching algorithms on large synthetic graphs, and up to a 1.74$\times$ speedup for the All-Pairs Shortest Path algorithms on real-world graphs, when compared to using the given graph as input.

Comments: Accepted at Networks

Subjects:

Data Structures and Algorithms (cs.DS)

ACM classes: G.2.2

Cite as: arXiv:2502.02477 [cs.DS]

(or arXiv:2502.02477v3 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2502.02477

arXiv-issued DOI via DataCite

Submission history

From: Akshar Chavan [view email] [v1] Tue, 4 Feb 2025 16:53:10 UTC (364 KB) [v2] Tue, 25 Mar 2025 22:09:13 UTC (363 KB) [v3] Tue, 31 Mar 2026 17:02:53 UTC (208 KB)