2026-07-22T21:28:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21017 2024-09-16T06:02:38Z ddc:004 open_access

Learning-Augmented Maximum Independent Set Braverman, Vladimir Dharangutte, Prathamesh Shah, Vihan Wang, Chen Learning-augmented algorithms maximum independent set graph algorithms We study the Maximum Independent Set (MIS) problem on general graphs within the framework of learning-augmented algorithms. The MIS problem is known to be NP-hard and is also NP-hard to approximate to within a factor of n^(1-δ) for any δ > 0. We show that we can break this barrier in the presence of an oracle obtained through predictions from a machine learning model that answers vertex membership queries for a fixed MIS with probability 1/2+ε. In the first setting we consider, the oracle can be queried once per vertex to know if a vertex belongs to a fixed MIS, and the oracle returns the correct answer with probability 1/2 + ε. Under this setting, we show an algorithm that obtains an Õ((√Δ)/ε)-approximation in O(m) time where Δ is the maximum degree of the graph. In the second setting, we allow multiple queries to the oracle for a vertex, each of which is correct with probability 1/2 + ε. For this setting, we show an O(1)-approximation algorithm using O(n/ε²) total queries and Õ(m) runtime. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir Braverman and Prathamesh Dharangutte and Vihan Shah and Chen Wang 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.24 urn:nbn:de:0030-drops-210179 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.24 eng https://creativecommons.org/licenses/by/4.0/legalcode