On the independent set problem in random graphs

Abstract

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 $2^{O({\log }_2^{2}n)}$. 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/2^{\sqrt{{\log }_{2}n}}$ in expected polynomial time.

Keywords:

• independent set
• random graphs
• exact algorithm
• parameterized algorithm
• algorithm

2010 AMS Subject Classification:

• 05C85

Acknowledgments

The majority of this work is done while the author was working in the Department of Mathematics and Computer Science at University of Maryland Eastern Shore, USA. This work is partially supported by the University Research Funding at Jiangsu University of Science and Technology, China, under the funding number 635301202.