Scholarlink

The maximum independent set (MIS) problem is a fundamental NP-hard optimization problem that remains challenging on large graphs. Machine learning (ML) offers the potential to aid algorithm designers in rapidly developing effective heuristics across problem variants and input distributions. However, existing end-to-end ML approaches often struggle with generalization, require extensive training data, and are rarely designed to scale to extremely large problem instances. We propose a hybrid ML–algorithmic framework that follows the Learning to Prune (LTP) paradigm: a classifier predicts vertices to fix (or prune) and the instance is simplified, before applying a state-of-the-art solver. A key challenge in this setting is due to the fact that Linear Programming Relaxation-derived features—crucial in many LTP pipelines—are often too slow and too coarse to be practical for MIS at scale. We overcome this by adapting the multiplicative weights method from the theoretical computer science literature, yielding fast, high-quality surrogate features that preserve the key structural signal of the linear programming relaxation. We showcase the flexibility of this generic technique by extending our approach to the \(3\) -path vertex cover problem ( \(VCP_3\) ). For MIS experiments, we utilize the state-of-the-art ReduMIS solver, which is capable of producing high quality solutions even on massive graphs. Results show that training on only about one hundred graph instances with ReduMIS solutions suffices for our method to achieve solutions within 10% of those obtained by ReduMIS on the test set, while running in roughly half the time, especially on dense graphs. In experiments on \(VCP_3\) , the learned models yield even stronger scalability and practical gains. We adopt the highest ranked heuristic solver from the PACE 2025 challenge for this problem. We show that on large test instances, our classifiers are powerful enough to admit aggressive vertex pruning, yielding solutions that are on average \(5\%\) better than the state-of-the-art PACE heuristic baseline in half of the runtime.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Scalable Learning Approach for Efficient Computation of Independent Set and Cover Variants

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Ryan O. Connor,
  • Noah Coleman,
  • Darren Strash,
  • Saurabh Ray,
  • Deepak Ajwani

摘要

The maximum independent set (MIS) problem is a fundamental NP-hard optimization problem that remains challenging on large graphs. Machine learning (ML) offers the potential to aid algorithm designers in rapidly developing effective heuristics across problem variants and input distributions. However, existing end-to-end ML approaches often struggle with generalization, require extensive training data, and are rarely designed to scale to extremely large problem instances. We propose a hybrid ML–algorithmic framework that follows the Learning to Prune (LTP) paradigm: a classifier predicts vertices to fix (or prune) and the instance is simplified, before applying a state-of-the-art solver. A key challenge in this setting is due to the fact that Linear Programming Relaxation-derived features—crucial in many LTP pipelines—are often too slow and too coarse to be practical for MIS at scale. We overcome this by adapting the multiplicative weights method from the theoretical computer science literature, yielding fast, high-quality surrogate features that preserve the key structural signal of the linear programming relaxation. We showcase the flexibility of this generic technique by extending our approach to the \(3\) -path vertex cover problem ( \(VCP_3\) ). For MIS experiments, we utilize the state-of-the-art ReduMIS solver, which is capable of producing high quality solutions even on massive graphs. Results show that training on only about one hundred graph instances with ReduMIS solutions suffices for our method to achieve solutions within 10% of those obtained by ReduMIS on the test set, while running in roughly half the time, especially on dense graphs. In experiments on \(VCP_3\) , the learned models yield even stronger scalability and practical gains. We adopt the highest ranked heuristic solver from the PACE 2025 challenge for this problem. We show that on large test instances, our classifiers are powerful enough to admit aggressive vertex pruning, yielding solutions that are on average \(5\%\) better than the state-of-the-art PACE heuristic baseline in half of the runtime.