The well known binary search method can be described as the process of identifying some marked node from a line graph T by successively querying edges. An edge query e asks in which of the two subpaths induced by T ∖ e the marked node lies. This procedure can be naturally generalized to the case where T = (V,E) is a tree instead of a line. The problem of determining a tree search strategy minimizing the number of queries in the worst case is solvable in linear time [Onak et al. FOCS’06, Mozes et al. SODA’08].Here we study the average-case problem, where the objective function is the weighted average number of queries to find a node An involved analysis shows that the problem is -complete even for the class of trees with bounded diameter, or bounded degree.We also show that any optimal strategy (i.e., one that minimizes the expected number of queries) performs at most O( Δ(T) ( log|V| + logw(T))) queries in the worst case, where w(T) is the sum of the node weights and Δ(T) is the maximum degree of T. This structural property is then combined with a non-trivial exponential time algorithm to provide an FPTAS for the bounded degree case.

On the Complexity of Searching in Trees: Average-Case Minimization

Cicalese, Ferdinando
;
2010-01-01

Abstract

The well known binary search method can be described as the process of identifying some marked node from a line graph T by successively querying edges. An edge query e asks in which of the two subpaths induced by T ∖ e the marked node lies. This procedure can be naturally generalized to the case where T = (V,E) is a tree instead of a line. The problem of determining a tree search strategy minimizing the number of queries in the worst case is solvable in linear time [Onak et al. FOCS’06, Mozes et al. SODA’08].Here we study the average-case problem, where the objective function is the weighted average number of queries to find a node An involved analysis shows that the problem is -complete even for the class of trees with bounded diameter, or bounded degree.We also show that any optimal strategy (i.e., one that minimizes the expected number of queries) performs at most O( Δ(T) ( log|V| + logw(T))) queries in the worst case, where w(T) is the sum of the node weights and Δ(T) is the maximum degree of T. This structural property is then combined with a non-trivial exponential time algorithm to provide an FPTAS for the bounded degree case.
2010
9783642141645
Average-case; Binary search; Bounded degree; Optimization
File in questo prodotto:
File Dimensione Formato  
ICALP2010.pdf

solo utenti autorizzati

Tipologia: Documento in Pre-print
Licenza: Accesso ristretto
Dimensione 238.29 kB
Formato Adobe PDF
238.29 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/931710
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 7
social impact