This paper studies the problem of detecting the presence of a small dense community planted in a large Erd\H{o}s-R\'enyi random graph \(\mathcal{G}(N,q)\), where the edge probability within the community exceeds \(q\) by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size \(N\) grows and the graph becomes sparser according to \(q=N^{-\alpha}\), there exists a critical value of \(\alpha = \frac{2}{3}\), below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest \(K\)-subgraph.