# Learning to Prune Instances of Steiner Tree Problem in Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 25 Aug 2022.

## Builds on (most cited first, 7 of 7)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems](https://mlsanity.com/paper/2005.05847/) (2020)
- [Identifying a set of influential spreaders in complex networks](https://mlsanity.com/paper/1602.00070/) (2016)
- [Learning to Sparsify Travelling Salesman Problem Instances](https://mlsanity.com/paper/2104.09345/) (2021)
- [Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems](https://mlsanity.com/paper/1902.08455/) (2019)
- [Learning fine-grained search space pruning and heuristics for combinatorial optimization](https://mlsanity.com/paper/2001.01230/) (2020)

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

- [ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization](https://mlsanity.com/paper/2501.17377/) (2025)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)

## Abstract (arXiv)

We consider the Steiner tree problem on graphs where we are given a set of nodes and the goal is to find a tree sub-graph of minimum weight that contains all nodes in the given set, potentially including additional nodes. This is a classical NP-hard combinatorial optimisation problem. In recent years, a machine learning framework called learning-to-prune has been successfully used for solving a diverse range of combinatorial optimisation problems. In this paper, we use this learning framework on the Steiner tree problem and show that even on this problem, the learning-to-prune framework results in computing near-optimal solutions at a fraction of the time required by commercial ILP solvers. Our results underscore the potential of the learning-to-prune framework in solving various combinatorial optimisation problems.