The trace reconstruction problem for spider graphs

Abstract

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{(n{q}^d{)}^{1/3}}{d^{1/3}}(\log n{)}^{2/3}\right)\right)$ traces. Our algorithm works for all deletion probabilities $q\in (0,1)$.

arXiv comment17 pages, 3 figures