Learning-Augmented Maximum Independent Set

Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, Chen Wang

Introduction

The Maximum Independent Set (MIS) problem is a fundamental challenge in combinatorial optimization. Given an undirected graph $G = (V, E)$, the goal is to find the largest subset of vertices such that no two vertices in the set are connected by an edge. MIS is a cornerstone of computer science with applications in scheduling, resource allocation, and social network analysis.

However, MIS is notoriously difficult. It is not only NP-hard to solve exactly, but it is also NP-hard to approximate within a factor of $n^{1-\delta}$ for any $\delta > 0$. This means that for large graphs, traditional algorithms cannot guarantee a solution that is even remotely close to the optimum. This paper investigates whether a "learning-augmented" approach—pairing a classical algorithm with a noisy machine learning oracle—can bypass these long-standing theoretical barriers.

The Learning-Augmented Framework

The authors propose a model where the algorithm has access to an oracle (representing a pre-trained ML model). For a fixed maximum independent set $I^*$, the oracle provides a prediction for any vertex $v$: it correctly identifies if $v \in I^*$ with probability $1/2 + \epsilon$, where $\epsilon > 0$ represents the model's small advantage over a random coin flip.

The research distinguishes between two types of noise:

  1. Persistent Noise: The oracle is queried once per vertex. The answer is "sticky"; subsequent queries for the same vertex yield the same result.
  2. Non-persistent Noise: The oracle can be queried multiple times for the same vertex, with each query providing fresh, independent randomness.

Algorithmic Approaches

Persistent Noise: Neighborhood Filtering

In the persistent setting, a single noisy prediction is too weak to rely on directly. The authors' key insight is to use the graph structure as a filter. Because an independent set cannot contain adjacent vertices, the algorithm aggregates the oracle's predictions for a vertex $v$ and its neighbors $N(v)$. If many neighbors are predicted to be in the MIS, $v$ is likely not in it. By filtering out these "blocked" vertices and applying a greedy algorithm to the remainder, the authors achieve an $O(\sqrt{\Delta}/\epsilon)$ approximation, where $\Delta$ is the maximum degree of the graph. This significantly improves upon the $n^{1-\delta}$ barrier for graphs that are not extremely dense.

Non-persistent Noise: Multi-Armed Bandits and Duality

In the non-persistent setting, the algorithm treats the vertices like a Multi-Armed Bandit (MAB) problem. By querying the oracle multiple times, the algorithm uses an elimination strategy to isolate a subset of vertices where the majority are likely members of the MIS.

To transform this "mostly correct" set into a valid independent set, the authors exploit the duality between independent sets and vertex covers. They use a standard 2-approximate vertex cover to identify and remove conflicting edges (pruning). This approach yields a constant-factor $O(1)$ approximation, a remarkable result given the problem's inherent hardness.

Key Results and Insights

  • Bypassing Hardness: The most significant contribution is the proof that even an incredibly noisy oracle (only slightly better than 50/50) is sufficient to break the $n^{1-\delta}$ approximation barrier.
  • The Power of Graph Structure: The authors prove that ignoring the graph structure and relying solely on the oracle is insufficient. Their "graph-aware" approach is necessary to achieve these approximation ratios with a linear number of queries.
  • Complexity: The persistent noise algorithm runs in linear time $O(m)$, while the non-persistent algorithm achieves its $O(1)$ guarantee in $O(m \log n)$ time with $O(n/\epsilon^2)$ queries.

Conclusion and Future Work

This work demonstrates that the integration of machine learning "hints" into combinatorial algorithms can provide theoretical guarantees that were previously thought impossible. While the paper is theoretical, the authors suggest that Graph Convolutional Networks (GCNs) could serve as practical oracles in real-world applications.

Future research directions include narrowing the $O(\sqrt{\Delta})$ gap in the persistent setting and exploring whether similar approximation gains can be achieved using sublinear queries (querying fewer than $n$ vertices).

Summary updated

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 Õ((√Δ)/ε)-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 Õ(m) runtime.
BibTeX
@inproceedings{braverman2024learning,
  author = {Vladimir Braverman and Prathamesh Dharangutte and Vihan Shah and Chen Wang},
  title = {{Learning-Augmented Maximum Independent Set}},
  booktitle = {APPROX/RANDOM},
  year = {2024},
  url = {https://openreview.net/forum?id=60dWF0QPi6},
}
Figure