Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems
This addresses a central problem in network analysis, data mining, and computational biology, offering a practical incremental improvement for solving NP-hard enumeration variants.
The paper tackles the problem of listing all maximum cliques in graphs, a computationally hard task, by proposing a machine learning framework that reduces search space and augments solvers, achieving several-fold speedups on real-world networks with millions of vertices while retaining all optimal solutions.
We propose a simple, powerful, and flexible machine learning framework for (i) reducing the search space of computationally difficult enumeration variants of subset problems and (ii) augmenting existing state-of-the-art solvers with informative cues arising from the input distribution. We instantiate our framework for the problem of listing all maximum cliques in a graph, a central problem in network analysis, data mining, and computational biology. We demonstrate the practicality of our approach on real-world networks with millions of vertices and edges by not only retaining all optimal solutions, but also aggressively pruning the input instance size resulting in several fold speedups of state-of-the-art algorithms. Finally, we explore the limits of scalability and robustness of our proposed framework, suggesting that supervised learning is viable for tackling NP-hard problems in practice.