Speeding-up Graph Algorithms via Clique Partitioning

Akshar Chavan, Sanaz Rabinia, Daniel Grosu, Marco Brocanelli · 2025

Read Speeding-up Graph Algorithms via Clique Partitioning by Akshar Chavan, Sanaz Rabinia, Daniel Grosu, Marco Brocanelli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02477.txt.

Description

Many classic graph problems, from shortest paths to matching, slow down badly on huge dense graphs. Akshar Chavan and co-authors speed them up by first slimming the graph down. Their restructuring algorithm finds bipartite cliques, complete two-sided connections, and swaps each for a three-part structure with far fewer edges. Crucially, the swap preserves all path information, so the original algorithms run unchanged on the smaller graph.

The method's own running time beats the best-known rival restructuring algorithm, and experiments back the claim. Edge counts fell by up to 74 percent on synthetic graphs with a billion edges and up to 47 percent on real-world graphs. Restructuring itself ran up to a hundred times faster than the rival. Used as preprocessing, it sped matching about twofold and shortest-path computations up to 1.7-fold.

Catalog record

CREATORAkshar Chavan, Sanaz Rabinia, Daniel Grosu, Marco Brocanelli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02477

Browse the full library · About the Tower of Babel