  Mining cohesive subgraphs from a graph is a fundamental problem in graph data
analysis. One notable cohesive structure is $\gamma$-quasi-clique (QC), where
each vertex connects at least a fraction $\gamma$ of the other vertices inside.
Enumerating maximal $\gamma$-quasi-cliques (MQCs) of a graph has been widely
studied. One common practice of finding all MQCs is to (1) find a set of QCs
containing all MQCs and then (2) filter out non-maximal QCs. While quite a few
algorithms have been developed (which are branch-and-bound algorithms) for
finding a set of QCs that contains all MQCs, all focus on sharpening the
pruning techniques and devote little effort to improving the branching part. As
a result, they provide no guarantee on pruning branches and all have the
worst-case time complexity of $O^*(2^n)$, where $O^*$ suppresses the
polynomials and $n$ is the number of vertices in the graph. In this paper, we
focus on the problem of finding a set of QCs containing all MQCs but deviate
from further sharpening the pruning techniques as existing methods do. We pay
attention to both the pruning and branching parts and develop new pruning
techniques and branching methods that would suit each other better towards
pruning more branches both theoretically and practically. Specifically, we
develop a new branch-and-bound algorithm called FastQC based on newly developed
pruning techniques and branching methods, which improves the worst-case time
complexity to $O^*(\alpha_k^n)$, where $\alpha_k$ is a positive real number
strictly smaller than 2. Furthermore, we develop a divide-and-conquer strategy
for boosting the performance of FastQC. Finally, we conduct extensive
experiments on both real and synthetic datasets, and the results show that our
algorithms are up to two orders of magnitude faster than the state-of-the-art
on real datasets.
