The task of complete complexity dichotomy is to clearly distinguish between easy and hard
cases of a given problem on a family of subproblems. We consider this task for some …

We consider a problem of searching for an unknown target vertex t in a (possibly edge-
weighted) graph. Each vertex-query points to a vertex v and the response either admits that …

We study the problem of minimizing the weighted average number of queries to identify an
initially unknown object in a poset. We show that for general posets, there cannot be any o …

We consider a problem of searching an element in a partially ordered set (poset). The goal
is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi …

Partial order multiway search (POMS) is a fundamental problem that finds applications in
crowdsourcing, distributed file systems, software testing, and more. This problem involves an …

The Binary Identification Problem for weighted trees asks for the minimum cost strategy
(decision tree) for identifying a vertex in an edge weighted tree via testing edges. Each edge …

We consider the following generalization of the binary search problem. A search strategy is
required to locate an unknown target node $ t $ in a given tree $ T $. Upon querying a node …

In this paper we consider the vertex ranking problem of weighted trees. We show that this
problem is strongly NP-hard. We also give a polynomial-time reduction from the problem of …

We study partial order multiway search (POMS), which is a game between an algorithm A
and an oracle, played on a directed acyclic graph G known to both parties. First, the oracle …

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 …