Research map / Graph learning / Graph algorithms and clustering
Improved Approximations for Hard Graph Problems using Predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends the epsilon-prediction model to edge-based bit predictions for NP-hard graph problems and gives learning-augmented approximations for Vertex Cover, Weighted VC, Set Cover, MIS, and MaxCut that beat classical barriers.
Problem
Classical approximation barriers for NP-hard graph problems (Vertex Cover, Set Cover, MIS, MaxCut) can be circumvented if algorithms receive noisy predictions, but prior vertex-based prediction models give weak guarantees or need strong assumptions on error counts.
Approach
Each edge provides independent epsilon-correlated bits about whether each endpoint is in an optimal solution; high-degree vertices are decided by majority vote over their incident edge bits, while low-degree parts are handled by classical solvers, and the two solutions are combined carefully.
Key results
- Vertex Cover achieves approximation 2 - Omega(log log(1/eps)/log(1/eps)) in expectation, beating the 2 barrier under UGC without predictions.
- Set Cover achieves O(log(1/eps)) approximation (constant for fixed eps), versus the Theta(log n) classical barrier.
- MIS achieves Omega(alpha(G) * eps^2 / log log(1/eps)) expected size, and MaxCut achieves alpha_GW + Omega~(eps^2), improving prior eps^4 bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add ε-correlated edge predictions to the Vertex Cover approximation algorithm | Vertex Cover · Vertex Cover | approximation ratio: 2 -> 2-\Omega \left( \frac{\log \log 1/\varepsilon }{\log 1/\varepsilon} \right) | Helped |
| Add ε-correlated edge predictions to the Weighted Vertex Cover approximation algorithm | Weighted Vertex Cover · Weighted Vertex Cover | approximation ratio: 2 -> 2-\Omega \left( \frac{\log \log 1/\varepsilon }{\log 1/\varepsilon} \right) | Helped |
| Add ε-correlated edge predictions to the Set Cover approximation algorithm | Set Cover · Set Cover | approximation ratio: O(\log n) -> O(\log 1/\varepsilon) | Helped |
| Add ε-correlated edge predictions to the Maximum Independent Set algorithm | Maximum Independent Set · Maximum Independent Set | approximation factor: \Omega \left( \frac{\log n}{n \log \log n} \right) -> \Omega\left( \frac{\varepsilon^2}{\log \log 1/\varepsilon} \right) | Helped |
| Use edge rather than vertex predictions for MaxCut | MaxCut · MaxCut | approximation factor: \alpha_{GW} + \tilde{\Omega}(\varepsilon^4) -> \alpha_{GW} + \tilde{\Omega}(\varepsilon^2) | Helped |
| Use the high-/low-degree algorithm with predictions rather than the prediction-only heuristic | Maximum Independent Set · facebook, congress, and twitch graphs | approximation ratio | Helped |
| Increase prediction quality ε for the learning-based algorithms | Maximum Independent Set · facebook and congress graphs | approximation ratio | Helped |
Surprising findings
- For vertex-prediction models with independent eps-correlated bits, the prior 1 + (eta+ + eta-)/OPT bound can grow arbitrarily beyond 2, so the naive transfer does not beat the classical factor 2.
Limitations
- Guarantees are in expectation and assume full independence of prediction bits (4-wise independence suffices per the paper).
- MIS guarantee is only a small constant-like factor eps^2/log log(1/eps), and the experiments use only moderately sized graphs with a single MIS setting.
- Weighted VC requires additional sanity-check swap steps; the framework must be tailored per problem.
Experimental setup
Datasets: facebook social network graph congress Twitter graph twitch user subscription graph (pruned to 50,000 nodes)
Benchmarks: facebook congress twitch
Metrics: approximation ratio (mean over 10 trials)
Baselines: greedy MIS approximation predictions-only heuristic CPLEX integer programming optimum
Builds on: epsilon-prediction model (Cohen-Addad et al. 2024) Caro-Wei bound Goemans-Williamson MaxCut bounded-degree independent set approximation
Closest papers by meaning
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.88)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.87)
- Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems (ICML 2025 · similarity 0.86)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.86)
- Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems (ICML 2024 · similarity 0.85)
- Incremental Topological Ordering and Cycle Detection with Predictions (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.