Improved Approximations for Hard Graph Problems using Predictions
Authors: Anders Aamand
Justin Y. Chen
Siddharth Gollapudi
Sandeep Silwal
Hao WU
Venue: ICML 2025 poster (2025)
Keywords: learning-augmented algorithms
learning augmented algorithms
data driven algorithms
data-driven algorithms
combinatorial optimization
approximation algorithms
Primary area: theory
TL;DR: We give learning-augmented approximation algorithms for fundamental NP-Hard graph problems using edge predictions, leading to improved approximation ratios.

Abstract: We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the $\varepsilon$-prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024).  We consider an edge-based version of this model, where each edge provides two bits of information, corresponding to predictions about whether each of its endpoints belong to an optimal solution. Even with weak predictions where each bit is only $\varepsilon$-correlated with the true solution, this information allows us to break approximation barriers in the standard setting. We develop algorithms with improved approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Independent Set problems (among others). Across these problems, our algorithms share a unifying theme, where we separately satisfy constraints related to high degree vertices (using predictions) and low-degree vertices (without using predictions) and carefully combine the answers.

Improved Approximations for Hard Graph Problems using Predictions
Anders Aamand" Justin Y. Chen
Siddharth Gollapudi 3
Sandeep Silwal Hao 5US
Abstract
running times for classical algorithms (Mitzenmacher & Vassilvitskii, 2022; Chen et al., 2022a), among many other highlights.
We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the s- prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024). We consider an edge-based version of this model, where each edge provides two bits of informa- tion, corresponding to predictions about whether each of its endpoints belong to an optimal solu- tion. Even with weak predictions where each bit only e-correlated with the true solution, this infor- mation allows us break approximation barriers in the standard setting. We develop algorithms with improved approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Indepen- dent Set problems (among others). Across these problems, our algorithms share a unifying theme, where we separately satisfy constraints related to high degree vertices (using predictions) and low- degree vertices (without using predictions) and carefully combine the answers.
We focus on a recent line of work on improving approxi- mation guarantees for fundamental NP-hard problems. The goal of this line of work is to use predictions to circum- vent hardness of approximation results in the worst case (under standard complexity conjectures). One compelling motivation for Cearning-augmente algorithms for NP-hard problems is the following: if we run heavy-duty com- putation on single input, such as running commercial integer linear programming solver, can we avoid repeated computation for similar future inputs? Can we augment classical approximation algorithms with insights learned from an expensive computation to warm-start any future calls to the algorithm? More generally, how porate noisy information, which is weakly correlated with an optimal solution, into the algorithm design pipeline for NP-hard problems?
incor-
formalize this, the starting point of our paper the re- cent work of Cohen-Addad al., which introduced the e-accurate vertex prediction model for the MaxCut problem. Their model provides the algorithm designer with vertex predictions: one bit for the side of the MaxCut each ver- tex lies in. Every bit is equal to the correct answer with probability 1/2 +.
1. Introduction
Learning-uugmentt augmented algorithms have recently emerged popular paradigm for beyond worst-case analysis via incor- porating machine learning into classical algorithm design. By utilizing predictions, e.g. those learned from past or similar instances, prior works have improved upon worst- case bounds for competitive ratios for online algorithms (Lykouris Vassilvitskii, 2021; Mitzenmacher & Vassil- vitskii, 2022), space usage in streaming applications (Hsu al., 2019; Jiang et al., 2020; Chen al.. 2022b), and
We are motivated by three follow up directions. The first direction explores the setting where we are optimizing global objective function (as in MaxCut) with additional edge-constrainus. For example, this captures the classic vertex-cover or independent set problems.
Can generalize the setting of Cohen-Addad al. to obtain learning-augee -agmented algorithms for NP-hard graph optimization problems with edge constraints?
Authorrs listed alphahetically. 'University of Copenhagen PMTT "UC Berkeley *UW-Madison "University of Water- 1oo. Correspondence to: Anders Aamand <aa@diiku..c Justin Y. Chen <justc@mit.edus Siddharth Gollapudi <sgol- lapu moou@berkeley.cooo edu>>, Sandcep Silwal <silwal@es wisc.edu>> Hao WU <hao.wul wul @ uwaterloo.ca>..
This naturally leads us introduce edge predictions an extension of the vertex prediction model (Cohen-Addad et al., 2024). In our edge prediction model, every edge is equipped with i.i.d. bits for each variable participating in the edge constraint. Similar to the vertex prediction model, our predieted bits are also c-corellteed with the ground truth
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Approximations for Hard Graph Problems using Predictions
Our Learning- Approx.
Problem
Classical Approx.
Reference
with E-correlated Predictions
log log 1/e log 1/2
Vertex Cover
2
Theorem 4. 1.
Weighted Vertex Cover
2
2 Ω
log log 1/c lug 1/2
Theorem A.I.
Set Cover
Ollog n)
(log 1/E)
Theorem B.2.
Maximum Independent Set
Ω
log n n log log 1
Ω
g² log log 1/E
Theorem 5.4.
MaxCut
OGW R .8786
aGW + (2(22)
Theorem C.2.
Table Summary of our main results. All approximation factors are for multiplicative approximation. Note that the first three problems are minimization problems, so we want the approximation factor to he as as small as possible. The last two problems are maximization problems, so we desire a large approximation factor. The bounds listed above are consistent with this distinction. a&w refers to the Goemans Williamson constant (Goemans & Williamson, 1995). For all of these problems, the stated classical approximation bounds are tight assuming * NP and the Unique-Games conjecture (for MaxCut).
(see Definition 1.1 for a formal definition of our model), meaning each bit is equal to the correct assignment (e.g. is the vertex adjacent to the edge in the optimal vertex cover or not) with probability 1/2++.. The second direction explores the power of our newly introduced edge predictions.
Definition 1.1 (VC Prediction Model), Given an input un- weighted and undirected graph G. we fix some optimal vertex cover C of G. Every edge e = (u,v) outputs two bits (b,(e), by (e)) of predictions. If u then b, 1 with probability 1/2 + & and with probability 1/2 E. Similarly if u é C then bu (e) 0 with probability 1/2 + and I with probability 1/2 E. b, (e) is similarly sampled and all predictions are i.i.d. across all edges and bits.
What is the power of edge predictions in the learning-augmented setting for NP-Hard graph problems? Can we understand a general frame- work for designing augmented graph algorithms with edge-prect prediirrdict?ons??
We appropriately generalize the above edge prediction model to wide range of problems, including weighted Vertex Cover, Set Cover, Maximum Independent Set, and MaxCut. Our prediction models are unified under a similar theme (the natural analogues of Definition 1.1 to other NP-hard problems): every edge (or a hyper-edge in the context of Set Cover) gives a single bit of information for each vertex that it is adjacent to. These bits e-correlated with true underlying assignment. For brevity, omit their definitions here and refer to Section 2.
is important to note that several concurrent or follow-up works to (Cohen-Addad et al., 2024) have appeared, such as (Bampis al., 2024; Ghoshal et al., 2025; Antoniadis al., 2024; Braverman et al., 2024) which also study graph problems with edge constraints, albeit with only vertex pre- dictions, as opposed to edge predictions introduced in our work (see Section 3 for a detailed comparison). Thus, we also ask:
We demonstrate the power of our edge predic- tions by giving improved approximation bounds, which go beyond known approximation barriers, for many fundamen- tal NP-hard graph optimization problems. Our results summarized in Table 1.
Direction 2:
Can our edge predictions lead to improved ap- proximation algorithms beyond vertex predictions for fundamental NP-Hard graph problems?
For Vertex Cover and weighted Vertex Cover, we ob- tain an algorithm with approximation ratio - f(s) for (e) = log log 1/E) Note that f is much faster grow- ing function than any polynomial in in the sense that (() e) for any constant C. For any constant e, this implies strictly smaller constant than 2. Such an algorithm in the standard setting without predictions, would imply that the Unique Games Conjecture false (Khot & Regev, 2003).
Our Contributions We individually address the three directions above and our contributions towards them.
log 1/c 1og
Direction 1: For the first direction, we introduce edge pre- dictions for NP-hard graph problems. As prototypical example, the following is our prediction model for the Ver- tex Cover problem. Recall in the Vertex Cover problem we want to find the smallest subset of vertices such that every edge adjacent to some vertex in the subset.
2

---

