2014/10/14 by Yinglei Song · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Independent set #Mathematics #Random graph #Combinatorics #Random regular graph #Maximal independent set #Parameterized complexity #Discrete mathematics #Chordal graph #Graph #1-planar graph
paper · doi:10.1080/00207160.2014.976210
openalex publication_date 2014/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, where p is a constant between 0 and 1. We show that a maximum independent set in a random graph that contains n vertices can be computed in expected computation time 2O(log22n). In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in n vertices can be approximated within a ratio of 2n/2log2n in expected polynomial time.