Source-linked AI summary
Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time
David Eppstein, Maarten Löffler, Darren Strash
TL;DR
The paper studies maximal-clique enumeration parameterized by degeneracy, motivated by sparse graphs and the need for efficient listing algorithms. It modifies Bron–Kerbosch, proving a running time of O(dn3^{d/3}) and matching maximal-clique bounds, with optimality under the stated conditions.
Problem
Maximal-clique enumeration lacks a sufficiently analyzed parameterized approach for sparse graphs, despite degeneracy being a useful sparsity measure in practice.
Method
The paper modifies the Bron–Kerbosch algorithm and prescribes processing vertices in degeneracy order.
Results
O(dn3^{d/3}) running time and a maximum of (n-d)3^{d/3} maximal cliques establish near-optimal enumeration, with exact optimality in the stated worst-case output-size sense.
Takeaways & Limitations
The algorithm is fixed-parameter tractable in degeneracy and performs optimally in terms of this parameter, supporting the observed fast performance of Bron–Kerbosch.
Takeaways & Limitations
The running-time bound depends on explicitly processing vertices in degeneracy order; no bound is established without that order.
Abstract
from arXiv · showhide
The degeneracy of an $n$-vertex graph $G$ is the smallest number $d$ such that every subgraph of $G$ contains a vertex of degree at most $d$. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron--Kerbosch algorithm and show that it runs in time $O(dn3^{d/3})$. We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an $n$-vertex graph with degeneracy $d$ (when $d$ is a multiple of 3 and $n\ge d+3$) is $(n-d)3^{d/3}$. Therefore, our algorithm matches the $Θ(d(n-d)3^{d/3})$ worst-case output size of the problem whenever $n-d=Ω(n)$.
1 Introduction
The paper studies maximal-clique enumeration in sparse graphs, using degeneracy as a parameter to reconcile exponential worst-case theory with efficient practical performance. A modified Bron–Kerbosch algorithm achieves a near-optimal degeneracy-dependent running time, matching the parametrized worst-case output size under stated conditions.
- Maximal-clique enumeration is important in social networks, bioinformatics, document clustering, computational topology, and e-commerce.
- Exponential worst-case output makes general-purpose maximal-clique listing inherently exponential, motivating parameterized analysis.
- Degeneracy is studied as a sparsity parameter because sparse real-world graphs, including web, citation, and collaboration networks, often have low degeneracy.
- O(dn3^(d/3)) time: a Bron–Kerbosch variant lists all maximal cliques in an n-vertex graph of degeneracy d.
- (n−d)3^(d/3) maximal cliques: every n-vertex graph of degeneracy d has at most this many, and some graph attains it.
- The algorithm is fixed-parameter tractable and has a smaller dependence on d than known alternative algorithms.
2 Preliminaries
The preliminaries define degeneracy and its equivalent ordering characterization, then describe the recursive Bron–Kerbosch framework and pivoting heuristic for maximal-clique enumeration.
- Degeneracy: Degeneracy is the smallest d such that every nonempty subgraph contains a vertex of degree at most d.
- Degeneracy: A degeneracy ordering places each vertex before at most d later neighbors, and the minimum such d equals the graph’s degeneracy.
- Degeneracy: Degeneracy is a robust, efficiently computable sparsity measure related within a constant factor to arboricity and thickness.
- Bron–Kerbosch: A recursive Bron–Kerbosch call maintains R, P, and X, respectively representing the current clique, possible additions, and excluded vertices.
- Bron–Kerbosch: When P and X are empty, R is reported as a maximal clique; recursive restrictions retain only neighbors of the chosen candidate.
- Bron–Kerbosch: Pivoting delays candidate vertices adjacent to a pivot because every maximal clique must contain a non-neighbor of that pivot, reducing recursive calls.
3 The Algorithm
The algorithm combines a degeneracy ordering with Bron–Kerbosch pivoting to enumerate every maximal clique without duplication. Its recursive bookkeeping yields time O(dn3^{d/3}), nearly matching the worst-case output size.
- Algorithm design: A degeneracy ordering drives the outer Bron–Kerbosch calls, while pivoting controls recursive calls below the top level.Each outer call receives at most d later neighbors in P.
- Algorithm design: The ordered variant partitions common neighbors into later vertices P and remaining neighbors X, enabling unique assignment of each clique to its earliest vertex.The algorithm generates all and only maximal cliques without duplication.
- Pivot implementation: Pivot selection uses an auxiliary graph H_P,X, whose vertex with the most neighbors in P is selected according to the stated pivot rule.The graph is formed from P∪X while retaining edges incident to P.
- Runtime analysis: O(d(|P|+|X|)) time suffices to construct H_P,X for each recursive call, while lower-level auxiliary graphs are computed from the parent graph in total O(|P|^2(|P|+|X|)) time.These bounds avoid repeatedly constructing recursive subgraphs from scratch.
- Runtime analysis: The algorithm is nearly worst-case optimal because graphs can contain Θ((n−d)3^{d/3}) maximal cliques.The matching extremal count makes the running time optimal up to the stated factor in the relevant regime.
4 Worst-case Bounds on the Number of Maximal Cliques
For d divisible by 3 and n ≥ d+3, the maximum number of maximal cliques is exactly (n-d)3^(d/3), established by matching upper and lower bounds.
- Theorem 3: (n-d)3^(d/3) is the largest possible number of maximal cliques in an n-vertex graph with degeneracy d.This holds when d is a multiple of 3 and n ≥ d+3.
- An Upper Bound: The upper bound counts cliques by their earliest vertex in a degeneracy ordering, where each vertex has at most d later neighbors.The first n-d-3 vertices contribute at most (n-d-3)3^(d/3) cliques.
- An Upper Bound: The remaining d+3 vertices contribute at most 3^((d+3)/3) maximal cliques, yielding the total upper bound (n-d)3^(d/3).The two terms combine as (n-d-3)3^(d/3) + 3^((d+3)/3).
- A Lower Bound: The graph K_(n-d),3,3,... contains exactly (n-d)3^(d/3) maximal cliques and is d-degenerate.Each maximal clique chooses one vertex from each disjoint independent set.
- Related Results: A previously known bound for all cliques, without requiring maximality, is (n-d+1)2^d.This concerns the total number of cliques in n-vertex d-degenerate graphs.
5 Comparison with Other Algorithms
The paper compares its modified Bron–Kerbosch algorithm with earlier sparse-graph clique-enumeration methods, finding a smaller dependence on degeneracy and linear time for constant d.
- Chiba–Nishizeki: Chiba and Nishizeki’s first algorithm has worst-case time O(d^2n(n-d)3^(d/3)) for all maximal cliques.It uses O(d^2n) time per clique after translating arboricity bounds into degeneracy.
- Chiba–Nishizeki: For constant d, the Chiba–Nishizeki bound is quadratic, whereas the paper’s algorithm is linear.The comparison uses the worst-case maximal-clique count derived in Section 4.
- Alternative Enumeration: An adaptation that enumerates cliques of orders d+1 down to 1 runs in O(nd^(d+1)) time.The method removes cliques that are not maximal after enumerating them.
- Later-Neighbor Testing: Testing all subsets of later neighbors gives at most 2^d subsets per vertex, with O(d^2) testing per subset.This approach extends the earlier triangle and 4-clique algorithms to larger maximal cliques.
6 Conclusion
The paper presents theoretical evidence for Bron–Kerbosch’s practical speed and identifies degeneracy as a useful parameter, while requiring a prescribed vertex order for its runtime guarantee.
- Conclusion: The problem is fixed-parameter tractable in graph degeneracy, which is expected to be low in many real-world applications.The paper’s modified Bron–Kerbosch algorithm is optimal in terms of degeneracy.
- Scope and Limitation: The runtime analysis requires explicitly prescribing the order in which Bron–Kerbosch processes vertices.Without this particular order, the authors do not have a running-time bound.
A.1 The Degeneracy of Protein–Protein Interaction Networks
The appendix studies seven protein–protein interaction networks from BioGRID and reports their graph statistics, including degeneracy alongside size and degree measures.
- Data Source: BioGRID is a curated database of published and high-throughput protein interactions used to construct protein–protein interaction networks.The graph represents proteins as vertices and interactions as edges.
- Observed Sparsity: The selected PPI networks have degeneracy significantly lower than both their vertex counts and maximum degrees.The authors therefore expect degeneracy-parameterized fixed-parameter algorithms to perform well on these graphs.
- Graph Statistics: Table 1 reports n, m, maximum degree ∆, and degeneracy d for seven PPI networks from BioGRID version 3.0.65.The table summarizes graph statistics for the selected networks.