Ferdinando Cicalese (Universita degli Studi di Salerno, Italija): Searching in Partially Ordered Structures: Average-case Minimization

Povzetek: We study the problem of minimizing the weighted average number of queries to identify a marked and initially unknown element  in a poset (U, <). A weight function  w : U -> Z+  is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the weighted average number of queries.

We show that for general posets, there cannot be any o(log n)-approximation algorithm unless  NP \subseteq TIME(n^{O(log log n)).

When the Hasse diagram of the partially ordered set has the structure of a tree, the problem is equivalent to the  ``Tree search problem'': in a given rooted tree T = (V, E) a node x has been marked and we want to identify it. In order to locate the marked node, we can use  queries asking for a given node v  whether the marked node x lies in  the subtree rooted at v.

The worst-case scenario where one is  interested in minimizing the maximum number of queries is well understood, and linear time  algorithms are known for finding an optimal search strategy [Onak et al. FOCS'06, Mozes et al. SODA'08] .

Here we prove that for the average-case scenario, the above {\em tree search problem} is NP-complete even  for the class of trees with  diameter at most 4. In addition we prove that  the problem is NP-complete even for the class of trees of maximum degree at most 16.

From the  algorithmic point of view, we show that a  natural greedy algorithm  attains a 2-approximation. Furthermore, for the bounded degree instances, we show that any optimal  strategy (i.e., one that minimizes the expected number of queries) performs at most O( D(T) ( log |V| + log w(T)))  queries in the worst case, where w(T) is the  sum of the likelihoods  of the nodes of T and D(T) is the maximum degree of T. We combine this result with a non-trivial exponential time algorithm to provide an FPTAS for trees with bounded degree.