  Graph connectivity is a fundamental combinatorial optimization problem that
arises in many practical applications, where usually a spanning subgraph of a
network is used for its operation. However, in the real world, links may fail
unexpectedly deeming the networks non-operational, while checking whether a
link is damaged is costly and possibly erroneous. After an event that has
damaged an arbitrary subset of the edges, the network operator must find a
spanning tree of the network using non-damaged edges by making as few checks as
possible.
  Motivated by such questions, we study the problem of finding a spanning tree
in a network, when we only have access to noisy queries of the form "Does edge
e exist?". We design efficient algorithms, even when edges fail adversarially,
for all possible error regimes; 2-sided error (where any answer might be
erroneous), false positives (where "no" answers are always correct) and false
negatives (where "yes" answers are always correct). In the first two regimes we
provide efficient algorithms and give matching lower bounds for general graphs.
In the False Negative case we design efficient algorithms for large interesting
families of graphs (e.g. bounded treewidth, sparse). Using the previous
results, we provide tight algorithms for the practically useful family of
planar graphs in all error regimes.
