An Optimal Algorithm for Partial Order Multiway Search
Shangqi Lu, Wim Martens, Matthias Niewerth, Yufei Tao · ACM SIGMOD Record · 2023
Partial order multiway search (POMS) is an important problem that finds use in crowdsourcing, distributed file systems, software testing, etc. In this problem, a game is played between an algorithm A and an oracle, based on a directed acyclic graph G known to both parties. First, the oracle picks a vertex t in G called the target; then, A aims to figure out which vertex is t by probing reachability. In each probe, A selects a set Q of vertices in G whose size is bounded by a pre-agreed value k, and the oracle then reveals, for each vertex q 2 Q, whether q can reach the target in G. The objective of A is to minimize the number of probes. This article presents an algorithm to solve POMS in O(log1+k n + d k log1+d n) probes, where n is the number of vertices in G, and d is the largest out-degree of the vertices in G. The probing complexity is asymptotically optimal.