Succinct Graph Representations and Algorithmic Applications

AIPR assessment

Problem difficulty is high: this sits in the crowded space of graph representations and compressed graph algorithms, where small improvements are hard because baselines are mature and graph families vary a lot. The strengths compound well, since the new representation, the succinctness criteria, the representation-aware algorithms, and the large-scale evaluation all point in the same direction. The weaknesses also compound somewhat, because the construction machinery is fairly elaborate and the

Abstract

We propose new graph representations that exploit dense local structure to improve time and space simultaneously. Given an undirected graph $G$, we define a dual clique cover (DCC) representation of $G$ to be the pair $(C, L)$, where $C$ is a collection of cliques that covers the edges of $G$ and $L$ is the incidence dual of $C$. We identify classes of polynomial-time constructible DCC representations that are compact and call them succinct DCC representations. We then develop representation-aware algorithms for several fundamental graph problems. We show that graph primitives such as connected components, breadth-first search forests, depth-first search forests, and maximal matchings can be computed in time proportional to the size of a DCC representation rather than the number of edges. Combined with our succinct DCC representations, these results give a class of algorithms that either match or improve the time and space bounds of their counterparts on standard graph representations. Furthermore, we design several algorithms for constructing succinct DCC representations and establish provable guarantees on their efficiency. We evaluate several graph algorithms on DCC representations against adjacency-list-based implementations on a large collection of real-world and synthetic graphs. All evaluated applications show substantial execution memory savings and total-time speedups; for example, the connected components algorithm achieves about $9\times$ execution memory savings on average, with a maximum of $35\times$, and about $6.5\times$ total-time speedups on average, with a maximum of $35\times$. We also evaluate several DCC construction algorithms and find that the succinctness property plays a key role in making DCC representations effective for algorithmic applications.

Score Breakdown

More from this week

• Beyond Visual Fidelity: Benchmarking Super-Resolution Models for Large-Scale Remote Sensing Imagery via Downstream Task Integration
• Eliminating Hidden Serialization in Multi-Node Megakernel Communication
• A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
• Beyond Benchmarks: MathArena as an Evaluation Platform for Mathematics with LLMs
• Claw-Eval-Live: A Live Agent Benchmark for Evolving Real-World Workflows

More in Discrete Mathematics

• On Thin Perfect Matchings up to Polylogarithmic Factors
• \(\mathit{SB}(3,n)\) has no Hamiltonian cycle when \(n\) is even: a sign-of-permutation proof, with extension to all odd \(m\equiv 3\pmod 4\)
• Weak Order on the MacNeille Completion of Bruhat Order
• A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
• Hamilton decompositions of the directed 7-torus at odd modulus via root-flat certificates and a prefix-count construction