  We study the trace reconstruction problem for spider graphs. Let $n$ be the
number of nodes of a spider and $d$ be the length of each leg, and suppose that
we are given independent traces of the spider from a deletion channel in which
each non-root node is deleted with probability $q$. This is a natural
generalization of the string trace reconstruction problem in theoretical
computer science, which corresponds to the special case where the spider has
one leg. In the regime where $d\ge \log_{1/q}(n)$, the problem can be reduced
to the vanilla string trace reconstruction problem. We thus study the more
interesting regime $d\le \log_{1/q}(n)$, in which entire legs of the spider are
deleted with non-negligible probability. We describe an algorithm that
reconstructs spiders with high probability using
$\exp\left(\mathcal{O}\left(\frac{(nq^d)^{1/3}}{d^{1/3}}(\log
n)^{2/3}\right)\right)$ traces. Our algorithm works for all deletion
probabilities $q\in(0,1)$.