Improved Approximations for Hard Graph Problems using Predictions
For Set Cover we obtain constant approximation factor for any constant O, in comparison to the classical setting where a O n) factor is tight (again assume P + N P) (Dinur& & Steurer, 2014). We defer the discussion of Maxi- mum Independent Set and MaxCut.
A Framework for Incorporating Edge-Predictinn in Leaming-AAgmentedd Algorithms.
Input: Graph G = (V, E), edge predictions (bu(e), (e)) E {0, 1}2 for every edge e = (), E E.
Output: A bit b1 for all E V satisfying certain edge constraints.
We highlight that in all of our main results, the notion of heavy vertices (those with large degree for an appropri- ately defined threshold) vs light vertices (those with degree smaller than the threshold) is central theme. In fact, our methodology in improving approximation ratios for differ- ent NP-hard problems can appropriately be captured by the high-level algorithm design framework of Figure 1. In this framework, high degree vertices use the majority of their prediction bits (e) for each edge e incident u of incident edges to decide if they should be included in the solution or not.
1. Set an appropriate vertex degree threshold A.
2. Loop over vertices v satisfying deg(v) > A and set
6,- = MMaaortty({bbb (((((e))
3. Remove all high-degree vertices from G, all low degree vertices which share a constraint with any high-degree vertex, as well as all the constraints corresponding to their edges
Then, all high degree vertices as well as low-degree ver- tices having an edge to high-degree vertex are removed from the graph, and we run an appropriate solver on the remaining low-degree graph. The idea is that on the one hand, for the high degree vertices, the majority vote is a very accurate prediction, and on the other hand, for graphs with bounded maximum degree, there often exist polynomial time algorithms with better approximation guarantees.
4. Run an appropriate solver on the remaining low-degree graph.
Figure I. A high-level description of the underlying structure com- mon among our algorithms.
We emphasize that the framework is as a guiding principle, but the nuances of cach problem must be separately dealt with individually. Nevertheless, we find it useful to highlight this connecting thread among our different algorithms, as it demonstrates the wide applicability of prediction model.
the Independent Set problem, an edge may be adjacent to both low-degree and high-degree vertices, and both steps (lines 2 and 4) may select both endpoints which would violate the constraints of the problem.
Some of the non-trivial parts that Figure 1 glosses over which must be handled on problem-by ba--n--b---reeene basis are:
We refer to the individual problem sections for more details.
To complement our theoretical results, we also experimen- tally test our algorithm compared to baselines which only run a worst-case approximation algorithm or only follow the predictions for the problem of Maximum Independent Set.
False-positive vertices: (high degree vertices in Line 2 on which the majority incorrectly sets b1, = 1). These are problematic since there are potentially 22()) many false-positivg vertices, which may artificially increase the size of the solution we output. For example in the Vertex Cover problem, if OPT is sublinear in n, we would not get any bounded competitive ratio, let alone ratio that is smaller than 2.
Direction 3: Lastly for the third direction, we show separa- tions between our edge predictions and previously consid- ered vertex predictions for Vertex Cover (Antoniadis et al., 2024), Maximum Independent Set (Braverman et al., 2024). and MaxCut (Cohen-Addad et al., 2024).
False- nelse-negative vertices (high degree vertices in Line 2 on which the majority incorrectly sets bg 0). On the flip side, if we fail to identify a vertex that is actually in OPT, we may not satisfy all the edge constraints, even among only those that high-degree vertices participate in.
We begin by discussing the Vertex Cover problem. Recent work by Antoniadis, Eliás, Polak, and Venzin (2024) ex- plores the learning-augmenter setting of Vertex Cover with vertex predictions. Their algorithm achieves an approxima- tion ratio of + (17 + 1) ))/) /OPT, where 17* and 17 are the number of false positive and false negative vertices, re- spectively in given predicted solution. They further prove that, under the Unique Games Conjecture and the condition (17 + "7 //OPT < 1, this bound is tight. However, this result necessarily requires strong assumptions about the pre- diction oracle to go beyond the known approximation results
Boundary effects: We must be careful when combining assignment on high-degree vertices (obtained via voting in line 2 of the framework in Figure 1) and an assignment for low- degree vertices (computed using a solver on the low-degree vertices in line 4 of Figure 1). These two solutions may conflict with each other. For example in
3

---

Improved Approximations for Hard Graph Problems using Predictions
without prediction. For instance, if we apply this result to the e-correlated vertex prediction model of (Cohen-Addad et al., 2024), where each vertex is predicted to belong to an optimal solution with probability 1/2 + independently, the ratio + (17 + 1) /OPPT can become arbitrarily larger than 2, which is significantly larger than the classic factor of 2-approximation.
results are in Section 6.
2. Preliminaries
We recall the definitions of the class NP-Hard problems studied here. Let G = (V, E) be an undirected graph with
n n= |V| vertices and m = | edges.
Thus, a meaningful instantiation of their theorem requires an implicit assumption that both the number of false pos- itive and false negative vertices are bounded. We remark that in our edge prediction model, we make no such as- sumptions about the number of false positive or negative vertices. Rather, we show that these terms can be related to the optimal vertex cover size, through a technical charging argument, detailed in Section 4.
Vertex Cover Given an input graph G, the Vertex Cover (VC) problem seeks minimum cardinality vertex subset such that every edge is incident to at least one vertex in the subset.
The weighted Vertex Cover (WVC) problem is an extension of the VC problem, where each vertex v E V is associated with a weight w(v) E IR+. The WVC problem seeks a vertex subset with minimum total weight such that every edge incident to at least one vertex in the subset.
Weighted Vertex Cover
A qualitatively similar barrier for vertex predictions arises in the Maximum Independent Set (MIS) problem. Braverman, Dharangutte, Shah, and Wang (2024) similarly address MIS with the same vertex prediction model of (Cohen-Addad et al., 2024): for each vertex, the oracle predicts its mem- bership in a fixed optimal MIS solution with probability 1/2+.. Their algorithm achieves an approximation ratio of ((VA/)), where A is the maximum degree of the graph. Note that in the worst case, this is an approximation ration of ()) if there are nigheeegree nodes in the graph. In contrast, using edge predictions allow us to obtain a constant factor approximation for any fixed E.
Set Cover Let U be a finite set of elements, and let U be a collection of subsets. The Set Cover
, Sn. (SC) problem seeks collection of the minimum number of subsets whose union is 2. For reasons that will become clear when we clarify the prediction model for the SC problem, we view each subset S; as a "vertex" and each element u E U as a hyperedge that spans the subsets con- taining u. Hence, without loss of generality, we assume U [m]
Lastly, we discuss MaxCut, the original problem studied in (Cohen-Addad et al., 2024). Here, Cohen-Addad et al. (2024) obtain acw++ approximation factor, whereas we obtain a larger advantage of acw + su(=²) over agw. the Goemans- Williamson (since E (0, E) <²)..
Maximum Independent Set Given an input graph G, the Maximum Independent Set (MIS) problem seeks a maxi- mum cardinality vertex subset such that no two vertices in the subset are adjacent.
MaxCut Given input graph G, a max cut is partition (S,7) of the vertices V such that the number of edges between S and T is maximized.
In summary, the vertex prediction model and our edge pre- diction models are to a degree incomparable: we obtain information from every edge (i.e. we receive more bits as predictions than the vertex prediction model), but our ap- proximation ratios are also stronger for MaxCut and MIS. For other problems such as Vertex Cover, we obtain a strictly smaller competitive ratio than 2, which the aforementioned results cannot without assuming bounds on the false positive and negative ratio among the predictions.
3. Related Work
(Weighted) Vertex Cover. Khot and Regev (2008) proved that, assuming the Unique Games Conjecture and P the (Weighted) Vertex Cover problem cannot be approximated within a factor of 2 E for any E > 0. Antoniadis, Eliás, Polak, and Venzin (2024) studied approximation algorithms for the weighted version of this problem under a prediction oracle that provides a predicted vertex set X of the optimal solution X This framework generalizes the vertex-based model, which predicts the membership of each vertex inde- pendently. Their algorithm achieves an approximation ratio of 1 + (1)+ +1) //PP,, where ,7t - w( X X²) is the total weight of false positives, and 1 = w(X" \ {x) is the total weight of false negatives. They further show that, assuming
Organization The paper is organized as follows. Sec- tion 2 provides formal definitions of the studied problems. Section reviews related work. Section 4 presents our algo- rithm for the Vertex Cover problem. Section 5 introduces our algorithm for the Maximum Independent Set problem. Section 6 shows experimental results for our algorithm in the context of Maximum Independent Set. Due to space con- straints, our algorithms for the Weighted Vertex Cover, Set Cover, and Max Cut problems are included in Appendix A, Appendix B, and Appendix C, respectively. Our empirical
the Unique Games Conjecture and (17 + +1 //)//TTP < 1, this bound is tight.
4

---

Improved Approximations for Hard Graph Problems using Predictions
Set Cover Dinur and Steurer (2014) proved that approxi- mating the Set Cover problem within factor of (1 (1 In is NP-hard for any > O. For instances where each set has size at most A, there exist (1 + In A) >approximation algo- rithms (Johnson, 1974; Lovász, 1975; Chvátal, 1979). On the other hand, Trevisan (2001) showed that, for such in- stances, the problem is hard to approximate within a factor of In A
clustering problems where noisy cluster labels are revealed.
4. Vertex Cover
In this section, we present Algorithm for VC under the pre- diction model of Definition 1.1, achieving an approximation ratio better than 2.
(In In A) unless P-NP.
Theorem 4.1. Algorithm returns a verlex cover with an approximation ratio of 22
log log 1/e) in expectation. log 1/s
Maximum Independent Set (MIS). The MIS problem is NP-hard to approximate within factor of n for any 5 > 0 (Håstad, 1996b). Braverman et al. (2024) attempt to bypass this barrier using the vertex prediction model. Their algorithm achieves an approximation ratio of Ö(VA/e), where A is the maximum degree of the graph.
Remark. For any C > 0, the bound e E 2- Ω
log log 1/s) holds for sufficiently small implying our log 1/5
approximation factor surpasses 2 poly(s). Moreover, as- suming the Unique Games Conjecture and PĄNP, VC re- mains inapproximable within E for any E > 0 (Khot & Regev, 2008)
Max Cut. For the classical MAXCUT problem, the cele- brated work of Goemans and Williamson (1995) achieved an approximation factor of oew x 0.878, which the best possible under the Unique Games Conjecture (UGC).
Algorithm 1 LeamedVC
1: So < Ø, A + 100 logg///)))
2: for u E V with deg(v) 2 A do
Recent research has explored methods to surpass this com- putational barrier using machine learning oracles. Cohen- Addad, d' O'Ors,, Gupta, Lee, and Panigrahi (2024) studied MAXCUT under a vertex-based prediction model, where the oracle predicts each vertex's 's label for the MAXCUT so- lution with probability 1/2 + e. Their algorithm achieves an approximation ratio of aiGW + ()) In contrast, our edge-based prediction model improves this approximation ratio to acw + {2(=²).
m, +- Majority (ajority((b.(()))))))
D if tie
end for
5: for v with deg(v) A do
6: if m, 1 and all neighbors u of v satisfy deg(u) 2
A and m. = then
7: Skip v
8: else if m. = then
So t So U (v)
10: else m.
then
11: So + So (N(v))
D. N(()) is the neighboring
Ghoshal, Markarychev, and Markarychev (2025) also in- vestigated the MAXCUT problem under the vertex-based prediction model. Their algorithms achieve an approxima- tion ratio of 1 0
vertiees of v
12: end if
13: end for
- for unweighted graphs and
52/2m/22
14: S + 2-approximate VC for heavy-heavy and heavy-
light edges not covered by So
an error bound of at most OPT - V Ees w for the weighted case.
15: S2 < (2 2-2 log -approximate VC for edges not log
covered by So US
Bampis, Escoffier, and Xefteris (2024) demonstrated that the acw barrier can be surpassed for restricted class of dense graphs under the based prediction model. Instead of querying the prediction oracle for every vertex, their algo- rithm queries only sampled set S of size θ Inn
16: S < So US US2
17: Return S
> Our VC approximation
(in)). For (G
Algorithm Given a threshold A E ([11/=In(1//8)) AI- gorithm classifies edges into three types:
graph with edge density = algorithm achieves an approximation factor of 1 -a - 8 cemr where error denotes the number of mispredicted vertices in S. Although their approach requires only sublinear number of predictions, their approach necessitates the error rate to be close to 0 to surpass the acw barrier.
2| - : their polynomial-time
Definition 4.2. For an edge e = (u, v) E with deg(u) S deg(v), we define:
heavy-heavy deg(u) 2 A,
heavy-light if deg(u) > A and deg(u) < A,
light-light if deg(u) < A.
Predictions for Other NP-Hard Problems Lastly, we remark that (Ergun et al.) and (Gamlath et al., 2022) have also studied sarning-augmenter algorithms for NP-hard
Algorithm 1 proceeds in three stages. In the first stage, it tries to cover all heavy-heavy and heavy-light edges using
5

---

Improved Approximations for Hard Graph Problems using Predictions
vertex subset So based on predicted information. Specif- ically, for each vertex with deg(u) A, a predicted bit my is computed. If my = 1, indicating v is likely in the optimal solution (C), then e' is added to Su. Otherwise, all its neighbors (v) are added to Sp, since if o & C, it must be that N(v) C.
u E C. Through careful analysis, we show that each u is charged most deg(() times, with each charge occurring with probability o(1/ deg(u)). Summing over all e C bounds the total "charging cost" by o(|C)).
Lemma 4.4 bounds the size of St. First, we show that
C2a U So covers all heavy-heavy and heavy-light edges. Thus, adding C2A \ So So ensures full coverage of these edges.
An exception in stage one occurs when a vertex and all its neighbors E (N)) have predicted bits m, and m. Vu N(e). Since e E C and N(v) _ C cannot hold simultaneously, Algorithm 1 defers the decision on Instead, in stage two (Line 14), it applies a conventional 2-approximation algorithm (Williamson & Shmoys, 2011) to identify a set S1 such that S. U S1 covers all heavy-heavy and heavy-light edges.
Next, we prove that E. [[Cza \ |ool] S c200 |Czzll This follows because if v E C2a is not in So. then either m, 0, which happens with probability Pr[m = 0] = (5 or it has been skipped at step 7. Since e has a neighbor u & (otherwise, v could be removed from C), and skipping occurs only if deg(u) 2 A and mh, 1, the probability of skipping is bounded by Pr(m... = (E2200).
After the first two stages, the remaining uncovered edges light-light edges. Algorithm 1 then applies a 2 - 2 log A -approximate VC algorithm (Halperin, log
Finally, the size bound of S₁ in Lemma 4.4 follows from S1 being a 2-approximate solution.
2002) to cover them.
Lemma 4.5 follows from: 1) C.s covers all light-light edges, and 2) the edges remaining after selecting So U U1 are exclusively light-light edges. Thus, Cea \ (So U Si) forms valid cover for these edges. Consequently, the expected size of S₂ is at most 2 - 2 log A times the size of C. \ (Sy U St).
To prove Theorem 4.1, we establish the follow- ing lemmas, each bounding the size of 'bad' events through- out the execution of Algorithm 1.
Analysis
Lemma 4.3 (False Vertices due to Prediction).
E [1So CI S e00 -CI-
Remark 4.6. We assume full independence in the prediction model of Definition 1.1 to simplify the analysis. In fact, 4-wise independence suffices to the lemmas. See the discus- sion after the formal proof of Lemma 4.3 in Appendix E for example.
Lemma 4.4 (Fix for Predicted Set). Let C2a = E deg(v)= 2 A). Then
B[Si|]] 2. 200 .Czal.
Lemma 4.5 (Cover for Light Edges). Let Cea = C Cza. Then
Proof Sketch Theorem 4. Since Sy covers all edges not covered by So SgUS1,5 S = SoUS; USS is a VC. The expected cost is bounded by
|Cea \ (So US)) (2 (2-2 log log A log A
B[[2[]] S TE
E [|S]]
< E [|So]] + E [ TE [[S2]]-
The complete proofs of them are included in Appendix E. Here, we provide brief, intuitive explanations.
E [|Soo]] can be decomposed into E E|S +C]]+ CI]. Bounding E [[S]]]] by O (Czal) with Lemma 4.4, E [So Cl] by e0 [C] with Lemma 4.3, and IE [[S]]] by E |Cy Sol (2 22-2 2 log log A with Lemma 4.5, and sum- ming up the upper bounds of E [[S]]]. E [[S. \ CI] and E []So CI] + E [|S2]]. proving the theorem.
Lemma 4.3 states that Algorithm does not add too many vertices outside C into So. This can occur in two cases:
Case One: A vertex v E C2a with m, = O causes its neighbors ((v), including vertices outside C, to be added to Sg. To bound the expected number of such vertices, suffices to show deg(v) Pr [ma, = 0) E o(1). Us- ing standard concentration incqualities, we establish that Pr [m. = 0) o(1 dcg(v)). Summing over all E Cza then bounds the number of added vertices by o((Czal).
5. Maximum Independent Set
We now present our prediction- based algorithm for approxi- mating maximum independent set. For graph G= (V, E), we denote (G)) the size of maximum independent set of G. Our goal is to find an independent set which is not much smaller than (G). In general, aGG) cannot be ap- proximated in polynomial time within multiplicative n!->
Case Two: A vertex & C with deg(v)= 2 A and m, = is directly added to Sg. To count such vertices, we use a "charging argument": we charge the cost of adding v to a neighboring vertex u & Sp. Since e & C, it must be that
6

