Approximating independent sets in sparse graphs

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)


We consider the maximum independent set problem on sparse graphs with maximum degree d. The best known result for the problem is an SDP based O(d log log d/log d) approximation due to Halperin. It is also known that no o(d/ log2 d) approximation exists assuming the Unique Games Conjecture. We show the following two results: (i) The natural LP formulation for the problem strengthened by O(log4(d)) levels of the mixed-hierarchy has an integrality gap of Õ(d/log2 d), where Õ(·) ignores some log log d factors. However, our proof is non-constructive, in particular it uses an entropy based approach due to Shearer, and does not give a Õ(d/log2d) approximation algorithm with sub-exponential running time. (ii) We give an O(d/log d) approximation based on polylog(d)-levels of the mixed hierarchy that runs in nO(1) exp(logO(1) d) time, improving upon Halperin's bound by a modest log log d factor. Our algorithm is based on combining Halperin's approach together with an idea used by Ajtai, Erdös, Komlós and Szemerédi to show that Kr-free, degree-d graphs have independent sets of size Or(n log log d/d). Read More:
Originele taal-2Engels
TitelTwenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15, San Diego CA, USA, January 4-6, 2015)
Plaats van productiePhiladelphia
UitgeverijSociety for Industrial and Applied Mathematics (SIAM)
ISBN van geprinte versie978-1-61197-374-7
StatusGepubliceerd - 2015
Evenement26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) - Westin San Diego Gaslamp Quarter, San Diego, Verenigde Staten van Amerika
Duur: 4 jan 20156 jan 2015
Congresnummer: 26


Congres26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)
Verkorte titelSODA '15
LandVerenigde Staten van Amerika
StadSan Diego
AnderTwenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Approximating independent sets in sparse graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit