The pyramid path-search equality for triangular query budgets

About 15 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.