Search for the end of a path in the d-dimensional grid and in other graphs

Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi +2

We consider the worst-case query complexity of some variants of certain \cl{PPAD}-complete search problems. Suppose we are given a graph $G$ and a vertex $s\in V(G)$. We denote th…