Fine-grained Search Space Classification for Hard Enumeration Variants\n of Subset Problems

We propose a simple, powerful, and flexible machine learning framework for\n(i) reducing the search space of computationally difficult enumeration variants\nof subset problems and (ii) augmenting existing state-of-the-art solvers with\ninformative cues arising from the input distribution. We instantiate our\nframework for the problem of listing all maximum cliques in a graph, a central\nproblem in network analysis, data mining, and computational biology. We\ndemonstrate the practicality of our approach on real-world networks with\nmillions of vertices and edges by not only retaining all optimal solutions, but\nalso aggressively pruning the input instance size resulting in several fold\nspeedups of state-of-the-art algorithms. Finally, we explore the limits of\nscalability and robustness of our proposed framework, suggesting that\nsupervised learning is viable for tackling NP-hard problems in practice.\n