Learning-augmented Maximum Independent Set

2024/07/16 by Braverman, Vladimir, Dharangutte, Prathamesh, Shah, Vihan +1 · 7 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2407.11364

Abstract

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 n^1-δ 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+ε. 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 + ε. Under this setting, we show an algorithm that obtains an O(√Δ/ε)-approximation in O(m) time where Δ 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 + ε. For this setting, we show an O(1)-approximation algorithm using O(n/ε²) total queries and O(m) runtime.

Cited by

• Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
• Learning-Augmented Streaming Algorithms for Correlation Clustering
• Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget
• Relative Error Fair Clustering in the Weak-Strong Oracle Model
• Improved Approximations for Hard Graph Problems using Predictions
• Fast and Simple Densest Subgraph with Predictions
• Learning-Augmented Algorithms for Boolean Satisfiability

Related

• Graph Reconstruction via MIS Queries
• An Improved Distributed Algorithm for Maximal Independent Set
• Generalising the maximum independent set algorithm via Boolean networks
• Maximum Independent Set: Self-Training through Dynamic Programming
• Improved Distributed Approximations for Maximum Independent Set