We consider two types of searching models, where the goal is to design an adaptive algorithm that locates an unknown vertex in a graph by repeatedly performing queries. In the vertex-query model, each query points to a vertex @math and the response either admits that @math is the target or provides a neighbor of @math on a shortest path from @math to the target. This model has been introduced for trees by Onak and Parys [FOCS 2006] and by Emamjomeh- [STOC 2016] for arbitrary graphs. In the edge-query model, each query chooses an edge and the response reveals which endpoint of the edge is closer to the target, breaking ties arbitrarily. Our goal is to analyze solutions to these problems assuming that some responses may be erroneous. We develop a scheme for tackling such noisy models with the following line of arguments: For each of the two models, we analyze a generic strategy that assumes a fixed number of lies and give a precise bound for its length via an amortized analysis. From this, we derive bounds for both a linearly bounded error rate, where the number of errors in @math queries is bounded by @math for some @math , and a probabilistic model in which each response is incorrect with some probability @math . The bounds for adversarial case turn out to be strong enough for non-adversarial scenarios as well. We obtain thus a much simpler strategy performing fewer vertex-queries than one by Emamjomeh- [STOC 2016]. For edge-queries, not studied before for general graphs, we obtain bounds that are tight up to @math factors in all error models. Applying our graph-theoretic results to the setting of edge-queries for paths, we obtain a number of improvements over existing bounds for searching in a sorted array in the presence of errors, including an exponential improvement for the prefix-bounded model in unbounded domains.
Regarding the problem of searching in graphs without errors, many papers have been devoted to trees, mainly because it is a structure that naturally generalizes paths, which represents the classical binary search (see e.g. @cite_3 for search in a path with non-uniform query times). This query model in case of trees is equivalent to several other problems, including vertex ranking @cite_4 or tree-depth @cite_19 . There exist linear-time algorithms for finding optimal query strategies @cite_13 @cite_38 . A lot of effort has been done to understand the complexity for trees with non-uniform query times. It turns out that the problem becomes hard for trees @cite_14 @cite_31 . Also refer the reader to works on a closely related query game with edge queries @cite_10 @cite_32 @cite_16 @cite_8 @cite_36 . For general graphs, a strategy that always queries a 1-median (the minimizer of the sum of distances over all vertices) has length at most @math @cite_26 .
@cite_38 @cite_14 @cite_4 @cite_26 @cite_8 @cite_36 @cite_10 @cite_32 @cite_3 @cite_19 @cite_31 @cite_16 @cite_13
1991217335 2293258084 2531053806 2107282727
We extend the binary search technique to searching in trees. We consider two models of queries: questions about vertices and questions about edges. We present a general approach to this sort of problem, and apply it to both cases, achieving algorithms constructing optimal decision trees. In the edge query model the problem is identical to the problem of searching in a special class of tree-like posets stated by Ben-Asher, Farchi and Newman [1]. Our upper bound on computation time, O(n^3 ), improves the previous best known O(n^4 log^3 n). In the vertex query model we show how to compute an optimal strategy much faster, in O(n) steps. We also present an almost optimal approximation algorithmfor another class of tree-like (and forest-like) partial orders. Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query e returns the component of T - e containing the vertex sought for, while incurring some known cost c ( e ) . The Tree Search Problem with Non-Uniform Cost is the following: given a tree T on n vertices, each edge having an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case.Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input trees of degree 3 or diameter 6. The best known approximation guarantee was an O ( log ź n log ź log ź log ź n ) -approximation algorithm of (2012) 4.We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an O ( log ź n log ź log ź n ) -approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-hard even when the input tree is a spider of diameter 6, i.e., at most one vertex has degree larger than 2. We start a systematic study of data structures for the nearest colored node problem on trees. Given a tree with colored nodes and weighted edges, we want to answer queries (v,c) asking for the nearest node to node v that has color c. This is a natural generalization of the well-known nearest marked ancestor problem. We give an O(n)-space O(log log n)-query solution and show that this is optimal. We also consider the dynamic case where updates can change a node's color and show that in O(n) space we can support both updates and queries in O(log n) time. We complement this by showing that O(polylog n) update time implies Omega(log n log log n) query time. Finally, we consider the case where updates can change the edges of the tree (link-cut operations). There is a known (top-tree based) solution that requires update time that is roughly linear in the number of colors. We show that this solution is probably optimal by showing that a strictly sublinear update time implies a strictly subcubic time algorithm for the classical all pairs shortest paths problem on a general graph. We also consider versions where the tree is rooted, and the query asks for the nearest ancestor descendant of node v that has color c, and present efficient data structures for both variants in the static and the dynamic setting. Given a simple graph G=(V,E) and a set of sources S ⊆ V, denote for each node ν e V by Lν(∞) the lexicographically ordered list of distance source pairs (d(s,v),s), where s ∈ S. For integers d,k ∈ N∪ ∞ , we consider the source detection, or (S,d,k)-detection task, requiring each node v to learn the first k entries of Lν(∞) (if for all of them d(s,v) ≤ d) or all entries (d(s,v),s) ∈ Lν(∞) satisfying that d(s,v) ≤ d (otherwise). Solutions to this problem provide natural generalizations of concurrent breadth-first search (BFS) tree constructions. For example, the special case of k=∞ requires each source s ∈ S to build a complete BFS tree rooted at s, whereas the special case of d=∞ and S=V requires constructing a partial BFS tree comprising at least k nodes from every node in V. In this work, we give a simple, near-optimal solution for the source detection task in the CONGEST model, where messages contain at most O(log n) bits, running in d+k rounds. We demonstrate its utility for various routing problems, exact and approximate diameter computation, and spanner construction. For those problems, we obtain algorithms in the CONGEST model that are faster and in some cases much simpler than previous solutions.