  We consider the problem of human-assisted graph search: given a directed
acyclic graph with some (unknown) target node(s), we consider the problem of
finding the target node(s) by asking an omniscient human questions of the form
"Is there a target node that is reachable from the current node?". This general
problem has applications in many domains that can utilize human intelligence,
including curation of hierarchies, debugging workflows, image segmentation and
categorization, interactive search and filter synthesis. To our knowledge, this
work provides the first formal algorithmic study of the optimization of human
computation for this problem. We study various dimensions of the problem space,
providing algorithms and complexity results. Our framework and algorithms can
be used in the design of an optimizer for crowd-sourcing platforms such as
Mechanical Turk.
