  Recently [Bhattacharya et al., STOC 2015] provide the first non-trivial
algorithm for the densest subgraph problem in the streaming model with
additions and deletions to its edges, i.e., for dynamic graph streams. They
present a $(0.5-\epsilon)$-approximation algorithm using $\tilde{O}(n)$ space,
where factors of $\epsilon$ and $\log(n)$ are suppressed in the $\tilde{O}$
notation. However, the update time of this algorithm is large. To remedy this,
they also provide a $(0.25-\epsilon)$-approximation algorithm using
$\tilde{O}(n)$ space with update time $\tilde{O}(1)$.
  In this paper we improve the algorithms by Bhattacharya et al. by providing a
$(1-\epsilon)$-approximation algorithm using $\tilde{O}(n)$ space. Our
algorithm is conceptually simple - it samples $\tilde{O}(n)$ edges uniformly at
random, and finds the densest subgraph on the sampled graph. We also show how
to perform this sampling with update time $\tilde{O}(1)$. In addition to this,
we show that given oracle access to the edge set, we can implement our
algorithm in time $\tilde{O}(n)$ on a graph in the standard RAM model. To the
best of our knowledge this is the fastest $(0.5-\epsilon)$-approximation
algorithm for the densest subgraph problem in the RAM model given such oracle
access.
  Further, we extend our results to a general class of graph optimization
problems that we call heavy subgraph problems. This class contains many
interesting problems such as densest subgraph, directed densest subgraph,
densest bipartite subgraph, $d$-cut and $d$-heavy connected component. Our
result, by characterizing heavy subgraph problems, partially addresses open
problem 13 at the IITK Workshop on Algorithms for Data Streams in 2006
regarding the effects of subsampling in this context.
