2015/03/10 by Mathias Hauptmann, Hauptmann, Mathias, Marek Karpiński +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Control (math.OC) #cs.DM #cs.DS #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1503.02880
16 pages, 2 figures
arxiv created 2015/03/10 · openalex publication_date 2015/03/10 · arxiv updated 2015/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give the first nonconstant lower bounds for the approximability of the Independent Set Problem on the Power Law Graphs. These bounds are of the form nε in the case when the power law exponent satisfies β<1. In the case when β=1, the lower bound is of the form log (n)ε. The embedding technique used in the proof could also be of independent interest.