  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})}$. Using techniques based on enumeration, we
develop an algorithm that can find a largest common subgraph in two random
graphs in $n$ and $m$ vertices ($m \leq n$) in expected computation time
$2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{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
$\frac{2n}{2^{\sqrt{\log_{2}{n}}}}$ in expected polynomial time.
