mlsanityData to 7 Oct 2026

Learning-augmented Maximum Independent Set

arXiv 2407.11364 ↗First posted 16 Jul 2024cs.DS cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

We study the Maximum Independent Set (MIS) problem on general graphs within the framework of learning-augmented algorithms. The MIS problem is known to be NP-hard and is also NP-hard to approximate to within a factor of n1-δ for any δ>0. We show that we can break this barrier in the presence of an oracle obtained through predictions from a machine learning model that answers vertex membership queries for a fixed MIS with probability 1/2+varepsilon. In the first setting we consider, the oracle can be queried once per vertex to know if a vertex belongs to a fixed MIS, and the oracle returns the correct answer with probability 1/2 + varepsilon. Under this setting, we show an algorithm that obtains an tildeO(√Delta/varepsilon)-approximation in O(m) time where Delta is the maximum degree of the graph. In the second setting, we allow multiple queries to the oracle for a vertex, each of which is correct with probability 1/2 + varepsilon. For this setting, we show an O(1)-approximation algorithm using O(n/varepsilon2) total queries and tildeO(m) runtime.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 28 of its 63 references that are in the map. First posted on arXiv 16 Jul 2024.

Builds on

28 of 63 references.

References · 28

  1. 2020Algorithms with Predictionscited by 152
  2. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  3. 2020Learning What to Defer for Maximum Independent Setscited by 53
  4. 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
  5. 2017The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regimecited by 31
  6. 2017Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selectioncited by 28
  7. 2020Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancingcited by 27
  8. 2021Learning-Augmented k-means Clusteringcited by 26
  9. 2022Triangle and Four Cycle Counting with Predictions in Graph Streamscited by 20
  10. 2022Chasing Convex Bodies and Functions with Black-Box Advicecited by 19
  11. 2021Robust Learning-Augmented Caching: An Experimental Studycited by 12
  12. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
16 more
  1. 2013Exact Algorithms for Maximum Independent Setcited by 10
  2. 2023Improved Frequency Estimation Algorithms with and without Predictionscited by 10
  3. 2023On Dynamic Graph Algorithms with Predictionscited by 9
  4. 2023On the Complexity of Algorithms with Predictions for Dynamic Graph Problemscited by 9
  5. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  6. 2024Constraint Satisfaction Problems with Advicecited by 6
  7. 2016Accelerating Local Search for the Maximum Independent Set Problemcited by 5
  8. 2022Optimal Clustering with Noisy Queries via Multi-Armed Banditcited by 5
  9. 2023Maximum Independent Set: Self-Training through Dynamic Programmingcited by 5
  10. 2023Online Graph Coloring with Predictionscited by 5
  11. 2022Graph Searching with Predictionscited by 4
  12. 2024Max-Cut with ε-Accurate Predictionscited by 4
  13. 2023Learning-Augmented Online Packet Scheduling with Deadlinescited by 3
  14. 2023Online Mechanism Design with Predictionscited by 3
  15. 2016On Approximating Maximum Independent Set of Rectanglescited by 2
  16. 2023Connectivity Oracles for Predictable Vertex Failurescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 6; 2026: 5.

11 papers.

  1. 2025Improved Approximations for Hard Graph Problems using Predictionscited by 4
  2. 2026Learning-Augmented Moment Estimation on Time-Decay Modelscited by 2
  3. 2025Learning-Augmented Algorithms for Boolean Satisfiabilitycited by 1
  4. 2025Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budgetcited by 1
  5. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  6. 2025Fast and Simple Densest Subgraph with Predictionscited by 0
  7. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimizationcited by 0
  8. 2026Metric k-clustering using only Weak Comparison Oraclescited by 0
  9. 2026Online Algorithms with Unreliable Guidancecited by 0
  10. 2026Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completioncited by 0
  11. 2026Learning-Augmented Approximation for Unrelated-Machines Makespan Schedulingcited by 0