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

arXiv: https://arxiv.org/abs/1902.08455 · HTML: https://mlsanity.com/paper/1902.08455/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2019.

## Built on by (most cited first, 7 of 7)

- [Learning to Sparsify Travelling Salesman Problem Instances](https://mlsanity.com/paper/2104.09345/) (2021)
- [Learning to Prune Instances of Steiner Tree Problem in Graphs](https://mlsanity.com/paper/2208.11985/) (2022)
- [Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling](https://mlsanity.com/paper/2211.14492/) (2022)
- [Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations](https://mlsanity.com/paper/2210.16963/) (2022)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees](https://mlsanity.com/paper/2607.14545/) (2026)

## Abstract (arXiv)

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.