  Given a subset of active nodes in a network can we re- construct the cascade
that has generated these observa- tions? This is a problem that has been
studied in the literature, but here we focus in the case that tempo- ral
information is available about the active nodes. In particular, we assume that
in addition to the subset of active nodes we also know their activation time.
We formulate this cascade-reconstruction problem as a variant of a Steiner-tree
problem: we ask to find a tree that spans all reported active nodes while
satisfying temporal-consistency constraints. We present three approximation
algorithms. The best algorithm in terms of quality achieves a
O(\sqrt{k})-approximation guarantee, where k is the number of active nodes,
while the most efficient algorithm has linearithmic running time, making it
scalable to very large graphs. We evaluate our algorithms on real-world
networks with both simulated and real cascades. Our results in- dicate that
utilizing the available temporal information allows for more accurate cascade
reconstruction. Fur- thermore, our objective leads to finding the "backbone" of
the cascade and it gives solutions of high precision.
