  In this paper, we study the {\sc Dominating Set} problem in random graphs. In
a random graph, each pair of vertices are joined by an edge with a probability
of $p$, where $p$ is a positive constant less than $1$. We show that, given a
random graph in $n$ vertices, a minimum dominating set in the graph can be
computed in expected $2^{O(\log_{2}^{2}{n})}$ time. For the parameterized
dominating set problem, we show that it cannot be solved in expected
$O(f(k)n^{c})$ time unless the minimum dominating set problem can be
approximated within a ratio of $o(\log_{2}n)$ in expected polynomial time,
where $f(k)$ is a function of the parameter $k$ and $c$ is a constant
independent of $n$ and $k$. In addition, we show that the parameterized
dominating set problem can be solved in expected $O(f(k)n^{c})$ time when the
probability $p$ depends on $n$ and equals to $\frac{1}{g(n)}$, where $g(n)< n$
is a monotonously increasing function of $n$ and its value approaches infinity
when $n$ approaches infinity.
