The pyramid path-search equality for triangular query budgets

From papers

Let Py(n)Py(n) denote the pyramid graph of height nn. For a positive integer kk, let pak(Py(n))pa_k(Py(n)) and sik(Py(n))si_k(Py(n)) denote, respectively, the minimum number of rounds needed for path-search and sink-identification when at most kk queries can be asked in each round. For a positive integer ll, set

sl=1+2++l.s_l=1+2+\ldots+l.

Pyramid path-search conjecture. If sl=1+2++ls_l=1+2+\ldots+l for some ll, then

sisl(Py(n))=pasl(Py(n))=n/l.si_{s_l}(Py(n))=pa_{s_l}(Py(n))=\lceil n/l\rceil.

This extends the fully adaptive equality si1(Py(n))=pa1(Py(n))=nsi_1(Py(n))=pa_1(Py(n))=n to larger query budgets, asserting that both search problems have the same optimal round complexity when the budget is triangular. The supplied text does not indicate whether the assertion has been proved or disproved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dániel Gerbner and Balázs Keszegh, “Path-search in the pyramid and in other graphs”, arXiv:1104.5098 (2011).

Solutions 0

No solutions have been posted yet.