---

Improved Approximations for Hard Graph Problems using Predictions
Algorithm 2 Learned Maximum Independent Set
set S using the majority vote of all the incident edges. Note that two adjacent notes in G2 may both be included in S during this process. To form an independent set we update S via the following clean-up up process: As long as the induced graph G[S) contains an edge, we pick any such edge and remove both endpoints from S. We denote the resulting set after this removal process by C2. The algorithm outputs the independent C defined be whichever of C₁ or C2 that has the largest cardinality.
1: A < (lg((//)
2: V& + {u Vlde }}}
3: V3 - V V
4: C1 + an 2(
Tog
approximate maximum inde-
pendent set of [A] A Tog log A
5: for V do
6: my < Majority ((bo(e))
O if tie
7: end for
8: f V> | m. = }}
For the analysis of this algorithm, we require the classic Caro- Veo bound on aGG) to "certify" that the actual optimal solution is sufficiently large. This is crucial for our charging argument of Theorem 5.4.
9: while G[S] has an edge e = (u, v) do
10: 5 5 fu, o}
11: end while
12: C2 S
Lemma 5.3 (Caro-Wei). Let G (V, E) be a graph and de- note by dhy the degree of V. Then (G)) 2 Σvev Itd."
13: [c2] 2 |c| then
14: return C2
15: end if
Our main theorem on Algorithm 2 is as follows.
16: return Ci
Theorem 5.4. Suppose & S 1/4. The expected size of the maximum independent set output by Algorithm 2, is =²
Ω (a(G)- log log 1/E
for any fixed y > O unless ZZP NP! (Hastad, 1996a). However, for bounded degree graphs, there are approxima- tion algorithms where the approximation factor depends only on the maximum degree. We will use the following theorem (Halldórsson, 1998) for handling such bounded degree graphs.
Proof of Theorem 5.4. Define T= VSA vertex v T bad if voted to be in S. We claim that the expected number of bad vertices is at most co((G). To see this, define X. = [u is voted into S] for E VSA and X x= X.. By Hoeffding's 's inequality over the voting, Pr[X, = 1] S exp(-22 22 and using the fact that e. z 2x for all æ E R. we obtain that
C' and call
Theorem 5.1 (Halldórsson, 1998)). Maximum independent log A set can be approximated within 2 & log log x) with high probability in polynomial time for graphs with maximum degree at most A.
Pr[X, = 1]
We assume access to edge predictions as before.
Finally, using that u E V> and thus has degree at least A, it follows that exp(="d,) 2 E and thus,
Definition 5.2 (Prediction Model). Given an input un- weighted and undirected graph G, we fix some maximum independent set C* of G. Every edge e = (u, outputs two bits (E) (e)) of predictions. u E C* then (e) = with probability 1/2 + e and 0 otherwise. be( is similarly sampled and all predictions are i..d. across all edges and bits.
Pr[X, =1 1| S 2dh
E
8
d
By Lemma 5.3 and linearity of expectation, it follows that the expected number of bad vertices is at most (G), as claimed. Additionally, note that for u E V, C by Hoeffding's 's inequality Pr[X, = 0] < exp( 1opp-22e0 2s de) < c Now during the clean-up phase, whenever we remove two nodes from S. one of them must have been bad. Indeed, two such nodes were included by majority vote into S but only one of them could have been in C* since they are connected by edge. Thus
With access to e-accurate predictions, our algorithm sentially achieves approximation ((s²) (note that without predictions, we cannot hope for any constant factor ap- proximation). It is presented in Algorithm 2 and works as follows. We define A = 3 (log(1/))/E², and further, VSA = {v V d S A). VA = V VSA. G G[V<A] and G2- G[VS For G, use the algorithms from Theorem 5.1 finding an approximate maxi- mum independent set C, On the other hand, for the graph G2, for each vertex E VSA, we include it in a preliminary
E| (1 -9 (l) 2: 25.a(G)
(1)
Moreover, by Theorem 5.1
log A
B[[C =S²
log log A (G1)
JZPP is the class of problems that can be solved in expected polynomial time by a Las Vegas algorithm. The conjecture P + N is almost as strong as 7.P & NP
log A
10 10 nonsssl)
=S2
2
log log
7

---

Improved Approximations for Hard Graph Problems using Predictions
Now
[|[C|] B[max((C C2]) 2 max [C=l], I))
If | n V c* / /2 then (2) gives that
E||C|| = Ω log
a(C))
log log A
Independent Epsiion:
If not, then |c* nVsll a(G)/2 and thus by (1),
B|C|] (G) [
5
a(G)
decrommeetto Sate
We finish by plugging in the value of A in the first bound.
Prstedoo Ong
6. Experiments
6.50
3.5
complement our theoretical results with an empirical evaluation for Maximum Independent Set (MIS, Section 5). The Iwo core component to implement the algorithms in setting predictions and an ap- proximation algorithm. In order to test our algorithms, we consider moderately-sized graphs on which we can solve MIS using a commercial integer program solver. We gen- crate edge predictions according to the E-accurate model based on these ground truth labels for varying e. Then, we utilize our high/low degree MIS algorithm using the greedy MIS approximation algorithm which iteratively picks the lowest degree node which is still available.
Approximation
weercwattto matts
Loin appeeeeee
6.5
024
0.25
Epstent
Independent: Set Approsimation Ratios vs. Epsilo:: Twicc
Hardware We perform all experiments workstation with an AMD Ryzen 5900X CPU and 32 GB of RAM. Deriving optimal solutions for MIS instance re- quires solving an integer linear program, which is NP-hard. In practice, solvers exist that can exploit certain structures and leverage hardware to overcome the worst-case barrier for this problem. We the CPLEX 22.1 solver (CPLEX, 2025) under academic license.
physical
apprummmtion Aato
6.6
Lcar
Onyy
Datasets We three graphs of varying sizes represent- ing real social networks: facebook (Leskovec & Mcauley, 2012), congress (Fink et al., 2023), and twitch (Rozem- berezki & Sarkar, 2021). The facebook graph has nodes representing real anonymized profiles from Facebook, with nodes representing connections between friends. has 4039 nodes and 88234 edges; the graph has an average degree of 43.69, a median degree of 25, and maximum degree of 1045. The congress graph represents the interactions between members of the 11hth Congress on Twitter: nodes correspond to the accounts of specific members of the 1 117hh Congress, and edges correspond to mentions of other mem- bers of Congress from given account. This graph has 475 nodes and 13289 edges, with an maximum degree of 214,
Epslonrd
Figure 2. Comparison of learning-augmentedd frequency estimation algorithms. Top: congress, Middle: facebook, Bottom: twitch. The plots compare Algorithm 2 with the optimal solution, the standard greedy approximation of MIS, and a degree-agnostic "predictions- only" heuristic. The algorithms are averaged across 10 trials.
8

---

Improved Approximations for Hard Graph Problems using Predictions
average degree of 43.04, and median degree of 38. The twitch graph represents Twitch users and their shared sub- scriptions: nodes represent the users, and an edge between users represent whether or not the users follow a common streamer on the platform. The resulting graph is strongly connected and has 168, nodes and 6,797,557 edges. For the purposes our experiment, we prune the original graph down 50,000 nodes and around 1.1 million edges in order to make the integer linear program for finding the optimal solution feasible.
Algorithms and Baselines Alongside the implementation of Algorithm 2. we also include 3 baselines: the optimal solution for MIS, given by an integer linear program, a "prediction-only"" heuristic, which employs the use of the edge-prediction model on the entire graph agnostic to de- gree, and a standard greedy algorithm approximation cour- tesy of Halldórsson.
Setup For the facebook and twitch graphs, fix the degree threshold for Algorithm 2 to be 10, and vary from 0.10 to 0.35. For the congress graph, we fix the degree threshold, we fix the degree threshold to 15, and vary epsilon from 00 to 0.25. At the upper end of these ranges of s both our algorithm and the predictions-only algorithm come close to approximation ratios of Due the inherent randomness in making the edge predictions, we repeat each algorithm k 10 times for each and report the mean ratio.
Results Across varying E, our algorithm outperforms the predictions-only baseline. This validates our theoretical findings where we leverage the fact that predictions are highly accurate for high degree vertices but very noisy for low degree vertices. Compared to the baseline approxi- mation algorithm, as и (which corresponds prediction quality) increases, we see the leamiig-basee algorithms eventually outperforming the baseline approximation algo- rithm. For both datasets, we show that for an appropriate our
algorithm achieves the best perfor- mance with our algorithm on both graphs.

---

Improved Approximations for Hard Graph Problems using Predictions
Acknowledgements
Cohen-Addad, V., d' d'Orsi, T., Gupta, A., Lee, E., and Pani- approximation algorithms
grahi, D. for maximum cut and related problems. In The Thirty- eighth Annual Conference on Neural Information Pro- cessing Systems, 2024.
A. Aamand was supported by the VILLUM Foundation grant 54451. Chen was supported by an NSF Graduate Research Fellowship under Grant No. 17453. S. Gollapudi is supported in part by the NSF (CSGrad4US award no. 2313998).
CPLEX, I. I. V22.1: User's manual for cplex. International Business Machines Corporation, 46(53):157, 2025.
Impact Statement
Dinur, I. and Steurer, D. Analytical approach to parallel repetition. In Shmoys, D. B. (ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 June 03, 2014, pp. 624-633, ACM, 2014. doi: 10. 1145/2591796 0111259997962221888888 2591884. URL https::///// /too::/doii.ooo 10. 0e.1115/259917 20..25511150 2591884
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here. Our work is of theoretical nature.
References
Ergun, J. C., Feng. Z., Silwal, S., Woodruff, D., and Zhou, Learning-augmenn k-means clustering, In International Conference on Learning Representations.
Antoniadis, A., Eliás, M., Polak, A., and Venzin, M. Ap- proximation algorithms for combinatorial optimization with predictions. arXiv preprint arXiv:2411 16600, 2024.
Fink, C. G., Fullin, K., Gutierrez, G., Omodt, N., Zinnecker, S., Sprint, G., and McCulloch, A centrality measure for quantifying spread weighted, directed networks. Physica A, 2023.
Bampis, E., Escoffier, B., and Xefteris, M. Parsimonious augmented approximations for dense instances of np-hard problems. In Forty-first International Confer- ence on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https: //openrevien oo ADD.:mmmmdd-DD0aaaaaa
Gamlath, B., Lattanzi, S., Norouzi-Fard, A., and Svensson, O. Approximate cluster recovery from noisy labels. In Conference on Learning Theory, pp. 1463-1509, PMLR, 2022.
Braverman, V., Dharangutte, P., Shah, V., and Wang, C. saaming-augmented maximum independent set. In Kumar, A. and Ron-Zewi, N. (eds.), Approximation, Randomization, and Combinatorial Optimization. Al- gorithmms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK, volume 317 of LIPIcs, pp. 24:1-24:18. Schloss Dagstuhl- Leibniz-Zentrrn für Informatik, 2024. doi:
Ghoshal, S., Markarychev, K., and Markarychev, Y. Con- straint satisfaction problems with advice. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1202-1221. SIAM, 2025.
Goemans, M. X. and Williamson, D. P. Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (6):1115-1145, 1995. doi: 10. 145724766677783222666 URL https://don /ttt::::/ooa...rr//00011////76/2
24. URL https: http:///t..o......./.o/. http://..00/11.../.11111 APPROX/ CERROX/RANDOR RARDDM. 2.0AD00M.024.24.. 2024.24.
Chen, J., Silwal, S., Vakilian, A., and Zhang, F. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pp. 3583 3602. PMLR, 2022a.
Halldórsson, M. M. Approximations of independent sets in graphs. Jansen, K. and Hochbaum, D. S. (eds.), Ap- proximation Algorithms for Combinatorial Optimization, International Workshop APPROX 98, Aalborg, Denmark, July 18-19, 1998, Proceedings, volume 1 1444 of Lecture Notes in Computer Science, pp. 1-13. Springer, 1998. doi: 10. 10.10077BBF80053999. URL https: /doi. org/10. 2007/BFb005395..
Chen, Y., Eden, T., Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D., and Zhang, M. Triangle and four cycle counting with predictions in graph streams. In International Confer- ence on Learning Representations, 2022b. URL https: //openreview net wwwpt/e/////aaa fww.mmiiiiioo d -diniiidiiiinnnnnn00
Halperin, E. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31685:1608-166 -123,, 2002. doi: 10.1137/
Chvátal, V. A greedy heuristic for the set-covering prob- lem. Math. Oper. Res., 4(3):233-22 235, 1979. doi: N0.1287/M0RR.433 4.3.233, URL attps://////.... /tt//ooo.orggoo////////// 10. 1287 20077/ooo /morr//oo//////////////o///////m 4.3.233.
$009753970003810997 URL https: / http:/iioog////// 1137/80097539700331
10

---

Improved Approximations for Hard Graph Problems using Predictions
Håstad, J. Clique hard to approximate within n leppiioon In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pp. 627-636. IEEE Computer Society, 1996a. doi: FA111////FCC..999955.. //doi.oog//00 1et.1110999900 1996. 548522.
Trevisan, L. Non-approximabilit results for optimization
problems bounded degree instances. In Vitter, J. S., Spirakis, P. G., and Yannakakis, M. (eds.), Proceedings on 33rd Annual ACM Symposium on Theory of Comput- ing, July 6-8, 2001, Heraklion, Crete, Greece, pp. 453- 461. ACM, 2001. doi: 10.1145/7807552388833. URL https: htops://ddi.. /tt.//ddii//////////////.. 1ttp:/110.111///72222333333
URL https:
Hästad, J. Clique is hard approximate within n lepsiloon In 37th Annual Symposium on Foundations of Computer Science, FOCS 96, Burlington, Vermont, USA. 14-16 October, 1996, pp. 627-636. IEEE Computer Society, 1996b. doi: 10.1109/SFCS (9W.SSSSCSS.999944858 1996.548522. URL https: //doi rrdoi.org//// /0/ 1119999/FCCS. 1996. 548522.
Williamson, D. P. and Shmoys, D. B. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 978-0-521-19527-0. URL http:
/ //www. cambridge http:///.......//////ooo.eeedee. isbn htlb://temm75334//ssiccc.
Hsu, C.-Y., Indyk, P., Katabi, D., and Vakilian, A. Learning- based frequency estimation algorithms. In International Conference Learning Representations, 2019.
Jiang, T., Li, Y., Lin, H., Ruan, Y., and Woodruff, D. data stream algorithms. ICLR, 2020.
Johnson, D. S. Approximation algorithms for com- binatorial problems. J. Comput. Syst. Sci., 9 (3):256-278 1974. doi: 10.1016/50022-00007774 80044-9. URL ottp:://oo..rg//10111001 S0022- 0000 (74) 80044-9.
Khot, S. and Regev, O. Vertex cover might be hard to approximate to within 2- 2- varepsilon. In 18th Annual IEEE Conference on Computational Complexity (Com- plexity 2003), 7-10 July 2003, Aarhus, Denmark, pp. 379, IEEE Computer Society, 2003. doi: 10.1109/CCC.2003. 1214437. URL https: / doi orgii.rrg/in 10.00////..000/.C... 1109/CCC. 0003.1214433
Khot, S. and Regev, O. Vertex cover might be hard to approximate to within 2- e. Journal of Computer and System Sciences, 74(3):335-333 330)399,9999 2008.
Leskovec, J. and Mcauley, J. Learning to discover social circles in ego networks. Advances in neural information processing systems, 25, 2012.
Lovász, L. the ratio optimal integral and frac- tional covers. Discret. Math., 13(4):383-32) 1975. doi: 10. 10.10660001233655779905555 8. URL httpss/////.. org/10.1016 0012 365X (75)5588888888
Lykouris, T. and Vassilvitskii, S. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68 (4):1-25, 2021.
Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. Communications of the ACM, 6577)333-35, 2022.
Rozemberczki, B. and Sarkar, R. Twitch gamers: a dataset for evaluating proximity preserving and structural role- based node embeddings, 2021.

---

Improved Approximations for Hard Graph Problems using Predictions
A. Weighted Vertex Cover
In this section, we present an algorithm for the weighted vertex cover problem, based on predictions. The main result is as follows.
Theorem A.1. The set S outputted by Algorithm 3 is valid vertex cover for the input graph G. Furthermore,
[[w((S) S (2 2- log log(1/e)
log(1/E) )) OPT.
Algorithm 3 Learned- WeinnndddWWg
So f- 2, A +- 100 le))//
2: for E with deg(v) A do
3: my <- Majority (eb
p if tie
4: end for
5: for with deg(v) 2 A do
6: (v) - (u E N(u): my 0 or deg(u) < A
7: m. then
8: Vu E (()) deg(u) 2 and m. then
9: Skip v
10:
else if w(vv
(NN (v))/e20 then
11:
So So U {b}
12:
else if ((v) 2 (NN-(u))/e" then Su - So (v)
13:
14:
end if
15:
else if m, = 0 then
(v) < 000 wNN- (v)) then
17:
So S (v)
18:
else if wv)) 210 =(N-((WW) then
19:
So - So (v)
20: end if
21: end if
22: end for
Si + 2-approximate VC for heavy-heavy and heavy-light edges not covered by So
24: S2 < (2-2
log log approximate VC for edges not covered by Su U S1 log A
25: S So US US
26: Return
b Our VC approximation
Before we dive into the analysis, we briefly discuss the ways in which Algorithm 3 differs from Algorithm 1. The main difference is that for unweighted vertex cover, it is fine if some vertices which are not in the optimal cover are voted (by our majority vote over bits) to be in the cover we output, as long as their total cardinality is small. However for weighted vertex cover, this is no longer sufficient, because even a single mistake can harm us, since we may include vertices extremely high weight, Thus, we need to perform appropriate 'sanity checks' throughout our exccution and check if we can ever make 'swap' (where we swap a vertex in our current cover with all its uncovered neighbors). This ensures that we never add vertex that has unreasonably high weight (formalized in the charging lemma below). One complication that this may prevent from adding vertices which are actually in the optimal solution execution) neighborhood has smaller weight. However, can also deal with this event by recognizing that this must mean one of its neighbors is misclassified, and use this event (which we show has appropriately low probability) in our charging scheme.
cover, if its (uncovered far in the
Recall that an optimal cover, and C = V VAC. C. Further, define VZA = {o V deg(v) 2 A), and Vea V VZa To prove Theorem A.I, we establish the following lemmas.
Lemma A.2 PeieeePoooiiieeeeeieee
(wrSS \ C)) S wC).
12

---

Improved Approximations for Hard Graph Problems using Predictions
Lemma A.3 (VC-Heayy-Fix-Weiigh), Then
E [w(( S & wa(C).
Lemma A.4 (VC-Light-Weight), Les Cea = C C2a. Then
2 - 2 log log A log A
E [w((2)] E w(C<s \ (50 US)))
Before we prove these lemmas, we apply them to finish the proof of Theorem A.1.
Proof of Theorem A.I. Since S2 covers all edges not covered by So US. S = So U U is a VC. The expected cost is bounded by
[S) < E [So(S)) + E (w(())) - [un(S22)
[w]) can be bounded by 200 (C2z according to Lemma A.3. The sum E [w((S)) + E [w((S)) can decomposed into
E [w(S [)] + B (w [C] + E (wr()))
where EE (So \. |C)] can be bounded by g (CC) according to Lemma A.2. Finally, based on Lemma A.4,
(tx(S2)) S2)] s w(C \ (8)) (2 (2-2
log log A log A
hence
E (wo n C)] + E (w(S2) S w(C) 2 2 log log A
log A
Summing up the upper bounds of E [ww(S))) (,)], E (S, \ C)] and E (S, nc)] + E [w() proves the lemma.
Proof of Lemma A.2. prove Lemma A.2, we need analyze four cases where vertices in added to So, each addressed by the following four lemmas (Lemmas A.5 A.8). The size bound of Lemma A.2 follows directly from the sum of size bounds of the following four lemmas.
Lemma A.5. Let U₁ be the set of vertices from V2a \ C that get added in Line 11 of Algorithm 3, We have
E (w())) O . -PT)..
Lemma A.6. Let U2 be the set of vertices that get added in Line 13 of Algorithm as result of vertex E C. We have
E [w((2)) E .(520.PPT)
Lemma A.7. Let Ug be the set of vertices from C. that we add to So in Line 17 of Algorithm 3, We have
B[w(Us)) E O(s OPT).
Lemma A.8. Let U4 be the set of vertices from C get added in Line 19 of Algorithm 3, We have
E(w(Us)] E O OPT).
The proofs of Lemmas A.5 to A.8 are presented after those Lemmas A.3 and A.4.
Proof of Lemma A.3. To prove Lemma A.3, we need one additional lemma.
13

---

Improved Approximations for Hard Graph Problems using Predictions
Lemma A.9. Let Us = Cza So. We have
[u((U))] E O OPT)..
(3)
The proof of Lemma A.9 is deferred those of Lemmas A.5 to A.8.
Now, to prove Lemma A.3, we will show that augmenting So with an additional set Us. ensures that all edges incident to at least one vertex V2 are covered. It follows that
E ((t) & B w(Uss) E 0( OPT).
Clearly, So U Us covers any edge incident to any vertex in C2a.
remains to consider an edge (u, a) such that e E V> \ and u E VEa. If is added So, then (u, v) is covered and we are done. Otherwise, since E V<a, v cannot be skipped step 9. If added to So, the algorithm must have added N (v) to Sp. Noting that N (t) completes the proof.
Proof of Lemmas A.5 to A.9
Proof of Lemma A.4. This simply follows from the fact that Cza (S, which is subset of the optimal cover, already covers all edges not covered by So U S1. Furthermore, after removing the edges covered by So U S1, the graph has degree log log approximation algorithm on this graph from (Halperin, 2002).
bounded by A, so we can run the 2 2
log A
Proof of Lemma A.5. First, since C, all neighbors must belong to
We charge the cost (v) of selecting E Vza \ C in Line 11 of Algorithm its neighbors in N NN(o).
For each E (v), we charge at most /e ensuring that the total charge is at most w(N (v))/e20, which covers w(v). Define an indicator X for this event. If u E Cea. Lemma E.1 gives:
Pr (X 1] Pr [m. 1]
exp (-2 deg(u) - s exp (-2-A.E" E?)
E C>a, then u e (v) implics m. = 0, yielding:
Pr = 1] S Pr [m, = 0] exp (-2 deg(u)- =²)
Set X = 0 in all other cases.
Now, for each u E C, define X, = EvEN(u) Xo-ma Thus, we bound w(ii by:
w(u)
w(u)
X,
X,,-
cl0
c10
uECaa
uEC
For each E CcA, since A = 100log(1/e)/E5
(w)).
u(uu) e1
E
Xx
- expppp (-2 A ...)) s w(() 100
e10
For each C>a.
w u)
vo(u) g10
Xx 5
deg(u) exp (-2 (eeg(u)e?)] S w(u) 100
10
14

---

Improved Approximations for Hard Graph Problems using Predictions
Therefore,
w(w) eIu
w(u) e10
B (ww( s E
Xu
+
Xu
E 0(E100.00 OPT).
ucCcs
aECsA
Proof of Lemma A.6. Every time we add N (e) in Line 13, the total weight of this set is at most w()). We can do this most once per vertex u E C, so the lemma follows.
Proof of Lemma A.7. First, since C, all its neighbors must belong to C.
We charge the cost w1) of selecting E V2a \ C in Line 17 of Algorithm to its neighbors in N (v).
For each и E N N- (v), we charge at most g0 w(u), ensuring that the total charge is at most 20 (oNN((())) (v)), which covers w(b). Define an indicator Xe-ru for this event. u E CzA.
Pr|X.-u = 51.
If C2a, then a E N- (v) implies m. 0, yielding:
Pr[X = 1] 5 Pr [m, = 0] = exp (-2 deg(u) s²)
Set X = O in all other cases.
Now, for each u E C, define X,, EveN(u) X Thus, we bound w(Ui) by:
Σ WEC.a
2t0 el0.w(u) X.
Σ
=0 w(u) X
aECsa
For each E Cra, since 100 (1)==)//)
E [0 10 w(u) Xu] S 1000. w(() < - w(u).
For each E Cza.
E [6 w(u) Xm] 20 w(u) deg(u) exp (-2 deg(u).@ vo(u).e 110
Therefore,
E [w(() < E
10 w(u) X., Σ uECzs
20 (e.w(uu X O(
uelcs
Proof of Lemma A.8. Let u E C2a. Since deg(u) 2 A = 100 log(1/e)/e3, The probability of being misclassified is at most e 200 from Lemma E.1. Furthermore, we only add N (u) in Line 19 if w(e) 2 10 -N -N)). Thus, if we add N (x)). then we add weight most w( Altogether, this means that
w(v) e10 < 1000 OPT).
E [[w(U+))
Σ rECSA
Pr(u is misclassified)
15

---

Improved Approximations for Hard Graph Problems using Predictions
Proof of Lemma A.9. A C be skipped step step 13 or step 19.
First, consider vertex C2a is skipped step 9. For each vertex C, it has at least one neighbor in C. Denote this neighbor as u. Then we know deg(u) A and m, 1. Therefore, based on Lemma 1. and given that dog(u) 2 A 100/E² log(1/E), we obtain
Pr (e is skipped at step 9] s Pr [m, = 1] & exp (-2 deg(u) .5 S E=200
(4)
Next, consider v C2a is skipped at step 12. Since v E C, it holds that
w(v) S
w(u),
MEN(e))
as otherwise (CU((()) C)) \ {v) is a better vertex cover than C, a contradiction. For each u N(v)) \ C, define the indicator Y, for being in N (v). Note that if deg(u) < A, then we must have Y, and Var [Y,] If deg(u) 2 A, then based Lemma E.
Pr (Y 1] Pr [m 2 1 cxp( 25 deg(u)) 2
200
Var [Yal < 200
(5)
Further,
E
Σ
w(u) Yu
2 =200
Σ
w(u) 2 (1 w(v).
uEN(v)iC
Now, U is skipped at step 12, which implies that
w(r) 2 (wN
2
Σ
w(u)) Yu-
(6)
g10
c10
MEN(U)iC
Therefore,
Pr
Σ
w(u)
Yu s 100 w(r)
(7)
C
< Pr
Σ w(u) Yu -E E
Σ ueENoo)e
w(u) Yu
21 - E000 200 =s0)-- -w(v)
(8)
NEN(o)Le
E EMEN(OiiC w(u)2. Var [Y,]
(9)
((1 200 (00) 2()))²
5 200 EmEN(O)iC u(u)
<
(10)
((1 220 - e00) wv))
2000
< 100
(11)
Finally, consider vertex u E C2a is skipped at step 19. This can be bounded by the probability Pr [m, = 5
Thus,
E [[wwUb)]] 100
Σ
w(v) 2 100
OPT.
(12)
vECzA
16

---

Improved Approximations for Hard Graph Problems using Predictions
B. Set Cover
In this section, we present Algorithm for SC, achieving an approximation ratio better than I... We first extend edge-based prediction model from Definition 1.1 to SC. Recall from Section 2 that in the SC problem, we treat subsets as "vertices" and elements "edges".
Definition B.1 (Prediction Model), Given a family of subsets , Each element i [m]] outputs bit (i) for every subset S, containing j E J", then by (i) with probability 1/2 + and 0 otherwise. All bits are independent across predictions.
Sn S [mm] let J S [n] be a fixed optimal set cover.
The main result is as follows. Recall that approximating the Set Cover problem (without prediction) within factor of (1-00 6) m is NP-hard for any (Dinur & Steurer, 2014).
Theorem B.2 (Learned Set Cover). Let A = 100/e² In(1/e), and J an optimal solution. Algorithm returns a solution J satisfying
||] S (1 (1+ 5 + +In)) 13*
(13)
Observe that, for given E, (1 + e + In A) is a constant which does not depend on m.
Algorithm Algorithm follows a similar philosophy to Algorithm first determines whether to include subsets size least A in the solution based on predicted information. However, unlike Algorithm simply ignores large subsets when predictions suggest they are not part of the optimal solution.
After selecting large subsets, Algorithm 4 applies the (1+ In apprrxxmmmaoo algorithm (Lovász, 1975) to small subsets, aiming to cover as many uncovered elements possible. Finally, it covers any remaining elements using an In m-approximation algorithm (Lovász, 1975) with all available subsets.
Algorithm 4 Learned Set Cover
Jiearned f Ø, A + l0gg(///))
2: Sort the Sy's in decreasing order according |Sy]
3: for [n] with [Sy] 2 A do
4: bj + Majority( (())))(((((()))))))))) (b)(s))
b if tie
5: if = and S₁ & Uerreeeree Sj then
6: Jiearned t- Jiearned U {}}
7: end if
8: end for
9: Utearned Uje UjaJeeee Sj
10: I<A h- 1j E [n] |S }}
11: Uappron +- (UjETea S,)
\ Uiearned
12: Japproz + (1 log A) appprooxie Set Cover on (U (Uapproz: Ica)
13: Jfir &- (In -aprroxxmie Set Cover on ([m] (Ulearned U U Uapprea), (n))
14: return Jtearned U Japproz U Jfi
The proof of Theorem B.2 relies on the following lemmas. At high level, the proofs of the lemmas involve bounding the expected number of optimal subsets selected by Algorithm 4 due to prediction errors (False Negatives), and applying "charging argument" to bound the expected number of non-optimal subsets incorrectly selected (False Positives).
Analysis
Lemma B.3 (False Positive). Define Js
|S,] T 2 A}, and Jer Jtearned TS
E ][Jrp| < 10, 12.11
15
(14)
Lemma B.4 (False Negative Neighhors). Define Jz = (jEJT J |S,1 2 A), and JFN = J=A Jtearned- Then
E
|8/1
< =0 |
JEJEN
17

---

Improved Approximations for Hard Graph Problems using Predictions
Lemma B.S. Let I Tappres be the optimal set cover for (U (Uopproz: Iza). Then
E I|]appreau ||
S Iea + +
|
(15)
Lemma B.6. Define Uii = [m]] ANaAWJJeaa UJ Sj.
E [ 0 1
(16)
Before we prove Lemmas B.3 to B.6, we apply them finish the proof of main result Theorem B.2.
Proof of Theorem B.2. Observe that
J| < [ + pppprool
[Jrial S
+
|tearned \ JAZAl + |Japprozl + [Jsszl.
Bounding the second term with Lemma B.4, the third term with Lemma B.5 and that Japproz being an (1 + log A) approximate solution, and the last term with Lemma B.6 gives
j| $ |ل 1 + (11++hn)(0 (n)) + - ([Aa)) t - s (1 (+ 10 +nn 1 -151
Proof of Lemmas B.3 B.6
In order to prove these four lemmas, we require the following technical result.
Lemma B.7 (Incorrect predictions). For each j E [n] s.t., |S,| 2 A, holds that
Pr ["EESteraeedd # I y 2 exp ( (- 1Sp1 62).
(17)
Proof of Lemma B.7. For each E Sj, let X; E (0,1) be the prediction by element i of the event j E T
We consider two cases. j & J", then by * Tijry if Eies, X, > |S /2. Note that E Eies, X, = =|S]| -11/ - E).
By Hoeffding's inequality, when |S A:
-2. 18,1.
Pr [by * [Er-1 Pr
Σ
X; > |S/1/2
S exp
-xxp (-21155)
|S
iES;
Therefore,
Pr [iEMtermrall # |[ET-1] = =Pr E Jeeanned S Pr [b, = 1] < exp (-2 15,111))-66))
(18)
If j E J", then bj + 1es9 if Eies, X; < /2 Note that E EiES, X.} |S (1/2 + s). By Hoeffding's
inequality, when [S 2 A:
-2 1S,12.5
Pr Pr #
= Pr Σ iES;
Xi S 1//1/2
< exp
exp (-2- --,115) -²²).
|8
Observe that
Pr [1 [eJhaarne # [[jer1
Pr [i & Jtearned]
(19)
Pr [j & Jieorned A bb +]+ Pr & Jiearned A by 1].
(20)
The former probability is bounded by
Pr & Jiearned A by = 0] PPr (b, 0] exp exp (-2-1-118) ..).
18

---

Improved Approximations for Hard Graph Problems using Predictions
When by 1, the algorithm decides not add Jeearned (therefore Jiearned) if S S S Eteareed Sy: However, for the optimal cover J holds that S E UyE Sy,, ,, as otherwise we can remove from J Therefore, Jtearned \ AJ of Ø. Let 5' be some index from Jiearned J. is added Jiearned only if by: 1. As j is processed before j, we have J |syl. concludes that
Pr & Jtearned A by = 1 Pr 1 S exp
S Pr 16, 1] s exp (-2-1Syl.e*)
We can now provide the proofs of Lemmas B.3 to B.6.
Proof of Lemma B.3. Define B = [j E [n] \ J" |8,] 2 AJ. We are going to charge the cost of selecting sets from B, to sets in J as follows: Consider a fix j E B and assume that j is selected into Jlearned. Since j is selected only if Sj & Up' Sy (at the time j is selected), there exists E S₁ \ (USrEsearned Sy):
Further, there exists some Sy for j' E I which covers element i. is easy to see j' Uyrehearme Sy: when j is selected. We will charge the cost selecting set Sj to Sy,, by setting Xj.² 1. Since Algorithm 4 selects sets into Jicorned in decreasing order according to their sizes, either of one the following happens:
1.
A s²)). |Sy1 < |S,]. then Pr [Xis' = Pr [b; 1| exp (-2-15)) - S exp (-2.A.
2.
|Syr > |Sy] and j' & Jeearnd, then Pr [Xj. 1| S Pr 1 & Jtearned] S exp ( (-2- |Syr 1 =².)
To make Xj well defined, we set Xa 0 for all other cases. Combining both cases, we have
Pr Pr[xj = 1| < exp (-2 max |S5 1,5,,A,A1 E²).
(21)
Finally, since,
Σ
|JFP|
E
Xys
Σ
jEB,j'EJ
j'EJ
JEB
we conclude that
E
[|JFp]] S Σ
|Sy1 exp (-2 max [|S 531. S -0
(22)
PET.
Proof of Lemma B.4. Consider a fixed j E Jz Via Lemma B.7, holds that
[] |Sy]] = |Sy| - Pr [ Moeneneee # [ije..] < |Syl exp (-2-15)l A exp (-2- A A=5)).
where the final inequality holds since = -2 x. 8² + In decreases when x 2 11((2 and |S 2 A 2 1/(2 {2). follows that
Σ |S
=E
Σ
[ieJenl |S
< $|Jaal exp (-2.A.6))) < TTAl 10
(23)
JEJEN
JEJSA
where the final inequality holds since
> 100/e2 (lg(1/e).
Proof of Lemma B.5. Define UšA USEJs Sj. U = UJEdeA Sj. Then USA and U is a partition of [m]. Since
I's S Jiearned U JFN, holds that
[ U
S, S USA (UJEJeNy
(24)
jEJicarned
19

---

Improved Approximations for Hard Graph Problems using Predictions
Since Tsa covers UA and UjEJex can be covered by at most EjEJØn
[Syl sets.
T $ |TZa + Σ |S
(25)
JEJeN
Taking expectation of both sides and applying Lemma B.4 finish the proof.
n
Proof of Lemma B.6. Since
ytu = [m]] \ (Ulearned U Uapproz) ) S UJEJeN
(26)
we have
UUsal Σ |syl-
(27)
JEJON
Taking expectation of both sides and applying Lemma B.4 finish the proof.
20

---

Improved Approximations for Hard Graph Problems using Predictions
C. Maximum Cut
Let G B) be a undirected and weighted graph without self loops, and A E R be a symmetric adjacent matrix, where As.j Wij 2 O, the weight of edge (i,j) if exists, and otherwise. The MAXCUT problem looks for the cut with maximum edge weight, and can be formulated as the following maximization problem
max (1/4) =1(-1
Σ (JE(")
was (x; - =z3²
(28)
Definition C.1 (Prediction Model). Given an input weight and undirected graph G, we fix some optimal solution b* (bi (n) E 1), Every edge (i outputs two bits (e) (e)) of predictions. bi(e) = bū with probability
1/2+ + and bb otherwise. (e( is similarly sampled and all predictions are i.i.d. across all edges and bits.
Our main result is stated as follows.
Theorem C.2. There is randomized algorithm for the MAXCUT problem under our prediction model which achieve approximation ratio of agw + ())²).
C.1. Algorithm
We present the road-map of the proof for the Theorem C.2. Let A E N+ E (0,1) be fixed parameters to be set later. Definition C.3. For each vertex i [n], the A-prefix for i comprises the A heaviest edges incident to i (breaking ties arbitrarily), while the A-suffix comprises the remaining edges.
Definition C.4 ((A, NaNNorrow/WWiee Vertex). A vertex i is (A. -wide if the total weight of edges in its A-prefix is at most W,, where W2 = EjeN() At is the weighted degree of i. Otherwise, the vertex i is (A, 77) -narro.
Intuitively, (A, (),))-va -wide vertex is one where the weights of the edges incident to are evenly distributed.
Definition C.5 ((A, m))NNrrow/Wiie Graph). A graph is (A, wiwd if the sum of weighted degrees of (A, na)roow vertices is at most 17- W, where W = Exe(s) W,. Otherwise, the graph i is (A, nnrrow.
(A, -Narrowww Graph. We apply the following result from (Cohen-Addad et al., 2024), which does not rely on the predicted information.
Proposition C.6 (CCohen-Addad et al., 2024)). Given a (A, -n)rrow graph, there is randomized algorithm for the MAXCUT problem with an (expected) approximation ratio of agw + /A?)
(), -/ideee Graph. We are going to prove the following key result. Algorithm 5 is adapted from (Ghoshal et al., 2025). The original work is based on the vertex prediction model and does not include proof for (A, wiide graphs. We extend their proof to cover this case.
Theorem C.7. Given -widd graph and the prediction model of Desinition C. there is randomized algorithm (Algorithm for the MAXCUT problem with an (expected) approximation ratio of
1 1-0 V E EEA +1)
(29)
Proof of Theorem C.2. Combining Proposition C.6 and Theorem C.7, and by setting n to be suitably small universal constant, and setting A = 1/cc/ss s) for some suitably small universal constant e finish the proof.
Remark C.8. The paper (Cohen-Addad et al., 2024) achieves ration of
(1-0(-1) ( + +))
0.98
+ 0.02 agW
(30)
for (wid) graphs. Therefore, they need to set A 1/(c=²), resulting in final ratio of ocw +5((e4) for (A, -nrroow graphs.
The proof of Theorem C.7 relies on the following lemmas.
21

---

Improved Approximations for Hard Graph Problems using Predictions
Algorithm 5 Learning Based MAXCUT
1: Truncation. Define the matrix As, by
0. min {Aiss W,/A),
Vj [n], is (A, 7)) narrow Vj E [n], is (A, 77) -wide
A
(31)
2: Prediction.
bi(e)
Vie [n], 2 deg(i)
(32)
28
eEE,
3: Optimization. Solve the convex optimization problem
min =E[-1,1]
x T Az + As Ar
(33)
4: Rounding, For each [n]. choose y4 E {1,, which minimizes
(11--1, yi, Imm )² Á (y1--1, Yis T++1m))
(34)
where (Hi:i-1: Mi, Fi+ 1m) is the vector whose first - 1 entries comprise the chosen yI...., 1/-1, the j(th) entry is ya and the remaining entries are T.,
Lemma C.9. and let Err = Eie(ni v EJee()) Pi Var [zz] Algorithm returns a solution yf satisfying
E AyyT (b") Ab" S 2nW + Err.
(35)
Lemma C.10. Given prediction model in Definition C.I, and an (A,1) -idde graph, it holds that
V
Err S E.
(36)
Proof of Theorem C.7. First, since (b²)² y,
have
Σ wi (b; - bj)² = Σ
Wisj (b²)) + (b))² - 2- 6,
2-b bj)
Σ
Wi.j (1z 13 - D9 -b))
$
Σ
Wi. (vi + 1) y: Dj + y: Uj 2. b7 b7))
$
Σ
Wins - 31) 2 8² Ay - 2 (b")T Ab
Therefore,
Σ Wans (v: 3/) Σ
Wi.j (b: - -b)
1 (y Ay (6")TAb') opl
1 (. Ay (b*)
i
Combing Lemmas C.9 and C010 and noting that opt W/2 gives
n Ay (b*) AB c0 ((-1)) +1) oph)
[V
(37)
which proves the claim.
To prove Lemma C.9, we need the following lemmas. Lemma C.11.
Ab Az A=|l] < Err
(38)
22

---

Improved Approximations for Hard Graph Problems using Predictions
Lemma C.12 (Rounding Error).
5² Ay S x² Ax.
(39)
Proof of Lemma C.9: First, note that
y" Ay (6")"AA Ab"
Σ
Ar. (yt- Y/ - bi .b))
=
= Σ
(Ais - -Ais) (yi : - by .b) + Σ
Aca (V: - b; 65)
141
if
s 2
Σ
(Ars -Ais) + Σ
Ais (2: y3 0g -j)
ifj
1
We will bound Σijs (Ais Ans)) by 7,, and ΣiØj A (ys- y, b; .b) by Err, which proves Lemma C.9.
Bounding Σijs (Ais - A.s). Denote Vz the collection of (A, 11) narrow vertices. Since the graph is (4, n)dwe,,, we have For each E Vs.
AL5= = Σ W; m...W. W.
(40)
'EV, JEiN]
iEV,
Next, consider a (A, 7)) vertex i. holds that deg(i) 2 A, and the maximum edge weight in its A-suffix bounded by 77 W,/A Since
Á.j = min (Ar 1) W./AJ, Vj E [r]]
(41)
Ar.j - A.j 0 for each j in the Aufuff.. Therefore, the gap Σits (Ai. - Ars) is at most the total weight of edges in its A-prefix, which is at most v W,. It follows that
Σ
Σ
(An A.s) S
Σ
n n. W. S.
(42)
KEIN
JE
Bounding Eins Ars y1 - 6j Bj). First, based on Lemma C.12:
v" Au (b*) Ab = - Ax + xJ Ax (b") < <x Ax -bb)T
-
It remains to bound I.T Är (b*)T SIOJTAb Ābo. First, observe that b* is also solution for the optimization problem specified in Equation (33). Since x is the optimal one,
x Az + Az - Ar/1 < {bb)) + AAz - Āb-
Further, since x E {-1,1}"
xf År x² Az = == (Ar Å2) s ||~1|ac |Ax Azll s Ar Az
Therefore,
x² Ax (b*) = IT Ax - xT Āz + x. A= - (B2)TAB* Ab*
< | A - Az +x Áz (b*)T T Ab s (b*)T As | Áb" || (b*)TAb.
Taking expectation of both sides and observing that E [2:] = bg gives
E T. (b²)²² ĀB- (b*)"áB**
E ds Āb- 11
Applying Lemma C.11 finishes the proof.
23

---

Improved Approximations for Hard Graph Problems using Predictions
Proof of Lemma C.I.I First, note that Vi E [m]] it holds that
E [=:] by
E (Az) E
Asg2s
(Ab"):
jEEN)
Since the (e)sss 's are least pairwise independent, are the Zz. Therefore,
Var (d)))
Σ
Mgg Var [zy].
jEiN]
By Jensen's 's inequality
E V (de)) (Ab+)s
/
s <VB B (Az), - (Ab+))) 12)
1 (Az)): E [(A2)) 2
[|
=1B
Σ jE[M]
Aī. Var [z
=1
=
Finally,
E
1=
Σ
E
(Ab") -(Aa)))
5 Σ
AP.
Var [z)].
iE(n)
iEin]
SE(x]
Proof of Lemma 1. First, the variance of the z; satisfies
Var [zi] E E
1 deg(i) E²2)
Therefore,
RS deg(i)
Err
Σ
Σ sE(M]
Ab, Var [2y] E
Σ
Σ
(E[m]
iEin]
jE(n]
Denote V/S the collection of (A, nnarrrw vertices. For each i E Vs, since À = O,
A?
deg(j) O. jE(m)
(43)
On the other hand, for each (A, widd vertex i, it holds that deg(i) 2 A, and
max As,j S 77 W.AA
(44)
jE[n]
Therefore,
AB deg(i)
AP
A.
W
VT W
Σ
<
A
A
JEIn]
JE(n)
jE[n]
And
W
7 W
Σ
Σ
deg( (
A
jc [n]
iæV, cC[n]
24

---

Improved Approximations for Hard Graph Problems using Predictions
Proof of Lemma C.12. We prove by induction on that
W5, (y1s-1, Vi, 1m) v.AAA. Av.
(45)
When since 11, 0, it holds that
f(y1) (21, A (y1, F2m) = 91
2A +C,
where C' does not depend on y1- Therefore, f is linearly in yi, and either f(-1) - f(m)) or f(1) < f(x) holds. We can
pick 1/1 E } so that (()) S f(1)..
Via similar argument, for each 1, either:
(U1--1, -1, 11+1 ) 1,, 11+1m) S (11--1, Fem) À 1, S x² Ax,
or
(11--11,,, 1, 24+1n) T (11--1, 1, 1141m) S (11--1, Iin)) T (1/11 (11:-1, S xxAAA Az.
hold. This proves our claim.
25

---

Improved Approximations for Hard Graph Problems using Predictions
D. Probability Facts
Fact D.I. Let .I...,, Xn be 4-wise independent random variables with mean 0. Then for each E 1820-
Σ ieln
E[
6
Eits
B B[
Pr Σ iE(n]
X
22
(46)
t
Proof. By Markov's inequality,
E EiEnn] X; -1
Pr
Σ
X,
2
(47)
KE[n]
On the other hand, since the X; are 4-wise independent mean zero random variables,
(1)
E
Σ X,
=
E
x2x3
+2
Σ
X,X,XX
+
Σ
XXxi
(48)
2
iEin]
iE [n]
#j
Σ
B|X +
Σ
E[X?|
E[X3]
(49)
kE[m
E. Proofs from Section
Proof of Theorem 4.1. We first claim that S + So US S2 is vertex cover. This claim is straightforward: So U.₁ forms vertex cover for heavy-heavy and heavy-light edges, while Sa covers light-light edges. Together, they cover all edges.
Next, combining Lemma 4.3, Lemma 4.4, and Lemma 4.5 yields:
E[|s|]
< E
| So
| [S
(50)
< E
[
n + 1% C| + [S| + |
(51)
log log A ) log A
< E
18. nc ncn SSu \ C| + |S IC&A \ (S. US))
2 -
(52)
S ncn CCZA (So US::) (2-2 log log A
< E
+ t |C| + 2 200
|Czal
(53)
log A
log log A
< [C]
2 2
10 |C| 2. g00
200 |Czal
(54)
log A
log log A log A
log log 1/5
log 1/s ))
< |C|
2 3 3- 10
|C|- 2 Ω
(55)
Proving Lemmas 4.3 to 4.5 require the following additional lemma.
Lemma E.1. Let be a fixed vertex satisfyyng deg(v) 2 A. Then
Pr m. + 1 lveci] I exp (-2 deg(v) .
(56)
Proof of Lemma E.I. Without loss of generality, assume that v E C. For each u E N(v), let X, E {0, be the prediction of whether E C, by the edge = (u, v). Then m. o [pec] EuEN(o) X, S deg(n)/2. Note that
26

---

Improved Approximations for Hard Graph Problems using Predictions
[ueN(()>Xe Xu} = deg(v) (1/2 + e). By Hoeffding's inequality, when deg(v) 2 A
Xa s deg(u)/2 s <exp (-2- deg(r)2.62) deg(v) ) =cxp exp (-2
Pr
Σ uEN(v)
deg(t). .²²)
We are ready to prove Lemmas 4.3 to 4.5.
Proof of Lemma 4.3. Vertices from V \\ C are added to So when one of the following events occurs:
(1) There exists vertex v E C2a such that m. = 0. In this case, Algorithm 1, line 12 adds ((v) to So, which may include vertices from V C.
(2) A vertex & C with deg(v) A and m.
also be added to So in Algorithm line 10. This occurs only if
either:
(a) v has neighbor with deg(u) < A; or
(b) all its neighbors u satisfy deg(u) 2 A, but least one neighbor has m. 0. In this case, v is also added to So when Algorithm 1 adds N(u) So. This is already accounted for in Case (1).
To bound the number of vertices added So from V \ C, it suffices to separately bound the numbers added from cases (1)
and (2.a).
Case (1): In this case, based on Lemma E.I, the expected number is bounded by
0m deg(v)
=
Σ
Pr [m, =0] -de(())
(57)
pECza
rECza
Σ exp (-2 deg(v) .6?) deg(u)
(58)
vECza
|C2a| exp (-2 . A 8²) A
(59)
< 10 |Czal:
(60)
where Equation (59) follows since the function y = x exp (-2 x E2)
E2) decreases when x 2 11/(2-=²) and Equation (60)
follows since A 2 1/=², for moderately small E, holds that exp (-2- A =²) A A 10
Case (2.a): We partition the vertices v added to Sp in the this case, into collection of |C] subsets, denoted as (Pu: PPa:u E Cea), as follows. Since v & C, holds that N(v) S C, otherwise the edges incident to are not cov- ered. Therefore, N(u)nCea+* Ø. We pick an arbitrary vertex u E ((v) and place into P... Based on Lemma E. we see that
Pr(ve E Pa]
[m, = 1] S exp (-2 A E?)
It remains to bound Euec.a |Pal. Since each |Pa| can be viewed as sum of at most deg(u) < A indicator random variables, each taking one with probability at most exp (-2 A =²)). concludes that
Σ NECCA
E
exp Σ A exp (-2 2²) =0 10. -Caal,
(61)
REC.A
where the last inequality holds if & is moderately small.
Case (2.b): Note that such a vertex v is already accounted for in Case (1) since has neighbor u E C>a with my = 0.
27

---

Improved Approximations for Hard Graph Problems using Predictions
Remank E.2. Indeed 4-wise independence in the prediction model of Definition 1.1 is enough establish this proof. For example, let Cza, and would like to prove that
deg(v) Pr [m, = 0j o(1).
(62)
Let X, = 1 (tu.))))) (2 - =). u E N(v) be 4-wise independent random variables, where b,((u, u)) is the prediction of from the edge (u, v). Then
E xx,] = 0,
1
E
+
2
1 +
1 + = + )
1
1
( -
1
E E =
+
8
22
-
+
2 S
2
2
4
8
Based on Fact D.I, there exists some universal constant 0, s.t.,
Pr [m,, 0] ddg(v))= Pr
Σ X 2 deg(v) E deg(u) LEE((e)
deg( (1)/8////)))) + 6- deg(v) (deg(v) 1)/16 deg(v) S
d
dog(v)e*
If we pick a threshold A properly, e.g., A E then deg(1) 2 A implies that
deg(v)e O(s1))
(63)
Proof of Lemma 4.4. We will show that
(1) C2 S. covers all heavy-heavy and heavy-light edges, and
(2) E| Sol] S 200
|Czall
Let Ci be the optimal vertex cover for the collection of edges that are incident to most one vertex with degree 2 and covered by Sg. follows that [1 S |C2A
\
Sol
E S1S
||
< B |G < E/2 [2a \ Soll s 2 2 200
|C2all
(64)
Proving (1): Each heavy-heavy edge is trivially covered by Cza, as at least one of its endpoints belongs to C and, consequently, C2a. For each heavy-light edge (u, v), if one of its endpoints belongs to Cza, then the edge is covered. Otherwise, without loss of generality, assume (og > and u & C2a. We claim that (v, u) must already be covered by So-
Note that does not satisfy Line 7 of Algorithm 1, as one of its neighbors, has degree deg(u) < A. Therefore, Algorithm either adds v to Sg. or it adds N (t) to Sg. In both cases, (v, u) is covered by Sp.
Proving (2): Consider fixed u C2a. If & So. then either
m. which happens with probability (according to Lemma E.1)
Pr [m, 0] exp (-2-deg(v) =²) I exp (-2.A.=²).
(65)
Or all its neighbors u have degree 2 A and m. = 1. In this case, at least one neighbor u & C, as otherwise, we could remove v from C while maintaining it as valid cover. Hence,
Pr [e & So) S Pr [m.. = 1] S exp (-2 deg(u) &?) s exp (-2. A.6
28

---

Improved Approximations for Hard Graph Problems using Predictions
We conclude that
EIC (Sol]=
[[ess) [C2al exp (-2.A = =C22>| exp (-200 (-200-In(4/3)) $|2aa| (E200
vECSa
Proof of Lemma 4.5. By definition, So U S1 covers all heavy-heavy and heavy-light edges. Since C&a is cover for the light-light edges, also covers any edges not covered by So S1. Furthermore, since S2 a (2 2 log log -approximate cover for the edges not covered by So U S1. the claim follows.
log A
29


Reviews:
[{"review_id": "5rQGKKhxBE", "reviewer": "Reviewer_Q5LC", "summary": "They design algorithms for some fundamental NP-hard graph problems such as (Weighted) Vertex Cover, Set Cover, Maximum Independent Set, and MaxCut when we have some random information about an optimal solution. More precisely, they assume that for each edge, we have two bits for its endpoints regarding whether they are in the optimal solution or not, but this bit does not have the accurate data. Instead, each bit correctly reflects the optimal solution with probability $1/2 + \\epsilon$. Their algorithms achieve a better approximation factor than those designed for the standard setting without predictions.\n\nTheir general idea is that for high degree vertices, decide their status in the solution based on the majority of information we have about them. This makes sense since if the degree of a vertex is $d$, then we have a $d$ sample about whether this vertex is inside the optimal solution or not. As the number of samples increases, the confidence in knowing the vertex's state improves. Finally, they handle low-degree vertices using a simple greedy approach specific to each problem.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.\n\n> Their general idea is that for high degree vertices, decide their status in the solution based on the majority of information we have about them ... Finally, they handle low-degree vertices using a simple greedy approach specific to each problem.\n\nWe agree that our high level idea of separating the vertices into heavy and light degrees is quite intuitive and generalizes across many problems. We view this as a strength of our framework. However, we would like to point out the many technical challenges we need to overcome. \n\nOur ‘high degree’ threshold is a constant (depending on $\\epsilon$ and independent of the graph size). This alone is not enough to union bound over potentially $O(n)$ high-degree vertices. Thus, there is always a non-negligible chance that a high-degree vertex gets misclassified. This can be very problematic since high-degree vertices can be highly influential in the final solution. For example in vertex cover, a high-degree vertex which is misclassified to not be in the solution can make us add all of its neighbors in the vertex cover, leading to an unbounded competitive ratio if we are not careful. Thus in all of our problems, we need a sophisticated “cleaning step” which not only fixes any misclassifications, but also helps us successfully merge the solution found for low-degree vertices. This is non-trivial since the solution on low-degree vertices may conflict with the solution on high-degree vertices, e.g. for independent set. Our cleaning step is especially subtle for the weighted vertex cover problem,where  the weight of a vertex is unrelated to its degree (see the paragraph starting on line 589 for a technical discussion).\n\n> I am not sure why their model is interesting.\n\nWe believe the edge-based prediction model that we introduce is interesting for the following reasons:\n\n1) Our model gives much stronger theoretical results compared to vertex predictions. For example in Max Cut, vertex predictions in Cohen-Addad et al. give $\\approx \\epsilon^4$ additive approximation advantage over the best classical approximation whereas edge predictions give $\\approx \\epsilon^2 \\gg \\epsilon^4$ advantage. The difference is much more pronounced for independent set where we can get a constant factor approximation, whereas prior work Braverman et al. can only guarantee a $O(\\sqrt{n})$ factor approximation with vertex predictions. For vertex cover (weighted and unweighted), we can get strictly smaller than a factor of 2 approximation whereas the vertex prediction based algorithm of Antoniadis et al. has an approximation factor depending on the number of predicted false positives and negatives, which can lead to an unbounded approximation ratio. \n\n2) Our results do not require i.i.d. predictions across edges. Rather, 4-wise independence of the predictions suffices (see our Remark 4.6). This means that our algorithms can handle potentially a huge number of correlations among the predictions.\n\n3) Lastly, while our work is the first to introduce edge predictions for augmenting NP-hard problems, we remark that edge based predictions have also been used in other learning-augmented optimization problems (unrelated to NP-complete problems), e.g. [1] for correlation clustering and [2] for metric clustering. \n- KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals. ICLR ‘23\n- Metric Clustering and MST with Strong and Weak Distance Oracles. COLT ‘24.\n\n> You mention previous work on vertex-based predictions but do not provide their approximation factors. Including these would facilitate comparison with your results.\n\nPlease see the first point of our response above. We also note that our submission does contain a thorough discussion on prior work on vertex-based predictions. See Lines 146-164 (right column) for discussion on prior work on vertex-cover, Lines 174-185 (left column) for independent set, and Lines 186-190 for discussion of prior work on max-cut. \n\nOverall, we thank the reviewer again for their feedback. We believe we have addressed the reviewer’s main concern about why our new model is interesting. We are happy to provide additional clarifications and engage further in the discussions if we have missed or misunderstood any crucial points. \n\nMany thanks,\nThe Authors.", "claims_and_evidence": "They provide proof for their claims.", "methods_and_evaluation_criteria": "They provide an evaluation, but only for one of their proposed algorithms. However, this is not a major concern, as the main contribution of the paper lies in its theoretical results.", "theoretical_claims": "I reviewed the proofs in the main part of the paper, but not the appendix.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "Previous works study the case that for each vertex we have one random bit that gives information about the optimal solution. In contrast, this work assigns two bits per edge, providing significantly more information for high-degree vertices.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "I am not sure why their model is interesting. Since the predictions are related to vertices, it does not make sense that each vertex has a separate prediction for each adjacent edge. The prior model, where each vertex had a single prediction bit, seems more realistic to me. Additionally, this model provides excessive information about high-degree vertices, which their algorithm takes advantage of. I find the paper's motivation insufficient in justifying the significance of their model.", "other_comments_or_suggestions": "You mention previous work on vertex-based predictions but do not provide their approximation factors. Including these would facilitate comparison with your results.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oV7VRiCb9L", "reviewer": "Reviewer_si3e", "summary": "The paper studies learning augmented algorithms for hard graph problems. The author introduce a new setting in which the algorithm can count on a prediction algorithm that provides two bits per edge, one per each incident vertex, which are positively correlated to the fact that the vertex satisfies the edge constraint. They show that in this setting algorithms can be designed whose approximation guarantees breaks the hardness barrier (in the absence of the predictions). Moreover they show that this model might be more powerful than the one where one bit per vertex is predicted.\n\n## Update after rebuttal\nI kept my positive score. The rebuttal phase did not bring any additional information to justify a decrease.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and comments. \n\n> a few typos and corrections:\n\nThank you, we have fixed the typos. \n\n> It is not clear how in practical cases one can make available predictions with the desired bounded reliability.\n\n> How do you guarantee the goodness of the prediction? \n\nOur guarantees **already** have worst case guarantees built in, even if the predictions are arbitrarily corrupt, in three ways.\n\n1) Our approximation factors consist of two terms: one coming from the classic bounds without predictions and a term $f(\\epsilon)$ that is the advantage that we have using edge-predictions that are correct with probability $½ + \\epsilon$. (Note $f(\\epsilon)$ depends on the particular problem studied). We recover the original worst-case guarantees by letting $\\epsilon \\rightarrow 0$. This corresponds to predictions that are random noise and have no signal. On the other hand, our approximation factors improve as $\\epsilon$ increases. Thus, our bounds naturally interpolate between the purely noisy case (where our guarantees converge to worst-case bounds) and to the case of large $\\epsilon$ where we provably obtain an advantage over the setting with no predictions.\n\n2) Even if the $\\epsilon$ parameter is not known in practice, we can simply guess over multiple choices of $\\epsilon$, run our algorithm, and simply take the best solution. E.g. in the vertex cover example, we can instantiate our algorithm for different $\\epsilon$ values and take the smallest vertex cover over all choices. This is because the problems we study are in the class NP, so we can compute the quality of the solution in polynomial time. Since for our theoretical bounds we only need to know $\\epsilon$ up to a constant factor, our guess over $\\epsilon$ can be done efficiently. Note that this also handles the reviewer’s other concern about determining $\\epsilon$ in practice.\n\n3) Lastly, we can simply run another approximation algorithm in parallel to our algorithm, e.g. the classic approximation algorithms without predictions, and take the best solution (again this is because the problems are in the class NP so we can compute the quality of the solution returned by both algorithms). This ensures that we can never output something worse than the classic algorithms. \n\n> Can you provide experimental comparison with the other prediction-augmented algorithms proposed in the literature.\n\nFor independent-set (the setting of our experiments) we are only aware of one prior work of Braverman et al. They use a different prediction model (vertex-based predictions) and obtain a substantially worse theoretical approximation factor (their approximation factor can be $\\sqrt{n}$ whereas we get a constant approximation). The authors did not provide an implementation of their algorithm. \n\nNevertheless, we tested their algorithm on the two datasets in our main submission. If we implement their algorithm as it is written in their paper, then their algorithm just converges to the standard greedy algorithm (dotted green line in our Figures). This is because their algorithm first prunes nodes based on a complicated degree condition (see Algorithm 1 in https://arxiv.org/pdf/2407.11364) and then runs the greedy solution on the pruned graph. However, the constants are quite large in the pruning condition so in the two graphs we tested, none of the nodes were pruned (and we suspect this to be the case for most “real world” graphs). Thus, their algorithm performs their step 4 (compute the greedy solution on the remaining un-pruned nodes) on the entire graph. (More precisely, their condition 2 of including all nodes in L with degrees at most $36 \\cdot \\log n$ always includes all nodes in our datasets). Perhaps one can optimize their constants to obtain a more reasonable bound, but we did not pursue this. Given this, we believe their algorithm to be mostly of theoretical interest, but it is an interesting direction for future work to devise a more practical version of their algorithm.", "claims_and_evidence": "The claims are supported by proof of the stated improved bounds.\nMoreover the authors present a moderate experimental analysis for the maximum independent set problem. \nHere, I would have expected also a comparison with the algorithm of Braveman et al.", "methods_and_evaluation_criteria": "Yes. The proofs appear to be sound.", "theoretical_claims": "I checked all the proofs in the body of the paper. I did not verify the appendix.", "experimental_designs_or_analyses": "See the above comment in Claims and Evidence", "relation_to_broader_scientific_literature": "The paper introduces a new setting for prediction-augmented algorithms. While the previously proposed setting was based on one predicted bit per vertex, here more bits, namely one per incident edge, are predicted per each vertex. \nThe authors discuss both the significance and the positive gap in efficecncy between the new setting the previous one.", "essential_references_not_discussed": "I think the treatment of the related literature is comprehensive", "other_strengths_and_weaknesses": "Strenghts: a new model is proposed and its efficacy and imprevements are proved w.r.t. previous model. \nA general approach for the new setting is designed that exploits known algorithms for degree-constrained instances.\nWeaknesses: it is not clear how in practical cases one can make available predictions with the desired  bounded reliability.", "other_comments_or_suggestions": "a few typos and corrections:\n\npage 3, lines 1 and 9, column 2:\n above which --> on which\n\npage 3, line 11, column 2\n many --> may\n\npage 4, line 10 column 1\n Minimum --> Maximum\n\nProof sketch of Theorem 4.1 (equation in display)\nin the left hand side of the inequality: w(S) should be S\nin the right hand side of the inequality, the first term should talk about S_0 not S_1", "questions_for_authors": "How do you guarantee the goodness of the prediction?\nCan you provide experimental comparison with the other prediction-augmented algorithms proposed in the literature, rather than with artificial new prediction algorithms or non-prediction-based algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4zWJPnCZaw", "reviewer": "Reviewer_CEUY", "summary": "This paper introduces a new prediction model that extends the framework of Cohen-Addad et al. (NeurIPS 2024) to improve approximation ratios for NP-hard graph problems, including (weighted and unweighted) Vertex Cover, Set Cover, Max Independent Set, and Max Cut. In their prediction model, each edge is assigned i.i.d. bits that provide $\\epsilon$-accurate information about the variables participating in the edge constraint. For instance, in the Vertex Cover and Max Independent Set problems, each edge has two bits indicating whether its endpoints belong to a fixed optimal solution. Each bit is independently correct with probability $1/2+\\epsilon$, regardless of the other bit or other edges. Using this prediction model, they achieve improved approximation ratios over classical approximation algorithms (without predictions) and learning-augmented approaches based on alternative prediction frameworks. The main algorithmic insight is to leverage predictions for high-degree vertices—where majority voting yields more reliable estimates—and apply a standard approximation algorithm for low-degree vertices.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and comments. \n\n>  report the variance of the results for algorithms\n\nThank you; we will do this in the final version. \n\n\n> It would be interesting to see how the algorithms perform if the predictions are not eps-accurate \n\nThank you for this question. This is a nice future direction to study. However, we note that even if the $\\epsilon$ parameter is not known in practice, we can simply guess over multiple choices of $\\epsilon$, run our algorithm, and simply take the best solution. E.g. in the vertex cover example, we can instantiate our algorithm for different $\\epsilon$ values and take the smallest vertex cover over all choices.", "claims_and_evidence": "All the claims are mathematically proved.", "methods_and_evaluation_criteria": "The paper evaluates the performance of its algorithms using the approximation ratio, which is standard in the literature. Additionally, its learning-augmented framework, though novel, is reasonable.", "theoretical_claims": "I did not check the proofs in the appendices, but the proof sketches in the main body of the paper make sense.", "experimental_designs_or_analyses": "The experimental setup, baselines, datasets, and performance measure are reasonable. However, it would be better to also report the variance of the results for algorithms that use predictions.", "relation_to_broader_scientific_literature": "In Section 3, the authors compare their work with previous classical and learning-augmented algorithms for the studied problems. They also mention hardness results related to these problems. The previous learning-augmented results use different prediction frameworks; I mention two of them here:\n * Antoniadis et al. (2024) studied the Weighted Vertex Cover under a different prediction model that predicts the optimal set of vertices, and achieved an approximation ratio of $1+\\frac{\\eta^+ + \\eta^-}{OPT}$, where $\\eta^+$ and $\\eta^-$ are the total weight of the false positive and false negative edges, respectively. In contrast, this work presents an algorithm with approximation factor $2-\\Omega(\\frac{\\log \\log 1/\\epsilon}{\\log 1/\\epsilon})$.\n * Cohen-Addad et al. (NeurIPS 2024) studied the Max Cut problem under $\\epsilon$-accurate vertex predictions, and achieved an approximation ratio of $\\alpha_{GW}+\\tilde{\\Omega}(\\epsilon^4)$, where $\\alpha_{GW}$ is the Goemans-Williamson constant. In contrast, this work uses $\\epsilon$-accurate edge predictions and achieves an approximation ratio of $\\alpha_{GW}+\\tilde{\\Omega}(\\epsilon^2)$.", "essential_references_not_discussed": "I am not aware of any related works that are essential to understanding the key contributions of the paper but are not currently cited.", "other_strengths_and_weaknesses": "The new prediction model introduced in this paper is interesting, achieves strong results, and improves upon previous results in other models. The proposed algorithms are simple and intuitive, and their ideas may have applications in other related problems. The paper is well-written and easy to follow. In particular, presenting the big picture and the main algorithmic ideas in the introduction was especially helpful.", "other_comments_or_suggestions": "It would be interesting to see how the algorithms perform if the predictions are not $\\epsilon$-accurate but instead come from a machine learning algorithm that does not have access to the current instance.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "INVnMY6LWc", "reviewer": "Reviewer_GWRK", "summary": "This paper addresses NP-hard graph problems by developing learning-enhanced approximation algorithms. The authors identify that existing prediction-based approaches predominantly rely on vertex-level information, which may limit performance improvements. To overcome this limitation, they propose a novel framework incorporating edge prediction mechanisms to enhance approximation algorithms. The core technical contribution involves systematically integrating edge prediction information with classical approximation methods through adaptive thresholding strategies. Experimental validation is conducted on two moderately-sized graphs: Facebook and Congress. Results demonstrate consistent performance improvements across varying ε parameters, compared to baselines.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.\n\n**On datasets and Benchmarks**: \nThe main focus of our paper is on giving rigorous theoretical improvements for classic NP-hard problems. We view our experiments as proof-of-concept, demonstrating that our theoretical ideas are also implementable. (We note that prior work such Cohen-Addad et al. who also studied augmenting NP-hard problems don't have experiments). \n\nWe also provide some intuition for our experimental choices. For independent-set, we believed it is natural to test on social networks since the problem is optimizing for a collection of nodes with no mutual connections. Thus in our paper, we selected two social networks from the popular SNAP library. We picked moderately sized networks since we wanted to validate the quality of the approximation returned by our augmented algorithm by comparing to the exact optimal solution. However, the independent set is NP hard, so computing the exact optimal requires running an expensive integer linear program, which is prohibitive for large graphs (this is exactly why approximation algorithms for NP hard problems are useful!). Note that to use our algorithm, computing the optimum is not necessary; we only do it to compute our algorithm’s exact approximation factor on real world datasets. In practice, this step can be skipped since we already give a mathematical guarantee bounding the approximation factor.\n\nLastly, **we ran a new experiment on a much larger graph** on a subgraph of large social network from SNAP (https://snap.stanford.edu/data/twitch_gamers.html) with ~50k nodes and ~1.1 million edges (we pruned the original graph to make the integer linear program for finding the optimal feasible). As seen in the figure in this anonymous link (https://ibb.co/60N2W8T1), the qualitative behavior remains the same: our learning-based algorithm can outperform the standard greedy approximation algorithm as well as the algorithm that only uses the predictions.\n\n>  does not explicitly address whether the algorithm remains efficient in terms of both time and space complexity when applied to very large graphs.\n\nAll of our algorithms provably run in polynomial time and space so theoretically they are efficient for even very large graphs. This is our main message: by using very noisy predictions, we can get improved approximation algorithms for fundamental optimization problems in polynomial time. Our approximations using predictions overcome existing barriers which without predictions are not possible in polynoial time (assuming P != NP).\n\n>  the paper does not provide a clear explanation of how to determine this ε for graphs of different sizes\n\n> The paper doesn't clearly explain how prediction errors are handled\n\nOur guarantees **already have worst case guarantees built in**, even if the predictions are arbitrarily corrupt, in three ways.\n\n1) Our approximation factors consist of two terms: one coming from the classic bounds without predictions and a term $f(\\epsilon)$ that is the advantage that we have using edge-predictions that are correct with probability $½ + \\epsilon$. (Note $f(\\epsilon)$ depends on the problem). We recover the original worst-case guarantees by letting $\\epsilon \\rightarrow 0$. This corresponds to predictions that are random noise with no signal. On the other hand, our approximation factors improve as $\\epsilon$ increases. Thus, our bounds naturally interpolate between the purely noisy case and to the case of large $\\epsilon$ where we provably obtain an advantage over no predictions.\n\n2) Even if the $\\epsilon$ parameter is not known in practice, we can simply guess over multiple choices of $\\epsilon$, run our algorithm, and take the best solution. E.g. in vertex cover, we can instantiate our algorithm for different $\\epsilon$ values and take the smallest cover over all choices. This is because the problems we study are in NP, so we can compute the quality of the solution in polynomial time. Since for our theoretical bounds we only need to know $\\epsilon$ up to a constant factor, our guess over $\\epsilon$ can be done efficiently. That this also handles the reviewer’s other concern about determining $\\epsilon$ in practice.\n\n3) Lastly, we can also run another approximation algorithm in parallel to our algorithm, e.g. classic approximation algorithms, and take the best solution (this is because the problems are in the class NP so we can compute the quality of the solution returned by both algorithms). This ensures that we can never output something worse than the classic algorithm. \n\nOverall, we thank the reviewer for their feedback. We believe we have addressed the reviewer’s main concerns about how our algorithms scale, as well as how our algorithms handle prediction errors. We are happy to provide additional clarifications and engage further in the discussions if we have misunderstood any crucial points. \n\nMany thanks, The Authors.", "claims_and_evidence": "Basically yes. However, it would be even better if the authors could address the following concerns of mine.", "methods_and_evaluation_criteria": "The benchmark datasets used in the paper do not reflect the essence of the problem. Firstly, according to the authors' description, the two datasets consist of medium-sized graphs, so the proposed algorithm has not been validated on graphs of other sizes. Secondly, the datasets used in the paper have a long time interval between them, and it seems that there are other datasets available in this field. Please provide a reasonable explanation.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "1. This paper only uses two graphs, but it does not explicitly address whether the algorithm remains efficient in terms of both time and space complexity when applied to very large graphs. This point is not clearly discussed.\n\n2. This paper conducts experiments on two moderately-sized graphs, and although the results show that \"for both datasets, we demonstrate that for an appropriate ε, our learning-augmented algorithm achieves the best performance on both graphs,\" it seems that the paper does not provide a clear explanation of how to determine this ε for graphs of different sizes.", "relation_to_broader_scientific_literature": "In the abstract, the authors state that their algorithm builds upon and extends the ε-prediction framework introduced by Cohen‐Addad, d’Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024). In the introduction, they also mention that 'learning-augmented algorithms have recently emerged as a popular paradigm for beyond worst-case analysis via incorporating machine learning into classical algorithm design,' thereby referencing related literature in this research area.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "## Strengths:\n1. This paper introduces a learning-enhanced framework based on edge prediction, which offers a new perspective for improving approximation algorithms for NP-hard graph problems by incorporating predictive information.\n2. This paper provides a detailed theoretical analysis, including a series of lemmas and proofs, such as Lemma A.5 to A.9, which lay a solid theoretical foundation for the algorithm's effectiveness and performance guarantees.\n\n## Weaknesses:\n1. The algorithm relies on a learning-enhanced framework, suggesting its performance depends on the accuracy of the predictions. The paper doesn't clearly explain how prediction errors are handled and whether they might significantly degrade the algorithm’s performance.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "Please answer the two questions in the \"Experimental Designs Or Analyses\" section as well as the question in \"Weaknesses\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission studies learning-augmented approximation algorithms for a variety of classic NP-hard graph problems, including (Weighted) Vertex Cover, Set Cover, Maximum Independent Set, and MaxCut. The key innovation is to use edge-based predictions, where each edge provides bits of (potentially noisy) information about its endpoints’ membership in an optimal solution. The authors demonstrate that this edge-based model enables better approximation factors than are possible under traditional worst-case analyses or prior vertex-based prediction models. They also provide theoretical bounds indicating that even if predictions are arbitrarily inaccurate, their algorithmic approach recovers the standard worst-case approximation guarantees.

Despite one reviewer expressing skepticism about the new prediction model’s practicality, the majority of reviewers find the paper’s theoretical contributions compelling, with two clear accepts and one borderline evaluation. The rebuttal provides a thorough explanation of the edge-based prediction model’s advantages and clarifies strategies for handling prediction errors, underscoring the novelty and strength of the results.

From my (Area Chair) perspective, the paper’s contributions to learning-augmented approximation are significant and of interest. I do not share the concerns with the reviewer regarding the prediction model and, in fact, find the model natural and worth studying.
Decision: Accept (poster)