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 . 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
in expected polynomial time.
2010 AMS Subject Classification:
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.