\section{Introduction and Preliminaries}\label{sec:section1}

Statistical convergence is a generalization of the ordinary convergence of a real or complex sequence. It was introduced by Steinhaus in \cite{St}. Maddox discussed the statistical convergence in more general abstract spaces such as locally convex spaces in \cite{M}. K\"{u}\c{c}\"{u}kaslan and Y\i lmazt\"{u}rk introduced and investigated the deferred statistical convergence in \cite{KY}. It is enough to mention the theory of statistical convergence (cf. \cite{Agnew,Fast,Fridy,KDD,M}). On the other hand, Riesz space (or, vector lattice) is another concept of functional analysis that was introduced by Riesz \cite{Riez}. Then, many authors developed the subject. Riesz space is an ordered vector space that has many applications in measure theory, Banach space, operator theory, and applications in economics (cf. \cite{AB,ABPO,AAydn2,LZ,Za}). The present paper aims to combine the concepts of deferred statistical convergence of real sequences and order convergence in Riesz spaces.

A real-valued vector space $E$ with an order relation is said to be {\em ordered vector space} if, for each $x,y\in E$ with $x\leq y$, we have $x+z\leq y+z$ and $\alpha x\leq\alpha y$ for all $z\in E$ and $\alpha \in \mathbb{R}_+$. An ordered vector space $E$ is called {\em Riesz space} or {\em vector lattice} if, for any two vectors $x,y\in E$, the infimum and the supremum
$$
x\wedge y=\inf\{x,y\} \ \ \text{and} \ \ x\vee y=\sup\{x,y\}
$$
exist in $E$, respectively. For an element $x$ in a vector lattice $E$, {\em the positive part}, {\em the negative part}, and {\em module} of $x$ are respectively defined as follows:
$$
x^+:=x\vee0, \ \ \ x^-:=(-x)\vee0\ \ and \ \ |x|:=x\vee (-x).
$$
Thus, in the present paper, the vertical bar $|\cdot|$ of elements in vector lattices will stand for the module of the given elements. A subset $A$ of a vector lattice $E$ is called \textit{solid} if, for each $x\in A$ and $y\in E$,  $|y|\leq|x|$ implies $y\in A$. A solid vector subspace of a vector lattice is referred to as an \textit{ideal}. A vector lattice is called {\em $\sigma$-order complete} if every nonempty bounded above countable subset has a supremum (or, equivalently, whenever every nonempty bounded below countable subset has an infimum) (cf. \cite{AB}).

A sequence $(x_n)$ in a Riesz space $E$ is said to be increasing whenever $x_1 \leq x_2\leq\cdots$ and is decreasing if $x_1 \geq x_2\geq \cdots$ holds. Then, we denote them by $x_n\uparrow$ and $x_n\downarrow$, respectively. Moreover, if $x_n\uparrow$ and $\sup x_n=x$, then we write $x_n\uparrow x$. Similarly, if $x_n\downarrow$ and $\inf x_n=x$, then we write $x_n\downarrow x$. Then, we call that $(x_n)$ is increasing or decreasing as monotonic. On the other hand, order convergence is crucial for this paper, and so, we continue with its definition.
\begin{definition}\label{def of order and un-order conv}
Let $(x_n)$ be a sequence in a vector lattice $E$. Then, it is called {\em order convergent} to $x\in E$ if there exists another sequence $y_n\downarrow 0$ (i.e., $\inf y_n=0$ and $y_n\downarrow$) such that $|x_n-x|\le y_n$ holds for all $n\in \mathbb{N}$, and abbreviated it as $x_n\co x$.
\end{definition}

For the definition of statistical convergence, the important point is the natural density of subsets of natural numbers. Recall that the \emph{density of} a subset $K$ of $\mathbb{N}$ is the limit $\lim_{n\rightarrow \infty}\frac{1}{n}\left\vert\left\{k\leq n:k\in K\right\}\right\vert$  whenever this unique limit exists, and it is mostly abbreviated by $\delta(K)$, where $\left\vert\left\{k\leq n:k\in K\right\}\right\vert$ is the cardinality of $K$, and it does not exceed $n$. A sequence $(x_n)$ of real numbers is called {\em statistical convergent} to a real number $l$ if, for every $\varepsilon>0$, we have
$$
\lim\limits_{n\to\infty}\frac{1}{n}\big\lvert\{k:n\geq k, \ |x_n-l|>\varepsilon\}\big\rvert=0.
$$

Now, consider a sequence $x:=(x_k)$ and take the sequences $(p_n)$ and $(q_n)$ of non-negative integers such that $p_n<q_n$ for each $n$ and $q_n$ divergent to infinity. Then, define a new sequence
$$
(D_{p,q}x)_n:=\frac{1}{q_n-p_n}\sum_{k=p_n+1}^{q_n}x_k,
$$
for each $n\in\mathbb{N}$. The sequence $(D_{p,q}x)_n$ is called the {\em deferred Ces\'{a}ro mean} as a generalization of Ces\'{a}ro mean of real (or complex) valued sequence; see \cite{Agnew}. On the other hand, $x$ is said to be {\em strong $D_{p,q}$-convergent} to $l$ if the following limit exists
$$
\lim\limits_{n\to\infty}\frac{1}{q_n-p_n}\sum_{k=p_n+1}^{q_n}|x_k-l|=0.
$$
Then, we abbreviate it as $x_k\xrightarrow{D[p,q]}l$. In this article, unless otherwise, when we mention $p$ and $q$ sequences, they always hold the above properties, and also, these properties are said to be {\em the deferred property}.

A sequence $x:=(x_k)$ is called {\em deferred statistical convergent} to $l\in\mathbb{R}$ whenever, for all $\varepsilon>0$, we have
$$
\lim\limits_{n\to\infty}\frac{1}{q_n-p_n}\big|\{p_n<k\leq q_n:|x_k-l|\geq\varepsilon\}\big|=0
$$
holds; see \cite{KY}. In this case, we write $x_k\xrightarrow{DS[p,q]}l$.

A characterization of statistical convergence on vector lattices was introduced by Ercan in \cite{ZE}, and also, some kinds of statistical convergence in Riesz spaces were introduced and studied by Ayd\i n in \cite{AAydn1,AAydn3,AAydn4,AE}.
\begin{definition}
Let $(x_n)$ be a sequence in a Riesz space $E$. Then, $(x_n)$ is called
\begin{enumerate}
\item[-] {\em statistical order decreasing} to $0$ if there exists a set $K=\{k_1<k_2<\cdots\}\subset\mathbb{N}$ with $\delta(K)=1$ such that $(x_{k_n})$ is decreasing and $\inf\limits_{n\in K}(x_{k_n})=0$, i.e., $(x_{k_n})_{k_n\in K}\downarrow 0$, and it is abbreviated as $x_n\sd 0$;

\item[-] {\em statistical order convergent} to $x\in E$ if there exists a sequence $q_n\sd0$ with an index set $K=\{k_1<k_2<\cdots\}\subset\mathbb{N}$ such that $\delta(K)=1$ and
$$
|x_{k_n}-x|\leq q_{k_n}
$$
for every $k_n\in K$, and so, we write $x_n\soc x$.
\end{enumerate}
\end{definition}
It is clear that every order convergent sequence is statistical order convergent to the same point.
\section{Deferred statistical decreasing}
Tripathy \cite{Trip} introduced the statistical monotonicity for real sequences, and also, statistically monotone sequences in Riesz spaces were investigated. We extend it to deferred statistical decreasing in Riesz spaces.
\begin{definition}\label{first def.}
Let $(p_n)$ and $(q_n)$ be sequences of nonnegative integers satisfying the deferred property. Then, a sequence $(z_n)$ in a Riesz space $E$ is called {\em deferred statistical order decreasing} to $0$ if there exists a set $K\subseteq\mathbb{N}$ such that the deferred density of $K$
$$
\delta_{p,q}(K):=\lim\limits_{n\to\infty}\frac{1}{q_n-p_n}\big|\{p_n< k\leq q_n:k\in K\}\big|=1
$$
and $(z_{k_n})_{k_n\in K}\downarrow0$ holds on $K$. Then, we abbreviate it as $z_n\downarrow^{D_{st_o}}_{p,q}0$.
\end{definition}

\begin{remark}\label{remark1} \
\begin{enumerate}[(i)]
\item If $q(n)=n$ and $p(n)=0$, then Definition \ref{first def.} coincides with the definition of statistical order decreasing.

\item If $(z_n)$ is monotone decreasing to zero, then it is deferred statistical order decreasing to zero. But, the converse does not need to be true in general. To see this, consider the Euclidean space $\mathbb{R}^2$ with the coordinatewise ordering and the sequences $q(n)=n$ and $p(n)=0$ and $(z_n)$ denoted by
$$
z_n:=
\begin{cases}
(0,n^2) & \text{if} \ n=k^3 \\
(0,\frac{1}{n^2}) & \text{if} \ n\neq k^3
\end{cases},
$$
where $k\in\mathbb{N}$. Hence, we get $z_n\downarrow^{D_{st_o}}_{p,q} (0,0)$. But, observe that the whole sequence $(z_n)$ is not monotonic.

\item A deferred statistical order decreasing to zero sequence may contain a subsequence of decreasing or incomparable elements of $E$ but the index set of such a subsequence has deferred density zero.

\item In Riesz spaces, it is well known that $z_n\downarrow0$ implies $z_{k_n}\downarrow 0$ for every subsequence $(z_{k_n})$ of $(z_n)$. However, this may
not hold in the setting of deferred statistical monotone decreasing sequences. For example, take the sequences in the $(ii)$ with the subsequence $(z_{k_n})$, where $k_n=j^3$ for some $j\in\mathbb{N}$, does not have a supremum.
\end{enumerate}
\end{remark}

In the general case, the example in Remark \ref{remark1}$(iv)$ shows that a subsequence of deferred statistical monotone decreasing sequence need not be deferred statistical monotone decreasing. But, we give a positive result in the following theorem.
\begin{theorem}
Let $(z_n)$ be a sequence in a Riesz space $E$. If $z_n\downarrow^{D_{st_o}}_{p,q}0$, then any subsequence $(z_{k_n})$ of $(z_n)$ with index set $\delta_{p,q}(K)=1$ such that $(z_{k_n})$ is decreasing on $K$ is deferred statistical order decreasing to $0$.
\end{theorem}

\begin{proof}
Suppose that $z_n\downarrow^{D_{st_o}}_{p,q}0$ holds in $E$. Then, there exists a set $K\subset\mathbb{N}$ such that $\delta_{p,q}(K)=1$ and $(z_{k_n})_{k_n\in K}\downarrow0$ on $K$. Let us consider any arbitrary index set $M\subseteq\mathbb{N}$ such that $K\neq M$, $\delta_{p,q}(M)=1$ and $(z_n)$ is decreasing on $M$. It can be observed that if there is not such a set $M$, then the poof is complete. It follows from $z_{k_n}\downarrow0$ that $0\leq z_{k_n}$ for all $k_n\in K$. Also, we have $\delta_{p,q}(K\cap M)=1$. Thus, for some $k_m\in K$ and $m_n\in M$, we have $k_n=m_n$. Hence, we have $z_{m_1}\geq z_{m_2}\geq\cdots\geq z_{m_n}=z_{k_n}\geq 0$. We can find infinitely many of such pair of indices. By continuing this way, we obtain $z_{m_n}\geq 0$ for every $m_n\in M$, i.e., zero is a lower bound of $(z_{m_n})$. Take another lower bound $u$ of $(z_{m_n})$. Therefore, we have $u\leq z_{m_n}$ for every $m_n\in M$. Then, we can find some $z_{n_{k_t}}$ such that $z_{n_{k_t}}=z_{m_k}\geq u$ for some $m_k\in M$. By following this way, we can construct a subsequence $(z_{n_{k_1}},z_{n_{k_2}},\cdots)$ of $(z_{k_n})$ such that $u$ is a lower bound of $(z_{n_{k_t}})$ for $t\in \mathbb{N}$. It follows from $z_{k_n}\downarrow 0$ that the infimum of every subsequence of $(z_{k_n})$ is zero. Hence, we get
$u=0$. Therefore, we get the desired result, $z_{m_n}\downarrow^{D_{st_o}}_{p,q}0$.
\end{proof}

In the next results without proof, we give the linear property of deferred statistical order decreasing sequences.
\begin{proposition}\label{uo-conv implies stuo-conv.}
Let $x_n\downarrow^{D_{st_o}}_{p,q}0$ and $y_n\downarrow^{D_{st_o}}_{p,q}0$ be a sequence in a Riesz space $E$ and $\lambda\in\mathbb{R}$. Then, we have
\begin{enumerate}
\item[(i)] $(x_n+y_n)\downarrow^{D_{st_o}}_{p,q}0$;
\item[(ii)] $\lambda x_n\downarrow^{D_{st_o}}_{p,q}0$.
\end{enumerate}
\end{proposition}

\section{Deferred statistical order convergence}

\begin{definition}\label{main def}
Let $p$ and $q$ be sequences of positive integers satisfying the deferred property. Then, a sequence $(x_n)$ in a Riesz space $E$ is called {\em deferred statistical order convergent} to $x$ if there exists a sequence $z_n\downarrow^{D_{st_o}}0$ with an index set $K\subseteq\mathbb{N}$ such that $\delta_{p,q}(K)=1$ and
$$
|x_{k_n}-x|\leq z_{k_n}
$$
holds for all $k_n\in K$. Then, we write $x_n\dc x$.
\end{definition}

\begin{remark}
It can be seen that, in the case of $x_n\dc x$, we have
$$
\delta_{p,q}(\{n\in\mathbb{N}:|x_n-x|\nleq z_n\})=0.
$$
\end{remark}

\begin{remark}
It can be observed that the deferred statistical order convergence of the sequence $(x_n)$ in Definition \ref{main def} with sequence $(z_n)$ to $x$ implies that $x_{k_n}\dc x$ with the same sequence $(z_n)$. The converse is also true, i.e., if there exists a subsequence $(x_{k_n})\dc x$ of a sequence $(x_n)$ with a sequence $z_n\downarrow^{D_{st_o}}0$, then $x_n\dc x$ with the same sequence $(z_n)$.
\end{remark}

It is clear that deferred statistical order decreasing sequence is deferred statistical order convergent. But, the converse does not hold in general.

\begin{remark}\label{order and deferred}
Let $q(n)=n$ and $p(n)=0$. Then, we have the following observations:
\begin{enumerate}
\item[(i)] an order convergent sequence is deferred statistical order convergent to its order limit;

\item[(ii)] the statistical order convergence and deferred statistical order convergence coincide;
\end{enumerate}
\end{remark}

One can observe that a subsequence of a deferred statistical order convergent sequence need not be deferred statistical order convergent.

\begin{proposition}
Let $(x_n)$ be a sequence in a Riesz space $E$. Then, $x_n\dc x$ holds if and only if there exists another sequence $(y_n)$ in $E$ such that $\delta_{p,q}(\{n\in\mathbb{N}:x_n=y_n\})=1$ and $y_n\dc x$.
\end{proposition}

\begin{proof}
Suppose that there exists a sequence $(y_n)$ in $E$ such that $\delta_{p,q}(\{n\in\mathbb{N}:x_n=y_n\})=1$ and $y_n\dc x$. Then, there is another sequence $z_n\downarrow^{D_{st_o}}0$ in $E$ with $\delta_{p,q}(K)=1$ such that
$|x_{k_n}-x|\leq z_{k_n}$ for each $k_n\in K$. Thus, it follows from the including
$$
\{p_n+1\leq m\leq q_n:|x_m-x|\nleq z_m\}\subseteq \{p_n+1\leq m\leq q_n:x_m\neq y_m\}
$$
$$
\cup \{p_n+1\leq m\leq q_n:|y_m-x|\nleq z_m\}
$$
that we have
$$\lim\limits_{n\to\infty}\frac{1}{q_n-p_n}|\{p_n+1\leq m\leq q_n:|x_m-x|\nleq z_m\}|
$$
$$
\leq \lim\limits_{n\to\infty}\frac{1}{q_n-p_n}|\{p_n+1\leq m\leq q_n:x_m\neq y_m\}|
$$
because of $\delta_{p,q}(\{p_n+1\leq m\leq q_n:|y_m-x|\nleq z_m\})=0$. Thus, we obtain
$$
\lim\limits_{n\to\infty}\frac{1}{q_n-p_n}|\{p_n+1\leq m\leq q_n:|x_m-x|\nleq z_m\}|=0.
$$
Therefore, we get the desired result, $x_n\dc x$. The other part of proof is obvious, and so, we omit it.
\end{proof}

\begin{proposition}\label{linear and unit}
The deferred statistical order limit is linear and uniquely determined.
\end{proposition}

\begin{proof}
Assume that $x_n\dc x$ and $x_n\dc y$ hold in a Riesz space $E$. Then, there are sequences $z_n\downarrow^{D_{st_o}}0$ with $\delta_{p,q}(K)=1$ and $t_n\downarrow^{D_{st_o}}0$ with $\delta_{p,q}(M)=1$ such that $|x_{k_n}-x|\leq z_{k_n}$ and $|x_{m_n}-y|\leq t_{m_n}$ for all $k_n\in K$ and $m_n\in M$. Thus, it follows that
$$
|x-y|\leq |x-x_{j_n}|+|x_{j_n}-y|\leq z_{j_n}+t_{j_n}
$$
for every $j_n\in J:=K\cap M$. By using $(z_{j_n}+t_{j_n})_{j_n\in J}\downarrow0$, we obtain that $ |x-y|=0$. Thus, we get the equality of $x$ and $y$.

Now, for the linearity of the deferred statistical order limit, take sequences $x_n\dc x$ and $y_n\dc y$ in a Riesz space $E$. Then, there are sequences $z_n\downarrow^{D_{st_o}}0$ and $t_n\downarrow^{D_{st_o}}0$ such that $\delta_{p,q}(\{n\in \mathbb{N}:|x_n-x|\nleq z_n\})=0$ and $\delta_{p,q}(\{n\in \mathbb{N}:|y_n-y|\nleq t_n\})=0$. It follows from the triangular inequality in Riesz spaces that
$$
\{n\in \mathbb{N}:|(x_n+y_n)-(x+y)|\nleq z_n+t_n\}\subseteq \{n\in \mathbb{N}:|x_n-x|\nleq z_n\}
$$
$$
\cup\{n\in \mathbb{N}:|y_n-y|\nleq t_n\}.
$$
Therefore, we obtain $\delta_{p,q}(\{n\in \mathbb{N}:|(x_n+y_n)-(x+y)|\nleq z_n+t_n\})=0$, i.e., we obtain $x_n+y_n\dc x+y$.
\end{proof}

In the following result, we observe some relations between deferred statistical order convergence and lattice properties.
\begin{theorem}
Let $x_n\dc x$ and $y_n\dc y$ in a Riesz space $E$. Then, we have the following statement:
\begin{enumerate}[(i)]
\item $x_n\vee y_n\dc x\vee y$;
\item $x_n\wedge y_n\dc x\wedge y$;
\item $x_n^+\dc x^+$;
\item $x_n^-\dc x^-$;
\item $|x_n|\dc |x|$.
\end{enumerate}
\end{theorem}

\begin{proof}
It is enough to show the first statement because the other case can be obtained by applying \cite[Thm.1.7]{ABPO} and Proposition \ref{linear and unit}. Now, from $x_n\dc x$ and $y_n\dc y$, we have sequences $z_n\downarrow^{D_{st_o}}0$ and $t_n\downarrow^{D_{st_o}}0$ with indexes sets $\delta_{p,q}(K)=\delta_{p,q}(M)=1$ such that $|x_{k_n}-x|\leq z_{k_n}$ and $|y_{m_n}-y|\leq t_{m_n}$ hold for all $k_n\in K$ and $m_n\in M$. On the other hand, by applying \cite[Thm.1.9]{ABPO} and by taking $J:=N\cap M$, we get
$$
\lvert x_{j_n}\vee y_{j_n}-x\vee y\rvert\leq \lvert x_{j_n}-x\rvert+\lvert y_{j_n}-y\rvert\leq z_{j_n}+t_{j_n}
$$
for every $j_n\in J$. Hence, we obtain
$$
\delta_{p,q}(\{n\in \mathbb{N}:\lvert x_{j_n}\vee y_{j_n}-x\vee y\rvert\nleq z_{j_n}+t_{j_n}\})=0.
$$
Therefore, we get the desired result, $x_n\vee y_n\dc x\vee y$.
\end{proof}

\begin{corollary}\label{corollary}
The positive cone $E_+=\{x\in E:0\leq x\}$ of a Riesz space $E$ is closed under the deferred statistical order convergence.
\end{corollary}

\begin{proposition}
If $x_n\dc x$, $y_n\dc y$ and $x_n\ge y_n$ satisfy for every $n\in\mathbb{N}$ in a Riesz space, then $x\ge y$ holds.
\end{proposition}

\begin{proof}
Assume that $y_n\leq x_n$ holds for each $n\in\mathbb{N}$. Then, we have $0\leq x_n-y_n \in E_+$ for each $n\in\mathbb{N}$. It follows from Corollary \ref{corollary} that $x_n-y_n\dc x-y\in E_+$ because of $(x_n-y_n)\in E_+$. Thus, we get $x-y\geq 0$, i.e., $x\geq y$.
\end{proof}

\begin{theorem}\label{motone and st implies order}
If $(x_n)$ is a monotone and deferred statistical order convergent in a Riesz space, then it is order convergent.
\end{theorem}

\begin{proof}
Suppose that $(x_n)\downarrow$ and $x_n\dc x$ in a Riesz space $E$. Fix any $k\in\mathbb{N}$. Then, we have $x_k-x_n\geq 0$ for all $n\geq k$. It follows that $x_k-x_n\dc x_k-x\geq 0$, i.e., $x_k\geq x$. Thus, $x$ is an lower bound of $(x_n)$ because $k$ is arbitrary. Choose another lower bound $z$ of $(x_n)$. Hence, we have $x_n-z\dc x-z\geq 0$, i.e., $x\geq z$. Therefore we get the desired result, $x_n\downarrow x$.
\end{proof}

\begin{remark}\label{ideal and vector lattice}
Let $A$ be an ideal in a vector lattice $E$ and $(a_n)$ be a sequence in $A$. One can observe that if $a_n\co 0$ in $A$, then $a_n\co 0$ in $E$. Hence, it is clear that $a_n\downarrow^{D_{st_o}} 0$ in $A$ implies $a_n\downarrow^{D_{st_o}} 0$ in $E$. For the converse, if $a_n\co 0$ in $E$ and order bounded, then $a_n\co 0$ in $A$, and so, $a_n\downarrow^{D_{st_o}} 0$ in $E$ implies $a_n\downarrow^{D_{st_o}} 0$ in $A$ for order bounded sequences.
\end{remark}

Thanks to Remark \ref{ideal and vector lattice}, we give the following two results.
\begin{theorem}
Let $A$ be an ideal in an $\sigma$-order complete vector lattice and $(x_n)$ be a sequence in $A$. Then, $x_n\dc 0$ in $A$ if and only if $x_n\dc 0$ in $E$.
\end{theorem}

\begin{proof}
Assume that $x_n\dc 0$ in $A$. Then, there exists a sequence $z_n\downarrow^{D_{st_o}}0$ in $A$ with index set $\delta_{p,q}(K)=1$ such that $|x_{k_n}|\leq z_{k_n}$ for all $k_n\in K$. Now, by using Remark \ref{ideal and vector lattice}, it follows from $(z_{k_n})_{k_n\in K}\downarrow0$ in $A$ that $(z_{k_n})_{k_n\in K}\downarrow0$ in $E$, i.e., we get $z_n\downarrow^{D_{st_o}}0$ in $E$ Therefore, we have $x_n\dc 0$ in $E$.

Conversely, assume $x_n\dc0$ in $E$. Then, there is a sequence $z_n\downarrow^{D_{st_o}}0$ in $E$ with index set $\delta_{p,q}(K)=1$ such that $|x_{k_n}|\leq z_{k_n}$ for all $k_n\in K$. Thus, Remark \ref{ideal and vector lattice} implies that $z_n\downarrow^{D_{st_o}}0$ in $A$. Therefore, we get $x_n\dc 0$ in $A$.
\end{proof}

The following result is similar to \cite[Thm.3.1.]{KDD}.
\begin{theorem}
Let $(x_n)$ be a sequence in a Riesz space $E$ and $(x_{k_n})_{k_n\in K}$ be a subsequence of $(x_n)$. If the limit
$$
\lim\inf\limits_{n\to\infty}\frac{1}{q_n-p_n}\big|\{p_n<k_n\leq q_n:k_n\in K\}\big|>0
$$
holds and $x_n\dc x$ for some sequences $p$ and $q$ satisfying the deferred property, then $x_{k_n}\dc x$.
\end{theorem}

\begin{proof}
Assume that $x_n\dc x$ satisfies in $E$. Then, there is a sequence $z_n\downarrow^{D_{st_o}}0$ in $E$ such that $\delta_{p,q}(\{n\in\mathbb{N}:|x_n-x|\nleq z_n\})=0$. It can be seen that
$$
\{p_n<k_n\leq q_n:k_n\in K,\ |x_{k_n}-x|\nleq z_n\}\subseteq \{p_n<n\leq q_n:|x_n-x|\nleq z_n\}.
$$
Thus, by taking $H_n:=\{p_n<k_n\leq q_n:k_n\in K\}$ for all $n$, we have
$$
\frac{1}{|H_n|}\big|\{p_n<k_n\leq q_n:k_n\in K,\ |x_{k_n}-x|\nleq z_n\}\big|
$$
$$
\leq\frac{1}{|H_n|}\{p_n<n\leq q_n:|x_n-x|\nleq z_n\}.
$$
Therefore, it is enough to show $\lim\sup\limits_{n\to\infty}\frac{1}{|H_n|}\big|\{p_n<n\leq q_n:|x_n-x|\nleq z_n\}\big|=0$ for proving the convergence $x_{k_n}\dc x$. We observe the following inequality
$$
\lim\inf\limits_{n\to\infty}\frac{|H_n|}{q_n-p_n}\lim\sup\limits_{n\to\infty}\frac{|\{p_n<n\leq q_n:|x_n-x|\nleq z_n\}|}{|H_n|}
$$
$$
\leq \lim\sup\limits_{n\to\infty}\frac{|\{p_n<n\leq q_n:|x_n-x|\nleq z_n\}|}{q_n-p_n}.
$$
Therefore, we have
$$
\lim\sup\limits_{n\to\infty}\frac{1}{|H_n|}\big|\{p_n<n\leq q_n:|x_n-x|\nleq z_n\}\big|=0
$$
because of $x_n\dc x$. Thus, we obtain the desired result.
\end{proof}

In Remark \ref{order and deferred}, we give a relation between statistical  order and deferred statistical order convergences by taking $q(n)=n$ and $p(n)=0$. We give another relation under a new condition in the next theorem.
\begin{theorem}\label{bounded}
If the sequence $\big(\frac{p_n}{q_n-p_n}\big)$ is bounded for any $p$ and $q$ sequences having the deferred property, then the statistical order convergence implies the deferred statistical order convergence.
\end{theorem}

\begin{proof}
Assume that $x_n\soc x$ in a Riesz space $E$ and $\big(\frac{p_n}{q_n-p_n}\big)$ is a bounded sequence for some sequences $p$ and $q$ satisfying the deferred property. Thus, there exists a sequence $z_n\sd0$ such that
$$
\lim\limits_{n\to\infty}\frac{1}{n}|\{k\leq n:|x_k-x|\nleq z_k\}|=0.
$$
It follows from the deferred properties of $(q_n)$ that we obtain
$$
\lim\limits_{n\to\infty}\frac{1}{q_n}|\{k\leq q_n:|x_k-x|\nleq z_k\}|=0.
$$
So, by the following inclusion
$$
\{p_n< k\leq q_n:|x_k-x|\nleq z_k\}\subseteq \{k\leq q_n:|x_k-x|\nleq z_k\},
$$
we obtain
$$
\lim\limits_{n\to\infty}\frac{1}{q_n-p_n}|\{p_n< k\leq q_n:|x_k-x|\nleq z_k\}|
$$
$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \leq \lim\limits_{n\to\infty} \frac{1}{q_n}(1+\frac{p_n}{q_n-p_n})|\{k\leq q_n:|x_k-x|\nleq z_k\}|.
$$
Thus, we get the desired result, $x_n\dc x$.
\end{proof}

The converse of Theorem \ref{bounded} need not be true in general. To see this, we give the following example.
\begin{example}
Consider the Riesz space $E:=\mathbb{R}^2$ equipped with the coordinatewise ordering and a sequence $(x_n)$ in $E$ as follows:
$$
x_n:=
\begin{cases}
(0,\frac{n+1}{2}), & \text{n is odd} \\
(0,-\frac{n}{2}), & \text{n is even}
\end{cases}
$$
for all $n$. Also, take $(q_n):=(2n)$ and $(p_n):=(4n)$. Then, it is clear that the assumption of Theorem \ref{bounded} is fulfilled, and also, $x_n\dc (0,0)$. But, it is not statistical order convergent.
\end{example}

\begin{theorem}
Let $p',q'$ and $p,q$ be pairs of sequences satisfying the deferred property such that $p_n\leq p'_n$ and $q_n'\leq q_n$ for each $n\in\mathbb{N}$, and $(x_n)$ be a sequence in a Riesz space $E$. Then, $x_n\xrightarrow[]{D_{st_o}(p',q')}x$ implies $x_n\dc x$ in $E$ whenever the sets $\{k:p_n<k\leq p'_n\}$ and $\{k:q'_n<k\leq q_n\}$ are finite for every $n\in\mathbb{N}$.
\end{theorem}

\begin{proof}
Assume that $x_n\xrightarrow[]{D_{st_o}(p',q')}x$ holds in $E$. Then, there exists sequence $z_n\downarrow^{D_{st_o}}0$ such that
$$
\delta_{p,q}(\{n\in\mathbb{N}:|x_n-x|\nleq z_n\})=0.
$$
On the other hand, we have the following equality
$$
\{k:p_n<k\leq q_n, \ |x_n-x|\nleq z_n\}=\{k:p_n<k\leq p'_n, \ |x_n-x|\nleq z_n\}
$$
$$
\ \ \ \ \ \cup\{k:p'_n<k\leq q'_n, \ |x_n-x|\nleq z_n\} \cup\{k:q'_n<k\leq q_n, \ |x_n-x|\nleq z_n\}.
$$
It follows that
\begin{eqnarray*}
\lim\limits_{n\to\infty}\frac{1}{q_n-p_n}|\{k:p_n<k\leq q_n, \ |x_n-x|\nleq z_n\}|=0.
\end{eqnarray*}
Hence, we get $x_n\dc x$.
\end{proof}

\begin{corollary}
Let $p',q'$ and $p,q$ be pairs of sequences satisfying the deferred property such that $\lim\limits_{n\to\infty}\frac{q_n-p_n}{q'_n-p'_n}=t>0$, and $(x_n)$ be a sequence in a Riesz space $E$. Then, $x_n\xrightarrow[]{D_{st_o}(p',q')}x$ implies $x_n\dc x$ in $E$.
\end{corollary}

Now, take the set $C^{p,q}_{(z_n)}:=\{(x_n):\exists x\in E,x_n\dc x\ \text{with} \ (z_n)\}$ for a fixed sequence $z_n\downarrow^{D_{st_o}}0$. Then, it is clear that $C^{p,q}_{(z_n)}\subseteq C^{p,q}_{(w_n)}$ whenever $z_n\leq w_n$ holds for all $n\in\mathbb{N}$.
\begin{proposition}
If $\delta_{p,q}(\{n\in\mathbb{N}:z_n\neq w_n\})=0$, then $C^{p,q}_{(z_n)}=C^{p,q}_{(w_n)}$.
\end{proposition}

\begin{proof}
Suppose that $\delta_{p,q}(\{n\in\mathbb{N}:z_n\neq w_n\})=0$ holds for some sequences $z_n\downarrow^{D_{st_o}}0$ and $w_n\downarrow^{D_{st_o}}0$. Take $(x_n)\in C^{p,q}_{(z_n)}$. Then, we have $\delta_{p,q}(\{n:|x_n-x|\nleq z_n\})=1$. It follows from the following inclusion
\begin{eqnarray*}
\{n:|x_n-x|\nleq w_n\}\subseteq\{n:|x_n-x|\nleq z_n\}\cup\{n:z_n\neq w_n\}
\end{eqnarray*}
that we obtain $(x_n)\in C^{p,q}_{(w_n)}$, and so, $C^{p,q}_{(z_n)}\subseteq C^{p,q}_{(w_n)}$. Similarly, we can get $C^{p,q}_{(w_n)}\subseteq C^{p,q}_{(z_n)}$. Therefore, we obtain $C^{p,q}_{(z_n)}=C^{p,q}_{(w_n)}$.
\end{proof}

It is clear that $C^{p,q}_{(z_{k_n})}\subseteq C^{p,q}_{(z_n)}$ for any subsequence $z_{k_n}\downarrow^{D_{st_o}}0$ of sequence $z_n\downarrow^{D_{st_o}}0$. For the converse, we give the following result.
\begin{proposition}
If $z_n\downarrow 0$ holds, then $C^{p,q}_{(z_n)}\subseteq C^{p,q}_{(z_{k_n})}$ satisfies for each subsequence $(z_{k_n})_{k_n\in K}$ of $(z_n)$ with $\delta_{p,q}(K)=1$.
\end{proposition}
\begin{proof}
Assume that $z_n\downarrow 0$ and $(z_{k_n})_{k_n\in K}$ be a subsequence of $(z_n)$ with $\delta_{p,q}(K)=1$. Take any element $(x_n)\in C^{p,q}_{(z_n)}$. Then, we have $x\in E$ and an index set $\delta_{p,q}(M)=1$ such that $|x_{m_n}-x|\leq z_{m_n}$ holds for all $m_n\in M$. On the other hand, by taking $J:=M\cap K$, we have $|x_{j_n}-x|\leq z_{j_n}$ for each $j_n\in J$. Since $(z_{j_n})$ is a subsequence of $(z_{k_n})$, we obtain $(x_n)\in C^{p,q}_{(z_{k_n})}$.
\end{proof}
{\tiny


\section{Introduction}

Consider a query game played on a graph whose goal is to locate a vertex $v^*$ that is unknown to an adaptive query algorithm.
Each query points to a pair of vertices $u$ and $v$, and the reply provides an answer that indicates which of those vertices is closer to $v^*$, breaking ties arbitrarily.
The aim is to construct an algorithm performing as few queries as possible in the worst case.
In this work we consider two types of queries: \emph{edge queries} in which $u$ and $v$ need to be adjacent and \emph{pair queries} in which there is no restriction on the choice of $u$ and $v$.
The latter have not been considered in the literature before while the former have been extensively studied but only for trees.
We note that both models generalize the classical binary search on a path to arbitrary graphs.

\medskip

The game is formally defined in Subsection~\ref{sec:problem}. Our results are summarized in Subsection~\ref{sec:results} and previously known results are highlighted in Subsection~\ref{sec:related_work}. We provide three types of results. First, we reformulate the problem of finding an invisible target in the language of combinatorial game theory in which two perfect players play the game having complete information (Subsection~\ref{sec:reformulation}). We also show some universal bounds and provide a construction that shows the two graph parameters related to edge and, respectively, pair queries can be drastically different (Subsection~\ref{sec:basic_properties}). Then, we investigate the behaviour of the two parameters in binomial random graphs $\G(n,p)$ (Section~\ref{sec:random_graphs}). For a wide range of the parameter $p=p(n)$, the two graph parameters are predictable with high probability and turn out to be of the same order. Finally, we show that determining any of the two parameters is $\mathcal{NP}$-hard for bounded degree graphs (Section~\ref{sec:hardness}).

\subsection{Problem Statement}\label{sec:problem}

For an arbitrary simple graph $G$, we consider two types of \emph{query games}, which differ by the types of allowed queries.
We first define the dynamics of the game and then we define the queries.
The game is played between an (adaptive) \emph{algorithm} and an \emph{adversary}.
The adversary picks in advance a vertex $v^*$ of $G$, that we call the \emph{target}.
The target is unknown to the algorithm and its goal is to locate $v^*$ by asking as few queries as possible.
In each step of the game an algorithm performs a query by selecting two vertices $u$ and $v$ as outlined below depending on the type of the query.
Then, the adversary reveals which of those vertices is closer to $v^*$, providing any of them when their distance to the target is the same.
The \emph{distance} $d_G(u,v)$ between any two vertices $u$ and $v$ is measured as the length of any shortest path between $u$ and $v$ in $G$.
The vertex pointed by the adversary is called the \emph{reply} to the query.
Note that the algorithm is adaptive in the sense that it is making its next query based on the graph and the replies to the previous queries.

In this work we consider two types of graph queries for the game played on $G$.
The more general one, called a \emph{pair query}, selects two arbitrary vertices $u$ and $v$ of $G$.
The second one, called an \emph{edge query}, selects two adjacent vertices $u$ and $v$.
Let $\pqn{G}$ be the least integer $t$ such that the algorithm can locate the target in at most $t$ pair queries, regardless of the strategy of the adversary. The graph parameter $\eqn{G}$ is defined similarly with the only difference that the algorithm has to perform edge queries instead. Since the latter version puts more restriction on the algorithm, for any graph $G$ we have $\pqn{G} \le \eqn{G}$.

The above definition of the process might suggest that this is an incomplete information game in which the target vertex is selected by one of the players (the adversary) but is hidden from the other player (the algorithm). However, because we concentrate on the worst-case scenario (that is, we search for the least number of queries that guarantees the success, regardless where the target is and regardless of the strategy of the adversary), we can alternatively think about this game as a combinatorial game in which both players have a perfect information. In particular, it implies that the graph parameters $\pqn{G}$ and $\eqn{G}$ are well-defined. We reformulate the process in this language in Subsection~\ref{sec:reformulation}.

\subsection{Notation}

In this paper, we present results obtained for the \emph{binomial random graph} $\G(n,p)$. More precisely, $\G(n,p)$ is a distribution over the class of graphs with vertex set $[n]:=\{1,\ldots,n\}$ in which every pair $\{i,j\} \in \binom{[n]}{2}$ appears independently as an edge in $G$ with probability~$p$. Note that $p=p(n)$ may (and usually does) tend to zero as $n$ tends to infinity. We say that $\G(n,p)$ has some property \emph{asymptotically almost surely} or a.a.s.\ if the probability that $\G(n,p)$ has this property tends to $1$ as $n$ goes to infinity. For more about this model see, for example,~\cite{Bollobas,JLR,Karonski_Frieze}.

Given two functions $f=f(n)$ and $g=g(n)$, we will write $f(n)=\mathcal{O}(g(n))$ if there exists an absolute constant $c \in \mathbb{R}_+$ such that $|f(n)| \leq c|g(n)|$ for all $n$, $f(n)=\Omega(g(n))$ if $g(n)=\mathcal{O}(f(n))$, $f(n)=\Theta(g(n))$ if $f(n)=\mathcal{O}(g(n))$ and $f(n)=\Omega(g(n))$, and we write $f(n)=o(g(n))$ or $f(n) \ll g(n)$ if $\lim_{n\to\infty} f(n)/g(n)=0$. In addition, we write $f(n) \gg g(n)$ if $g(n)=o(f(n))$ and we write $f(n) \sim g(n)$ if $f(n)=(1+o(1))g(n)$, that is, $\lim_{n\to\infty} f(n)/g(n)=1$.

We will use $\log n$ to denote a natural logarithm of $n$. For a given $n \in \mathbb{N} := \{1, 2, \ldots \}$, we will use $[n]$ to denote the set consisting of the first $n$ natural numbers, that is, $[n] := \{1, 2, \ldots, n\}$. Finally, as typical in the field of random graphs, for expressions that clearly have to be an integer, we round up or down but do not specify which: the choice of which does not affect the argument.

\subsection{Our Results}\label{sec:results}

Let us start with presenting results for binomial random graphs. The behaviour of $\pqn{G}$ and $\eqn{G}$ change drastically when the random graph changes its diameter. In order to control when this happens, we will use the following well-known result.

\begin{lemma}[\cite{Bollobas}, Corollary 10.12]\label{lem:diameter}
Suppose that $d = pn \gg \log n$ and for some $i = i(n) \in \mathbb{N}$,
$$
d^{i+1}/n - 2 \log n \to \infty \text{ \ \ \ \ and \ \ \ \ } d^{i}/n - 2 \log n \to -\infty.
$$
Then the diameter of $\G(n,p)$ is equal to $i+1$ a.a.s.
\end{lemma}

This result was proved in~\cite[Theorem~6]{bollobas1981diameter} for graphs with $d \gg \log^3 n$ but in~\cite[Corollary~10.12]{Bollobas} the condition was relaxed and it is now required only that $d \gg \log n$.

\medskip

In order to state the results in a simple form, let us concentrate on relatively dense graphs (that is, $d > n^{\varepsilon}$ for some $\varepsilon > 0$) and values of $d$ for which we are relatively far away from the places when the diameter changes its value.

\begin{corollary} \label{cor:xi}
Suppose that $d = pn = n^{\xi + o(1)}$, where $\xi \in ( \frac {1}{i+1}, \frac {1}{i} )$ for some $i \in \mathbb{N}$ ($i$ is an arbitrarily large but fixed constant).
Then, the following properties hold a.a.s.\ for $G \in \G(n,p)$.
$$
\pqn{G} = \Theta \Big( \eqn{G} \Big) = \Theta \left( \frac {n \log n}{d^i} \right).
$$
\end{corollary}

Note that for any $\xi \in ( \frac {1}{i+1}, \frac {1}{i} )$ there exists $\varepsilon = \varepsilon(\xi) > 0$ such that $d^{i}/n = n^{i \xi - 1 + o(1)} \le n^{-\varepsilon} = o(1) \ll \log n$ whereas $d^{i+1}/n = n^{(i+1) \xi - 1 + o(1)} \ge n^{\varepsilon} \gg \log n$. So, by Lemma~\ref{lem:diameter}, the diameter of $\G(n,p)$ is equal to $i+1$ a.a.s. More importantly, it implies that the assumptions stated in Theorems~\ref{thm:lower_bound}, \ref{thm:upper_bound_pqn}, and~\ref{thm:upper_bound_eqn} are satisfied. The first of them yields the desired lower bound for $\pqn{G}$ whereas the last two yield upper bounds for $\pqn{G}$ and, respectively, $\eqn{G}$. The corollary implies that a.a.s.\ both $\pqn{G}$ and $\eqn{G}$ are equal to $n^{f(\xi)+o(1)}$, where function $f(\xi)$ is depicted on Figure~\ref{fig:f}.
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=1]{fig-f.pdf}
	\end{center}
	\caption{An illustration for Corollary~\ref{cor:xi}: the function $f(\xi)$ }
	\label{fig:f}
\end{figure}

The above corollary ignores the cases when $\xi = 1/i$ for some constant $i \in \mathbb{N}$ and very sparse graphs (that is, when $d = n^{o(1)}$). The three theorems mentioned above provide some useful bounds for these regimes but not everything is known. For example, to keep the argument relatively short, we did not consider the cases when $i = i(n)$ is the largest natural number such that $d^i = o(n)$ but also $d^{i+1}/n - 2\log n \to -\infty$ (say, $d^{i+1} = cn$ for some constant $c >0$). Having said that, we provided a short argument dealing with a rather simple case when $p \in (0,1)$ is a fixed constant. The next corollary follows immediately from Theorem~\ref{thm:dense_graphs} which states an explicit upper bound and Observation~\ref{obs:lower} which provides a trivial lower bound but of matching order.

\begin{corollary}
Fix $p \in (0,1)$.
The following property holds a.a.s.\ for $G = (V,E) \in \G(n,p)$:
$$
\pqn{G} = \Theta \Big( \eqn{G} \Big) = \Theta \left( \log n \right).
$$
\end{corollary}

\bigskip

In terms of the complexity, we prove the following result.

\begin{theorem} \label{thm:NP}
Given a graph of diameter at most $3$ and an integer $\ell$, deciding whether $\pqn{G}\leq \ell$ or $\eqn{G}\leq \ell$ is $\mathcal{NP}$-complete.
\end{theorem}

\subsection{Related Work}\label{sec:related_work}

The edge query model has been studied for trees and paths as a special case.
This is due to the fact that the problem for paths is the classical binary search, where most attention received noisy comparison models, see e.g.\ \cite{Ben-OrH08,DaganFGM17,DereniowskiLU21,DereniowskiTUW19,FeigeRPU94,KarpK07}.
As for the case of trees, they generalize binary search to searching partial orders with some interesting applications e.g.\ in automated program testing~\cite{Ben-AsherFN99}.
It turns out that $\eqn{T}$ for a tree $T$ can be computed in linear time~\cite{MozesOW08}.
Interestingly, this problem re-appeared under various different names like minimum height elimination trees~\cite{Liu90}, LIFO-search~\cite{GiannopoulouHT12}, tree-depth~\cite{NesetrilM06}, or edge ranking.
Due to the latter connection, a linear-time algorithm has been independently shown for trees in~\cite{LamY01}. Edge queries in trees are also of interest in applications like parallel database query processing, where one wants to find a spanning tree $T$ of the graph representing a database query that minimizes $\eqn{T}$~\cite{MakinoUI01}.
For some research on random partial orders in this context see~\cite{CarmoDKL04}.

It is natural to further generalize edge queries to the weighted variant, where the weight of an edge represent the duration of a query~\cite{LaberMP02}.
Such an extension turns out to be $\mathcal{NP}$-complete for some quite narrow subclasses of trees~\cite{CicaleseJLV12,CicaleseKLPV16,Dereniowski06}.
On the other hand, there has been a series of results on approximation algorithms~\cite{CicaleseJLV12,CicaleseKLPV16,Dereniowski06} with the best approximation ratio to date being $\mathcal{O}(\sqrt{\log n})$ that was proved in~\cite{DereniowskiKUZ17}.
Finally, let us mention another generalization of binary search in linear orders to graphs~\cite{Zadeh16,DereniowskiTUW19} with some interesting applications in machine learning \cite{Zadeh17}.

\medskip

Another related problem is the localization game (cf.~\cite{bonato2020bounds,bosek2018localization,carraher2012locating,seager2014locating}), in particular, there are many similarities between its centroidal variant~\cite{bosek2018centroidal} and our game. Indeed, the idea behind the localization game is similar to the pair query model. The main difference is that the target may move to a neighbouring vertex between queries. As a result, more than two vertices need to be examined by a query in order to guarantee capture and the goal is to minimize the number of vertices examined in each round. For the localization game the reply returns a vector of distances between the current position of the target and each of the examined vertices. In particular, in this language the famous metric dimension of a graph is the minimum number of sensors needed in the localization game so that the target is found in one single round. For the centroidal variant of the game, the reply informs the player when the distance is zero; otherwise, for every pair of examined vertices the result of comparison of distances is returned (that is, which vertex is closer or whether distances are equal).

\medskip

Although, the query games have not yet been studied for random graphs, there are some known results for the closely related graph parameters mentioned above.  An asymptotic behaviour of  the metric dimension of dense binomial random graphs $\G(n,p)$ is obtained in~\cite{bollobas2013metric}, while for sparse, subcritical $\G(n,p)$ and uniform random trees and forests, its asymptotic distribution is shown in~\cite{mitsche2015limiting}. The localization number for dense binomial random graphs (in particular, in the regime in which $\G(n,p)$ has diameter two a.a.s.) was studied in~\cite{dudek2019note}. The bounds for dense graphs were consecutively improved in~\cite{dudek2022localization}, and the arguments were extended to sparse graphs. The localization game was also recently studied for random geometric graphs~\cite{lichev2021localization}. We direct the reader to the book~\cite{bonato2017graph} for more graph searching games in the context of random graphs.

\section{Preliminaries}

\subsection{Reformulation of the Process}\label{sec:reformulation}

In this subsection, we provide a reformulation of the game that will be easier to deal with when proving our results. In particular, this reformulation will show that the process can be viewed as a combinatorial game. Indeed, it is convenient to think about this game as the target is \emph{not} selected a priori by the adversary but rather as a process in which after a $t$-th query the set $V_t$ of \emph{potential targets} is maintained by both players.

Let us denote by $\dist{u}{v}$ the distance between $u$ and $v$ in a given graph $G=(V,E)$.
For any pair of vertices $u$ and $v$, let
$$\mathcal{C}(u,v)=\{ x \in V \hspace{0.1cm}\bigl|\bigr.\hspace{0.1cm} \dist{u}{x} \leq \dist{v}{x} \},$$
that is, $\mathcal{C}(u,v)$ is the set of vertices that are closer to $u$ than to $v$, or at the same distance from both $u$ and $v$.
For a reply $u$ to the query on $u,v$, we say that a vertex $x$ is \emph{compatible} with the reply if $x\in \mathcal{C}(u,v)$.

With these definitions at hand, we may formally define $V_t$ to be the set of vertices of $G$ that are compatible with each of the first $t$ replies. In other words, each vertex from the set $V_t$ satisfies all inequalities associated with the first $t$ queries and the corresponding replies. On the other hand, no vertex from $V \setminus V_t$ has this property.
The game starts with $V_0 = V$. At the beginning of round $t \in \mathbb{N}$, the first player (the algorithm) presents a pair of vertices $(u_t, v_t)$ which partitions $V_{t-1}$, the set of potential targets from the previous round, into three sets:
\begin{itemize}
    \item $V_t^< := V_{t-1} \cap (\mathcal{C}(u_t,v_t) \setminus \mathcal{C}(v_t,u_t)$), the set of vertices of $V_{t-1}$ that are closer to $u_t$ than to $v_t$,
    \item $V_t^> := V_{t-1} \cap (\mathcal{C}(v_t,u_t) \setminus \mathcal{C}(u_t,v_t)$), the set of vertices of $V_{t-1}$ that are closer to $v_t$ than to $u_t$,
    \item $V_t^= := V_{t-1} \cap (\mathcal{C}(u_t,v_t) \cap \mathcal{C}(v_t,u_t)$), the set of vertices of $V_{t-1}$ that are at the same distance from both $u_t$ and $v_t$.
\end{itemize}
The second player (the adversary) has now two options: fix $V_t = V_{t-1} \cap \mathcal{C}(u_t,v_t) = V_t^< \cup V_t^=$ (that is, reply with vertex $u_t$) or fix $V_t = V_{t-1} \cap \mathcal{C}(v_t,u_t) = V_t^> \cup V_t^=$ (that is, reply with vertex $v_t$). After making the decision, the round is over and we move to the next round.
The game ends when $|V_t|=1$ since the only element in $V_t$ must be the target.
With this point of view, one may think about the adversary as also being adaptive in the sense that the goal of the adversary is to provide replies which result in maximizing the value of $t$ for which $V_t$ is a singleton.

\subsection{Some Basic Properties}\label{sec:basic_properties}

In order to warm-up, let us start with a few simple observations highlighting some properties of the two graph parameters we are concerned with in this paper.

\begin{observation} \label{obs:lower}
For any connected graph $G$ on $n$ vertices,
$$
\log_2 n \le \pqn{G} \le \eqn{G} \le n-1.
$$
In fact, there exists a strategy of the algorithm that in each round eliminates at least one vertex from the search space. (This, of course, implies an upper bound of $n-1$.)
\end{observation}

\begin{proof}
The inequality $\pqn{G} \le \eqn{G}$ follows immediately from the fact that pair queries are more general than edge queries. Hence, any strategy asking edge queries can be used by more flexible algorithm asking pair queries.

The lower bound of $\log_2 n$ is due to the fact that there exists a strategy (simple and greedy) for the adversary that guarantees that each pair query reduces the search space by at most half. Indeed, recall that in round $t \in \mathbb{N}$, set $V_{t-1}$ is partitioned into three sets, $V_t^<$, $V_t^>$, and $V_t^=$ (the partition depends on the algorithm) and then $V_t = V_t^< \cup V_t^=$ or $V_t = V_t^> \cup V_t^=$ (the choice belongs to the adversary). Hence, indeed, there exists a strategy for the adversary that guarantees that for each $t \in \mathbb{N}$ we have $|V_t| \ge |V_{t-1}| / 2$. Hence, $|V_t| \ge |V_0| / 2^t = n / 2^t$ implying that $|V_t| > 1$ if $t < \log_2 n$. The lower bound holds.

To prove the upper bound of $n-1$, let us present another simple strategy for the algorithm, this time performing edge queries, that guarantees that in each round at least one vertex is eliminated from the search space. Assume that $|V_{t-1}| \ge 2$, and let $x$, $y$, $x \neq y$, be any two vertices from $V_{t-1}$. Let $(x=z_0, z_1, \ldots z_k = y)$ be any shortest path between $x$ and $y$. The algorithm, for example, may select vertices $u_t = x = z_0$ and $v_t = z_1$ as its edge query to eliminate $x$ or $y$ from the search space, giving $|V_t| \le |V_{t-1}| - 1$. This finishes the proof of the observation.
\end{proof}

The next observation shows that the two easy bounds we proved above are sharp. We leave it as an easy exercise for the reader and only provide a hint that edge queries can mimic the binary search on a path.

\begin{observation} \label{obs:simple}
For any $n \in \mathbb{N} \setminus \{1\}$,
$\eqn{K_n} = \pqn{K_n} = n-1$,
$\eqn{K_{1,n-1}} = \pqn{K_{1,n-1}} = n-1$,
$\eqn{P_n} = \pqn{P_n} = \lceil\log_2n\rceil$.
\end{observation}

The last observation shows that the difference between the two variants of the game may be asymptotically as large as possible.

\begin{observation}
For any $n \in \mathbb{N} \setminus \{1\}$, there exists a graph $G$ on $\Theta(n)$ vertices such that $\eqn{G} = \Omega(n)$ and $\pqn{G} = \mathcal{O}(\log n)$.
\end{observation}
\begin{proof}
For a fixed $n \in \mathbb{N} \setminus \{1\}$, let $k=k(n)=\lfloor\log_2n\rfloor$. Let $T_k$ be a full binary tree of height $k$. (The height is measured as the length of a path from the root to any of the leaves.)
We say that the vertices at distance $i$ from the root in $T_k$ are at \emph{level} $i$, $i\in\{0,\ldots,k\}$. We denote the set of vertices at level $i$ by $L_i$; in particular, $L_k$ is the set of the leaves of $T_k$ and $L_0$ consists of only one vertex, the root of $T_k$. It will be convenient to use $T_k(x)$, $x\in V(G)$, to denote the subtree of $T_k$ induced by the set consisting of $x$ and all of its descendants in $T_k$.

We construct a graph $G = G_k$ on the same vertex set as $T_k$ (that is, $V(G_k) = V(T_k)$).
Note that $|V(G_k)| = 2^{k+1} - 1$, hence $n \le |V(G_k)| < 2n$.
The edge set $E(G_k)$ is defined as follows. First of all, we join any two leaves of $T_k$ by an edge, that is, the set $L_k$ induces a complete graph in $G_k$. Then, for any non-leaf $u$ of $T_k$ (that is, $u \in V(T_k) \setminus L_k$) we join $u$ to all the leaves of a subtree $T_k(u)$ of $T_k$ rooted at $u$.
Note that not all edges of tree $T_k$ are present in $G_k$---see Figure~\ref{fig:obsdif} for an example of this construction.

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width = 0.5\textwidth]{fig-g3.pdf}
	\end{center}
	\caption{A graph $G_3$. The dashed edges are edges of $T_3$ that are \emph{not} present in $G_3$. }\label{fig:obsdif}
\end{figure}

\medskip

Let us start with providing a strategy for the algorithm that proves that $\pqn{G_k} \le 2k$, hence $\pqn{G_k}=\mathcal{O}(\log n)$.
We will distinguish two phases. During the first phase the algorithm performs $k$ pair queries starting from vertices that at close to the root and moving toward the leaves, each time essentially removing one branch of $T_k$ from the search space.

Formally, as always, the algorithm starts with $V_0 = V(G_k) = V(T_k)$ and $u_0$ being the root of $T_k$.
In the first round, the algorithm queries two children of $u_0$ that we denote by $v^1_0$ and $v^2_0$. By symmetry of graph $G_k$, without loss of generality we may assume that the reply is $v^1_0$. Note that all vertices in $T_k(v^1_0)$ are closer to $v^1_0$ than to $v^2_0$. The only vertex that is at the same distance from both $v^1_0$ and $v^2_0$ is the root of $T_k$ (that is, $V_1^= = \{u_0\}$). Hence, the algorithm moves to the next round with $V_1 = V_0 \cap \mathcal{C}(v^1_0, v^2_0) = V_0 \setminus V(T_k(v^2_0))$ and we prepare ourselves for the next round by fixing $u_1 = v^1_0$. Note that $V_1 = V(T_k(u_1)) \cup \{u_0\}$, where $\{u_0\}$ is the set of ancestors of $u_1$ in $T_k$.
We recursively follow the same strategy as for the first round. Suppose that at the end of round $t$, for some $1 \le t < k$, we have a vertex $u_t$ at level $t$ identified such that $V_t = V(T_k(u_t)) \cup \{u_0, \dots u_{t-1}\}$, where $u_i$ is the ancestor of $u_t$ at level $i < t$. At round $t+1$, the algorithm queries two sons of $u_t$, $v^1_t$ and $v^2_t$. As before, because of symmetry, without loss of generality we may assume that the reply is $v^1_t$. Then, we fix $u_{t+1} = v^1_t$ such that
$$
V_{t+1} = V_t \cap \mathcal{C}(v^1_t, v^2_t) = V_t \setminus V(T_k(v^2_t)) = V(T_k(u_{t+1})) \cup \{u_0, \dots u_{t}\}.
$$
It follows that after $k$ pair queries, regardless of the strategy of the adversary, the algorithm learns that the target is hidden in the set $V_k = \{u_0, \dots, u_k\}$ where $u_k$ is some leaf of $T_k$, while $u_i$ for $i < k$ is the ancestor of $u_k$ at level $i$.

During the second phase, by Observation~\ref{obs:lower}, the algorithm may eliminate at least one vertex at the time. The target is then identified in at most $k$ additional rounds and so the total number of pair queries is at most $2k=\mathcal{O}(\log n)$.

\medskip

We now move to the proof of the fact that $\eqn{G_k}=\Omega(n)$.
In order to simplify the argument, we assume that the algorithm is provided with some additional information, namely, that the target is in $L_k$. (In other words, we start the game with $V_0 = L_k$ instead of $V_0 = V(G_k)$.) We will show that even with this additional information, the algorithm cannot quickly identify the target.

Consider a query to an edge $uu' \in E(G_k)$. Since each edge of $G_k$ has at least one leaf from $T_k$, without loss of generality we may assume that $u' \in L_k$. If $u \not \in L_k$, then the adversary might reply with $u'$ which provides no new information to the algorithm.
Thus, the algorithm is forced to query edges within the complete graph induced by $L_k$. However, since all vertices in $L_k$ are at distance one from each other, each such query eliminates at most one vertex from the search space. It follows that the number of edge queries that is needed to identify the target is at least $|L_k|-1 = 2^k-1 \ge \frac{n}{2}$.
This finishes the proof of the lower bound of $\eqn{G_k}$ and so also the proof of the observation.
\end{proof}

\section{Random Graphs}\label{sec:random_graphs}

Let us first state a specific instance of Chernoff's bound that we will find often useful. Let $X \in \textrm{Bin}(n,p)$ be a random variable with the binomial distribution with parameters $n$ and $p$. Then, a consequence of Chernoff's bound (see e.g.~\cite[Corollary~2.3]{JLR}) is that
\begin{equation}\label{chern}
\mathbb{P} \Big( |X-\mathbb E [X]| \ge \varepsilon \ \mathbb E [X] \Big) \le 2\exp \left( - \frac {\varepsilon^2 \ \mathbb E [X]}{3} \right)
\end{equation}
for  $0 < \varepsilon < 3/2$. However, at some point we will need need a stochastic upped bound for $X$ when $\mathbb E[X]$ is small. In such situations the following bound can be applied instead of~(\ref{chern}) (see e.g.~\cite[Theorem~2.1]{JLR}):
\begin{equation}\label{chern2}
\mathbb{P}( X \ge \mathbb E [X] + u ) \le \exp \left( - \frac {u^2}{2(\mathbb E [X] + u/3)} \right).
\end{equation}

\subsection{Lower Bound}

Let us start with the following expansion properties of random graphs. For a vertex $v \in V$, let $N_i(v)$ and $N_{\le i}(v) = \bigcup_{j=0}^i N_i(v)$ denote the set of vertices at distance $i$ from $v$ and the set of vertices at distance at most $i$ from $v$, respectively. For any $Z \subseteq V$, let $N_i(Z) = \bigcup_{v \in Z} N_i(v)$ and $N_{\le i}(Z) = \bigcup_{v \in Z} N_{\le i}(v)$.

\begin{lemma}\label{lem:gnp exp}
Suppose that $\omega \log n \le d=pn \le n / \omega = o(n)$, where $\omega=\omega(n)$ is any function tending to infinity as $n \to \infty$ such that $\omega \le \log n$.

Then, the following properties hold a.a.s.\ for $G = (V,E) \in \G(n,p)$.
\begin{itemize}
\item [(a)] Suppose that for some $i = i(n) \in \mathbb{N}$ and $Z \subseteq V$ with $z=|Z|$ we have $zd^i = o(n)$. Then,
$$
\left| N_{\le i}(Z) \right| = \left(1+ \mathcal{O} \left( \frac {1}{\sqrt{\omega}}\right) + \mathcal{O} \left( \frac{zd^i}{n} \right) \right) d^i |Z| \sim d^i |Z|,
$$
and so also
$$
\left| N_i(Z) \right| = \left(1+ \mathcal{O} \left( \frac {1}{\sqrt{\omega}}\right) + \mathcal{O} \left( \frac{zd^i}{n} \right) \right) d^i |Z| \sim d^i |Z|.
$$
\item [(b)] Let $i=i(n) \in \mathbb{N}$ be the largest integer such that $d^i = o(n)$. Let
$$
z := \frac {n}{d^i} \log (d^i) \left(1 - \frac {1}{\omega^{1/3}} \right) = \Theta \left( \frac {n}{d^i} \log n \right).
$$
Then, for any $Z \subseteq V$ with $|Z|=z$ there are at least two vertices at distance at least $i+1$ from $Z$, that is, $|N_{\le i}(Z)| \le n-2$.
\end{itemize}
\end{lemma}

\begin{proof}
In order to investigate the expansion property of neighbourhoods, let $Z \subseteq V$, $z=|Z|$, and consider the random variable $X = X(Z) = |N_{\le 1}(Z)|$. We will bound $X$ in a stochastic sense. There are two things that need to be estimated: the expected value of $X$, and the concentration of $X$ around its expectation.

Since for $x=o(1)$ we have $(1-x)^z = e^{-xz(1+\mathcal{O}(x))}$ and also $e^{-x}=1-x+\mathcal{O}(x^2)$, it is clear that
\begin{eqnarray}
\mathbb E [X] &=& n - \left(1- \frac {d}{n-1} \right)^z (n-z) \nonumber \\
&=& n - \exp \left( - \frac {dz}{n} (1+\mathcal{O}(d/n)) \right) (n-z) \nonumber \\
&=& dz (1+\mathcal{O}(dz/n) ), \label{eq:expX}
\end{eqnarray}
provided $dz = o(n)$. It follows from Chernoff's bound~\eqref{chern} applied with $\varepsilon = 3/{\sqrt{\omega}}$ that the expected number of sets $Z$ satisfying
$$
\big| |N_{\le 1}(Z)| - \mathbb E[|N_{\le 1}(Z)|] \big| > \varepsilon d|Z|
$$
is at most
$$
2 \binom{n}{z} \exp \left( - \frac {\varepsilon^2 d z}{3+o(1)} \right) \le 2 n^z \exp \left( - \frac {\varepsilon^2 (\omega \log n) z }{3+o(1)} \right) = 2 n^z \exp \Big( - (3+o(1)) z \log n \Big) = o(1),
$$
since $d \geq \omega \log n$. Hence the statement holds for $i=1$ a.a.s.

Now, we will estimate the cardinalities of $N_{\le i}(Z)$ up to the $i$'th iterated neighbourhood, provided $zd^i = o(n)$ and thus $i = O(\log n /\log \log n)$. Suppose then that for some $i \ge 2$, $Y = N_{\le i-1}(Z)$ satisfies $|Y| \sim d^{i-1} z$ and $|Y| = o(n/d)$. It follows from~(\ref{eq:expX}) and~(\ref{chern}) (this time applied with $\varepsilon = 4 d^{-(i-1)/2} \omega^{-1/2}$) that with probability at least $1-\beta$,
$$
|N_{\le 1}(Y)| = d |Y| \left( 1+ \mathcal{O} \left( d|Y|/n \right) + \mathcal{O} \left( d^{-(i-1)/2} \omega^{-1/2} \right) \right),
$$
where the bounds in $\mathcal{O}()$ notation are uniform. The failure probability is at most
$$
\beta = 2 \exp \left( - \frac {\varepsilon^2 d |Y|}{3+o(1)} \right) = 2 \exp \left( - \frac {\varepsilon^2 d^i z}{3+o(1)} \right) \le \exp \left( - 5 d z / \omega \right) \le \exp( - 5 z \log n) \le n^{-z} n^{-4}.
$$
As we want a result that holds a.a.s., we may assume this statement holds deterministically, since there are only $\mathcal{O}(n^z \log n)$ choices for $Z$ and $i$.

Given this assumption, we have good bounds on the ratios of the cardinalities of $N_{\le 1}(Z)$, $N_{\le 1}(N_{\le 1}(Z)) = N_{\le 2}(Z)$, and so on. Since $i=O(\log n / \log \log n)$ and $\sqrt{\omega} \le (\log n)^{1/2}$, the cumulative multiplicative error term is
\begin{align*}
(1+&\mathcal{O}(dz/n) + \mathcal{O}(1/\sqrt{\omega})) \prod_{j=2}^i \left( 1+ \mathcal{O} \left( d^jz/n \right) + \mathcal{O} \left( \omega^{-1/2} d^{-(j-1)/2} \right) \right) \\
&= (1+\mathcal{O}(1/\sqrt{\omega}) + \mathcal{O}(d^iz/n) )  \prod_{j=5}^{i-2} \left( 1+ \mathcal{O} \left( \log^{-2} n \right) \right) = (1+ \mathcal{O}(1/\sqrt{\omega}) + \mathcal{O}(d^iz/n) ),
\end{align*}
and the proof of part (a) is complete.

\bigskip

In order to prove part (b), let us fix any set of vertices $Z \subseteq V$ of size
$$
|Z|=z=\frac {n}{d^i} \log (d^i) \left(1 - \frac {1}{\omega^{1/3}} \right),
$$
where $i=i(n) \in \mathbb{N}$ be the largest integer such that $d^i = o(n)$. Note that, by the definition of $i$,
$$
\left( \frac 12 + o(1) \right) \frac {n \log n}{d^i} \le z \le \frac {n \log n}{d^i}.
$$
Since $zd^{i-1}/n = \mathcal{O}( \log n / d ) = \mathcal{O}( \omega^{-1} )$, we may expose $N_{\le i-1}(Z)$ and based on part~(a) we may assume that
$$
|N_{\le i-1}(Z)| = (1+\mathcal{O}(\omega^{-1/2})) \, zd^{i-1}.
$$
There are $(1+\mathcal{O}( \omega^{-1} )) \, n$ vertices outside of $N_{\le i-1}(Z)$. The probability that a given one of them is not adjacent to any vertex of $N_{\le i-1}(Z)$ is $(1-p)^{(1+\mathcal{O}(\omega^{-1/2})) \, zd^{i-1}}$ and so the probability that all of them belong to $N_{\le i}(Z)$ (that is, $N_{\le i+1}(Z) = \emptyset$) is equal to
\begin{eqnarray*}
q &=& \left( 1 - (1-p)^{(1+\mathcal{O}(\omega^{-1/2})) \, zd^{i-1}} \right)^{(1+\mathcal{O}( \omega^{-1} )) \, n} \\
&=& \left( 1 - \exp \left( - \frac {(1+\mathcal{O}(\omega^{-1/2})) \, zd^{i}}{n} \right) \right)^{(1+\mathcal{O}( \omega^{-1} )) \, n} \\
&=& \left( 1 - \exp \left( - \left( 1 - \frac {1+o(1)}{\omega^{1/3}} \right) \log(d^i) \right) \right)^{(1+\mathcal{O}( \omega^{-1} )) \, n}.
\end{eqnarray*}
Since $\log(d^i) = \Theta(\log n)$ and $\omega \le \log n$, $(1+o(1)) \log(d^i) / \omega^{1/3} \ge 3 \log \log n$ and so
\begin{eqnarray*}
q &\le& \left( 1 - \exp \left( - \log(d^i)  + 3 \log \log n \right) \right)^{(1+\mathcal{O}( \omega^{-1} )) \, n} \\
&=& \left( 1 - \frac {\log^3 n}{d^i} \right)^{(1+\mathcal{O}( \omega^{-1} )) \, n} \\
&=& \exp \left( - (1+o(1)) \, \frac {n \log^3 n}{d^i} \right).
\end{eqnarray*}
Similarly, the probability that all but exactly one vertex outside of $N_{\le i-1}(Z)$ belong to $N_{\le i}(Z)$ is equal to
\begin{align*}
(1+o(1)) n \, (1-p)^{(1+\mathcal{O}(\omega^{-1/2})) \, zd^{i-1}} & \left( 1 - (1-p)^{(1+\mathcal{O}(\omega^{-1/2})) \, zd^{i-1}} \right)^{(1+\mathcal{O}( \omega^{-1} )) \, n} \\
& \le nq \le \exp \left( - (1+o(1)) \, \frac {n \log^3 n}{d^i} \right).
\end{align*}
On the other hand, the number of sets of size $z$ is, trivially, at most
$$
\binom{n}{z} \le n^z = \exp \left( z \log n \right) \le \exp \left( \frac {n \log^2 n}{d^i} \right) = o( nq ).
$$
We get that the expected number of sets $Z \subseteq V$ with $|Z|=z$ with the property that at most one vertex is at distance at least $i+1$ from $Z$ is equal to $o(1)$ and so the desired property holds a.a.s.\ by the first moment method. This finishes part~(b) and the proof of the lemma.
\end{proof}

Now, we are ready to prove a lower bound for $\pqn{G}$.

\begin{theorem}\label{thm:lower_bound}
Suppose that $\omega \log n \le d=pn \le n / \omega = o(n)$, where $\omega=\omega(n)$ is any function tending to infinity as $n \to \infty$ such that $\omega \le \log n$.
Let $i=i(n) \in \mathbb{N}$ be the largest integer such that $d^i = o(n)$.
Suppose that $d^{i+1} / n - 2 \log n \to \infty$.

Then, the following property holds a.a.s.\ for $G = (V,E) \in \G(n,p)$:
$$
\eqn{G} \ge \pqn{G} \ge k := \frac {n}{2 d^i} \log (d^i) \left(1 - \frac {1}{\omega^{1/3}} \right) = \Omega \left( \frac {n \log n}{d^i} \right).
$$
\end{theorem}
\begin{proof}
Note that we assumed that $d^{i+1} / n - 2 \log n \to \infty$ and by definition of $i$ we get that $d^{i} / n - 2 \log n \to -\infty$. Hence, by Lemma~\ref{lem:diameter} we get that the diameter of $\G(n,p)$ is equal to $i+1$ a.a.s.

\medskip

Typically, in order to establish lower bounds for the length of the game, one needs to show a strategy for the second player (the adversary) and prove that this strategy guarantees that the game is not over after $k$ rounds. However, our ``board'' (random graph $\G(n,p)$) has nice expansion properties that guarantee that the game cannot finish earlier \emph{regardless} what the adversary does.

Suppose then that the first player (the algorithm) presents a sequence of pairs of vertices $(u_t,v_t)_{t \in [k]}$ during the first $k$ rounds of the game. Let
$$
Z = \{ u_t : t \in [k] \} \cup \{ v_t : t \in [k] \}
$$
be the set of all vertices presented during this part of the game. Clearly, $|Z| \le 2k$. We may add some additional vertices to $Z$, if needed, so that $|Z| = 2k$. By Lemma~\ref{lem:gnp exp}(b), we may assume that there are at least two vertices (say, $x$ and $y$) that are at distance at least $i+1$ from $Z$. Since the diameter of $G$ is equal to $i+1$, these two vertices are at distance exactly $i+1$ from any vertex in $Z$ and so, in particular, from any vertex that was presented up to this point of the game. We get that $\{x,y\} \subseteq V^=_t$ for all $t \in [k]$, which implies that $x$ and $y$ are compatible with all replies so far. As a result, regardless of what the adversary does, $\{x,y\} \subseteq V_k$ and so the game is not over yet. This finishes the proof of the theorem.
\end{proof}

\subsection{Upper Bounds}

As usual, let us start with some useful expansion properties of random graphs.

\begin{lemma}\label{lem:gnp exp2}
Suppose that $\omega \log n \le d=pn \le n / \omega = o(n)$, where $\omega=\omega(n)$ is any function tending to infinity as $n \to \infty$ such that $\omega \le \log n$.  Let $i=i(n) \in \mathbb{N}$ be the largest integer such that $d^i = o(n)$. Finally, let $\hat{\omega} = \hat{\omega}(n) = \min( \sqrt{\omega}, n/d^i ) \to \infty$ as $n \to \infty$.

The following properties hold a.a.s.\ for $G = (V,E) \in \G(n,p)$.
For any vertices $x,y \in V$ ($x \neq y$) we partition the set of vertices $V$ into the following 4 parts:
\begin{eqnarray*}
X &=& N_i(x) \setminus N_{\le i}(y) \\
Y &=& N_i(y) \setminus N_{\le i}(x) \\
Z &=& V \setminus N_{\le i}(\{x,y\}) \\
R &=& V \setminus (X \cup Y \cup Z) = N_{\le i}(x) \cap N_{\le i}(y).
\end{eqnarray*}
Then, the following holds:
\begin{itemize}
\item [(a)] $|X| = \left(1+ \mathcal{O} \left( \hat{\omega}^{-1} \right) \right) d^i \sim d^i$.
\item [(b)] $|Y| = \left(1+ \mathcal{O} \left( \hat{\omega}^{-1} \right) \right) d^i \sim d^i$.
\item [(c)] $|Z| = n - \left(2+ \mathcal{O} \left( \hat{\omega}^{-1} \right) \right) d^i \sim n$.
\item [(d)] $|R| = \mathcal{O} \left( \hat{\omega}^{-1} \right) d^i = o(d^i)$.
\end{itemize}
Moreover, the following holds, provided that $d^{i+1} / n \gg \hat{\omega} \log n$:
\begin{itemize}
\item [(e)] Each vertex in $X \cup Y \cup Z$ has $\mathcal{O} \left( \hat{\omega}^{-1} \right) d^{i+1} / n$ neighbours in $R$.
\item [(f)] Each vertex in $X \cup Z$ has $\left(1+ \mathcal{O} \left( \hat{\omega}^{-1/2} \right) \right) d^{i+1} / n \sim d^{i+1}/n$ neighbours in $Y$.
\item [(g)] Each vertex in $Y \cup Z$ has $\left(1+ \mathcal{O} \left( \hat{\omega}^{-1/2} \right) \right) d^{i+1} / n \sim d^{i+1}/n$ neighbours in $X$.
\end{itemize}
\end{lemma}

\begin{proof}
Parts~(a)--(d) follow immediately and deterministically from Lemma~\ref{lem:gnp exp}(a). Since we aim for a statement that holds a.a.s., we may assume that the property stated in Lemma~\ref{lem:gnp exp}(a) holds for any set $Z \subseteq V$ with $|Z| \le 2$:
\begin{eqnarray}
\left| N_i(Z) \right| &=& \left(1+ \mathcal{O} \left( \frac {1}{\sqrt{\omega}}\right) + \mathcal{O} \left( \frac{d^i}{n} \right) \right) d^i |Z| \sim d^i |Z|,\label{eq:ball_of_Z} \\
\left| N_{\le i}(Z) \right| &=& \left(1+ \mathcal{O} \left( \frac {1}{\sqrt{\omega}}\right) + \mathcal{O} \left( \frac{d^i}{n} \right) \right) d^i |Z| \sim d^i |Z|.\label{eq:sphere_of_Z}
\end{eqnarray}
Now, for a given $x,y \in V$ ($x \neq y$) we may apply~\eqref{eq:ball_of_Z}--\eqref{eq:sphere_of_Z} with $Z=\{x,y\}$, $Z=\{x\}$, and $Z=\{y\}$ to get the desired properties. This finishes the proof of parts~(a)--(d).

\medskip

In order to prove part~(e), let us concentrate on any pair of vertices $x,y \in V$ ($x \neq y$). We first expose edges up to the $(i-1)$th neighbourhood of $\{x,y\}$. Since we aim for a statement that holds a.a.s., by Lemma~\ref{lem:gnp exp}(a) we may assume that $|N_{\le i-1}(\{x,y\})| \sim 2d^{i-1} = \mathcal{O} \left( \hat{\omega}^{-1} \right) d^i$. For any vertex $v \notin N_{\le i-1}(\{x,y\})$, let $Q$ be the number of neighbours of $v$ in $N_{\le i-1}(\{x,y\})$. Clearly, $Q$ is a binomial random variable with expectation equal  to $|N_{\le i-1}(\{x,y\})| d/n = \mathcal{O} \left( \hat{\omega}^{-1} \right) d^{i+1}/n$. It follows from Chernoff's bound~\eqref{chern2} that
$$
\mathbb{P}( Q \ge \mathbb E [Q] + \hat{\omega}^{-1} d^{i+1}/n ) \le \exp \left( - \Omega \left( \hat{\omega}^{-1} d^{i+1}/n \right) \right) = o(1/n^3),
$$
since it is assumed that $d^{i+1} / n \gg \hat{\omega} \log n$. By the union bound over $x,y$, and $v$, we may assume that all vertices outside of $N_{\le i-1}(\{x,y\})$ have $\mathcal{O} \left( \hat{\omega}^{-1} \right) d^{i+1}/n$ neighbours in $N_{\le i-1}(\{x,y\})$.

Let us now expose edges up to the $i$th neighbourhood of $\{x,y\}$, which identifies sets $X$, $Y$, $Z$, and $R$.
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.85]{fig-xyz.pdf}
	\end{center}
	\caption{An illustration of the partition of $V$: $X,Y,Z$, and $R = (N_i(x) \cap N_i(y)) \cup N_{\le i-1}(\{x,y\})$ (grey area).}
	\label{fig:xyz}
\end{figure}
Since we aim for a statement that holds a.a.s., we may assume that properties (a)--(d) hold. More importantly, note that edges within $V \setminus N_{\le i-1}(\{x,y\}) = X \cup Y \cup Z \cup (N_i(x) \cap N_i(y))$ are not exposed yet---see Figure~\ref{fig:xyz} for an illustration. For any $v \in X \cup Y \cup Z$, the expected number of neighbours of $v$ in $N_i(x) \cap N_i(y)$ is at most $|R| d/n = \mathcal{O} \left( \hat{\omega}^{-1} \right) d^{i+1}/n$. After applying Chernoff's bound~\eqref{chern2} again we get that a.a.s., for all $x,y$, all vertices in $X \cup Y \cup Z$ have $\mathcal{O} \left( \hat{\omega}^{-1} \right) d^{i+1} / n$ neighbours in $N_i(x) \cap N_i(y)$. This, together with the previous observation, implies the same bound for the number of neighbours in $R = (N_i(x) \cap N_i(y)) \cup N_{\le i-1}(\{x,y\})$, which concludes the proof of part~(e).

\medskip

To prove part~(f), let us expose edges up to the $i$th neighbourhood of $\{x,y\}$ and fix any $v \in X \cup Z$. Let $Q$ be the number of neighbours of $v$ in $Y$. Clearly, $\mathbb E [Q] = |Y| d/n = \left(1+ \mathcal{O} \left( \hat{\omega}^{-1} \right) \right) d^{i+1} / n \gg \hat{\omega} \log n$. The conclusion follows from Chernoff's bound~\eqref{chern} (applied with $\varepsilon = \hat{\omega}^{-1/2}$), since
$$
\mathbb{P} \Big( |Q-\mathbb E [Q]| \ge \varepsilon \ \mathbb E [Q] \Big) \le 2\exp \left( - \Omega( \varepsilon^2 \mathbb E[Q] ) \right) = o(1/n^3).
$$
The proof of part~(g) is exactly the same. This finishes the proof of the lemma.
\end{proof}

Let us start with a proof of an upper bound for $\pqn{G}$. Of course, since $\pqn{G} \le \eqn{G}$, any upper bound for $\eqn{G}$ implies the same bound for $\pqn{G}$. There are two reasons why we present them independently. First of all, the corresponding strategies for the first player (the algorithm) are slightly different but the proofs that they are winning strategies are almost identical. We present details for a slightly easier proof for $\pqn{G}$ and then we will discuss how to adjust it to deal with $\eqn{G}$. Moreover, the second proof requires slightly stronger assumptions for an asymptotic value of $d^{i+1} / n$.

\begin{theorem}\label{thm:upper_bound_pqn}
Suppose that $\omega \log n \le d=pn \le n / \omega = o(n)$, where $\omega=\omega(n)$ is any function tending to infinity as $n \to \infty$ such that $\omega \le \log n$.
Let $i=i(n) \in \mathbb{N}$ be the largest integer such that $d^i = o(n)$.
Suppose that $d^{i+1} / n - 2 \log n \to \infty$.

Then, the following property holds a.a.s.\ for $G = (V,E) \in \G(n,p)$:
$$
\pqn{G} \le k := (2+o(1)) \frac {n \log n}{d^i} = \mathcal{O} \left( \frac {n \log n}{d^i} \right).
$$
\end{theorem}
\begin{proof}
Note that we assumed that $d^{i+1} / n - 2 \log n \to \infty$ and by definition of $i$ we get that $d^{i} / n - 2 \log n \to -\infty$. Hence, by Lemma~\ref{lem:diameter} we get that the diameter of $\G(n,p)$ is equal to $i+1$ a.a.s.

\medskip

Let $\hat{\omega} = \hat{\omega}(n) = \min( \sqrt{\omega}, n/d^i )$. Clearly, $\hat{\omega} \to \infty$ as $n \to \infty$. We say that a graph $G=(V,E)$ is \emph{nice} if for any $x,y \in V$ ($x \neq y$) we have
\begin{eqnarray*}
\left| N_i(x) \setminus N_{\le i}(y) \right| &=& \left(1+ \mathcal{O} \left( \hat{\omega}^{-1} \right) \right) d^i \sim d^i, \\
\left| N_{\le i}(x) \cap N_{\le i}(y) \right| &=& \mathcal{O} \left( \hat{\omega}^{-1} \right)  d^i = o(d^i).
\end{eqnarray*}
We will show that for any nice graph $G$, $\pqn{G} \le k$ (deterministically). This will finish the proof since, by Lemma~\ref{lem:gnp exp2}(a), a.a.s.\ $G \in \G(n,p)$ is nice.

Let us then move away from random graphs and concentrate on any (deterministic) nice graph $G=(V,E)$ on $n=|V|$ vertices. The first player (the algorithm) will use a randomized strategy to play the game for the first $k$ rounds. We will show that this strategy is a winning one with probability at least $1/2$. By the trivial probabilistic method, it will imply that there exists a winning strategy and the bound $\pqn{G} \le k$ will be established. To that end, it is enough to show that for any pair of vertices $x$ and $y$, regardless of what the second player (the adversary) does, the randomized strategy eliminates at least one of them from being the target with probability at least $1-n^{-2}$. Formally, we need to show that
\begin{equation}\label{eq:distinguish_pair}
\mathbb{P} \left( \{x,y\} \subseteq V_k \right) \le n^{-2} \qquad \text{for any $x,y \in V$}.
\end{equation}
Indeed, if~\eqref{eq:distinguish_pair} is established, then by the union bound
$$
\mathbb{P}(\text{the strategy fails}) = \mathbb{P} \left( |V_k| \ge 2 \right) = \mathbb{P} \left( \exists x,y \in V : \{x,y\} \subseteq V_k \right) \le \binom{n}{2} n^{-2} \le 1/2.
$$

\medskip

Let us now describe the randomized strategy the algorithm is going to use. Fix $b > 1$, an arbitrarily large but fixed real number. The strategy consists of $a \log n$ independent \emph{phases}, where $a = 2/(b-1)$. Each phase will last for $b n / d^i$ rounds so the total number of rounds is equal to
$$
k = (a \log n) \, \frac {b n}{d^i} = \frac {2b}{b-1} \, \frac {n \log n}{d^i}.
$$
Since $2b/(b-1) \to 2$ as $b\to \infty$, we will get the desired upper bound.

At the beginning of each phase, the algorithm generates a sequence of $bn/d^i + 1$ random vertices, each of them selected independently and uniformly at random from $V$, all available vertices. During the first round, the algorithm presents the first two vertices from the sequence. Then, in each consecutive round, the algorithm presents the vertex the adversary replied with in the previous round together with the next vertex from the random sequence.

\medskip

It remains to show that~\eqref{eq:distinguish_pair} holds. Let us fix any $x,y \in V$. We partition the set of vertices $V$ into the following 4 parts:
\begin{eqnarray*}
X &=& N_i(x) \setminus N_{\le i}(y) \\
Y &=& N_i(y) \setminus N_{\le i}(x) \\
Z &=& V \setminus N_{\le i}(\{x,y\}) \\
R &=& V \setminus (X \cup Y \cup Z) = N_{\le i}(x) \cap N_{\le i}(y).
\end{eqnarray*}
Since the diameter of $G$ is $i+1$, we get that
\begin{itemize}
\item [(i)] vertices in $X$ are at distance $i$ from $x$ and at distance $i+1$ from $y$,
\item [(ii)] vertices in $Y$ are at distance $i+1$ from $x$ and at distance $i$ from $y$,
\item [(iii)] vertices in $Z$ are at distance $i+1$ from both $x$ and $y$,
\item [(iv)] vertices in $R$ are at distance at most $i$ from both $x$ and $y$.
\end{itemize}
Since $G$ is nice, we have that both $X$ and $Y$ consist of $\left(1+ \mathcal{O} \left( \hat{\omega}^{-1} \right) \right) d^i \sim d^i$ vertices and $|R| = \mathcal{O} \left( \hat{\omega}^{-1} \right) d^i = o(d^i)$. As a result, $|Z| = n - (2+o(1)) d^i \sim n$.

A given phase is \emph{good} if the following two properties hold for the random sequence of $bn/d^i + 1$ vertices the algorithm generates at the beginning of that phase:
\begin{itemize}
\item [(1)] the sequence consists of only vertices from $X \cup Y \cup Z$,
\item [(2)] the sequence has at least one vertex from $X$ and at least one vertex from $Y$.
\end{itemize}
First, let us note that if a phase is good, then the strategy guarantees that at least one of $x$ and $y$ is eliminated during that phase. Indeed, if $(u_t, v_t)$ with $u_t \in X$ and $v_t \in Y$ is presented during the first round of the phase, then, regardless what the adversary does, the goal is immediately achieved: replying with $u_t$ eliminates $y$ whereas replying with $v_t$ eliminates $x$. (We need to consider this potential situation but this is a very rare event so we should not count on it.) The properties (1)--(2) of being good, and the strategy used, imply that at some round during this phase, $(u_t, v_t)$ is presented with $u_t \in Z$ and $v_t \in X \cup Y$. By symmetry, without loss of generality, we may assume that $v_t \in X$. If the adversary replies with $u_t$, then $x$ gets eliminated: $x$ is closer to $v_t$ than to $u_t$. So assume that the adversary replies with $v_t$ which does not eliminate any of the two vertices: $x$ is closer to $v_t$ than to $u_t$ and $y$ is at the same distance from both of them. Vertex $v_t$ is kept by the algorithm and reused in the next round. During the following rounds, $v_t$ can be presented together with some other vertices from $Z$ but the only chance for $x$ not to be eliminated is that the adversary keeps replying with a vertex from $X$. (Trivially, vertex from $X$ is transferred to the next round when two vertices from $X$ are presented.) However, eventually, vertex from $X$ will be presented together with vertex from $Y$ eliminating either $x$ or $y$.

Now, we will show that at least one phase must be good with probability at least $1-n^{-2}$. Let $X$ be the random variable counting the number of vertices from $R$ that occur during a given phase. Clearly,
$$
\mathbb E [X] = \frac {|R|}{n} \left( \frac {bn}{d^i} + 1 \right) = \mathcal{O} \left( \frac {d^i}{n \hat{\omega}} \, \frac {bn}{d^i} \right) = \mathcal{O} ( \hat{\omega}^{-1} ) = o(1).
$$
Hence, by the first moment method, the probability that a given phase does not satisfy property~(1) can be estimated as follows:
$$
\mathbb{P} ( X \ge 1 ) \le \mathbb E [X] = \mathcal{O} ( \hat{\omega}^{-1} ) = o(1).
$$
On the other hand, by the union bound, the probability that a given phase does not satisfy property~(2) is at most
$$
\left( 1 - \frac {|X|}{n} \right)^{bn/d^i + 1} + \left( 1 - \frac {|Y|}{n} \right)^{bn/d^i + 1} \le 2 \exp \left( - \frac {d^i}{n} \, \frac {bn}{d^i} (1+o(1)) \right) = 2e^{-b} + o(1).
$$
Hence, all independent phases fail to be good with probability at most
\begin{eqnarray*}
\left( 2e^{-b} + o(1) \right)^{a \log n} &=& \exp \left( \Big( ( \log 2 - b ) a + o(1) \Big) \log n \right) \\
&=& \exp \left( -2 \Big( \frac {b-\log 2}{b-1} + o(1) \Big) \log n \right) \\
&\le& \exp \left( -2 \log n \right) = 1/n^{-2}.
\end{eqnarray*}
This finishes the proof of~\eqref{eq:distinguish_pair} and so also the entire proof of the theorem.
\end{proof}

Now, let us adjust the proof of Theorem~\ref{thm:upper_bound_pqn} to claim the same upper bound for $\eqn{\G(n,p)}$.

\begin{theorem}\label{thm:upper_bound_eqn}
Suppose that $\omega \log n \le d=pn \le n / \omega = o(n)$, where $\omega=\omega(n)$ is any function tending to infinity as $n \to \infty$ such that $\omega \le \log n$.
Let $i=i(n) \in \mathbb{N}$ be the largest integer such that $d^i = o(n)$. let $\hat{\omega} = \hat{\omega}(n) = \min( \sqrt{\omega}, n/d^i ) \to \infty$ as $n \to \infty$.
Finally, suppose that $d^{i+1} / n \gg \hat{\omega} \log n$.

Then, the following property holds a.a.s.\ for $G = (V,E) \in \G(n,p)$:
$$
\eqn{G} \le k := (2+o(1)) \frac {n \log n}{d^i} = \mathcal{O} \left( \frac {n \log n}{d^i} \right).
$$
\end{theorem}
\begin{proof}
We will use the same notation as in the proof of Theorem~\ref{thm:upper_bound_pqn}. As before, we will have $a \log n$ independent phases, each phase lasting for $bn/d^i$ rounds. Since the first player (the algorithm) has to present edges, we need to modify the strategy slightly. During the first round of each phase, the algorithm presents a vertex selected uniformly at random from $V$. Then, in each consecutive round, the algorithm presents the vertex the adversary replied with in the previous round together with a random neighbour of that vertex. That is the only modification that is required. As before, we investigate any deterministic nice graph and independently consider each pair of vertices $x,y$ ($x \neq y$). The goal, as before, is to show that with probability at least $1-n^{-2}$, at the end of the last phase the target cannot be hidden in both $x$ and $y$.

A given phase is good if only vertices from $X \cup Y \cup Z$ are played during that phase as well as at least one vertex from $X$ and at least one vertex from $Y$ were played.
By Lemma~\ref{lem:gnp exp}(a), we may assume that each vertex has degree asymptotic to $d$. To show that a.a.s.\ at least one phase must be good, and so a.a.s.\ the strategy is a winning strategy, we will use Lemma~\ref{lem:gnp exp2}. Let us concentrate on any given phase. By property~(c), a.a.s.\ the first vertex is selected from $Z$.
By property~(e), provided that the first endpoint of an edge is in $X \cup Y \cup Z$, the second endpoint is in $R$ with probability $o( d^{i+1} n^{-1} ) / d = o( d^{i} / n )$, which is of the same order as $|R|/n$. Since there are $\mathcal{O} (n/d^i)$ rounds in that phase, as in the previous proof, a.a.s.\ no vertex from $R$ is presented during that phase.
Similarly, by properties~(f)--(g), provided that the first endpoint of an edge is in $X \cup Z$ ($X \cup Z$, respectively), the second endpoint is in $Y$ ($X$, respectively) with probability asymptotic to $(d^{i+1} n^{-1})/d \sim d^i/n$, and so asymptotically the same as $|Y|/n$ ($|X|/n$, respectively).
Hence, conditioning on the fact that no vertex from $R$ is presented, the probability that no vertex from $Y$ ($X$, respectively) is presented is at most
$$
\left( 1 - (1+o(1)) \frac {d^i}{n} \right)^{bn/d^i + 1} \le e^{-b} + o(1).
$$
We get that a given phase fails with probability at most $2e^{-b} + o(1)$ and the argument continues as before. This finishes the proof of the theorem.
\end{proof}

Finally, let us deal with very dense random graphs, that is, when $p \in (0,1)$ is a fixed constant. The following observation follows immediately from the Chernoff's bound~\eqref{chern} (applied with $\varepsilon = c \sqrt{\log n / n}$, where $c=c(p)$ is a sufficiently large constant) and the union bound. Since the reader is already warmed-up, we skip a simple proof and leave it as an exercise.

\begin{lemma}\label{lem:gnp exp3}
Fix $p \in (0,1)$.
The following properties hold a.a.s.\ for $G = (V,E) \in \G(n,p)$.
\begin{itemize}
\item [(a)] For any vertex $x \in V$, $\deg(x) = |N_1(x)| = (1+\mathcal{O}( \sqrt{\log n / n} )) \, pn \sim pn$.
\item [(b)] For any vertices $x,y \in V$ ($x \neq y$), $|N_1(x) \setminus N_{\le 1}(y)| = (1+\mathcal{O}( \sqrt{\log n / n} )) \, p(1-p)n \sim p(1-p)n$.
\item [(c)] For any vertices $x,y,u \in V$ (pairwise distinct),
$$
| N_1(u) \cap (N_1(y) \setminus N_{\le 1}(x)) | = (1+\mathcal{O}( \sqrt{\log n / n} )) \, p^2(1-p)n \sim p^2(1-p)n.
$$
\end{itemize}
\end{lemma}

Now, we are ready to prove our last upper bound.

\begin{theorem}\label{thm:dense_graphs}
Fix $p \in (0,1)$.
The following property holds a.a.s.\ for $G = (V,E) \in \G(n,p)$:
$$
\pqn{G} \le \eqn{G} \le k := \frac {3}{p^2 (1-p)^2} \log n = \mathcal{O} \left( \log n \right).
$$
\end{theorem}
\begin{proof}
We continue using the same proof strategy as in the previous two theorems, Theorems~\ref{thm:upper_bound_pqn} and~\ref{thm:upper_bound_eqn}, but the strategy and the proof that it is a winning strategy a.a.s.\ are much easier than before. There are $a \log n$ rounds, where $a = 3 p^{-2} (1-p)^{-2}$. In each round, the first player (the algorithm) presents an edge that is generated at random, that is, the first vertex, $u$, is selected uniformly at random from $V$ and then a neighbour of $u$, vertex $v$, is selected uniformly at random from all neighbours of $u$.
As in the previous two proofs, since we aim for a statement that holds a.a.s., we may assume that properties stated in Lemma~\ref{lem:gnp exp3} hold deterministically (that is, our graph is ``nice''). We need to show that for any pair of vertices $x,y$ ($x \neq y$), the above strategy guarantees that with probability at least $1-n^{-2}$ the target cannot be hidden in both vertices.

Let us fix any pair of vertices $x,y$ ($x \neq y$). If $u \in N_1(x) \setminus N_{\le 1}(y)$ but $v \in N_1(y) \setminus N_{\le 1}(x)$ (or vice-versa), then the goal is achieved, regardless what the second player (the adversary) does. By Lemma~\ref{lem:gnp exp3}(b), $u \in N_1(x) \setminus N_{\le 1}(y)$ with probability asymptotic to $p(1-p)$. Conditioning on this event, by Lemma~\ref{lem:gnp exp3}(c), $u$ has $(1+o(1)) p^2 (1-p) n$ neighbours in $N_1(y) \setminus N_{\le 1}(x)$. Hence, by Lemma~\ref{lem:gnp exp3}(a), the (conditional) probability that $v \in N_1(y) \setminus N_{\le 1}(x)$ is asymptotic to $p (1-p)$. We get that $u \in N_1(x) \setminus N_{\le 1}(y)$ but $v \in N_1(y) \setminus N_{\le 1}(x)$ happens with probability asymptotic to $p^2(1-p)^2$. By symmetry, the same is true if $u$ and $v$ are swapped. It follows that the strategy fails with probability at most
$$
\left( 1 - (2+o(1)) p^2 (1-p)^2 \right)^{a \log n} \le \exp \left( - (2+o(1)) p^2 (1-p)^2 a \log n \right) \le n^{-2},
$$
since $a = 3 p^{-2} (1-p)^{-2}$. This finishes the proof of the theorem.
\end{proof}

\section{$\mathcal{NP}$-hardness}\label{sec:hardness}

In this section, we prove that computing the parameters $\pqn{G}$ and $\eqn{G}$ is $\mathcal{NP}$-hard for a general family of graphs, that is, for graphs of diameter at most $3$. This is done by a reduction from the $\textsc{$3$-EXACT SET COVER}$ problem: given a set of elements $A = \{a_1, \dots, a_n\}$, where $n = 3k$ for some natural number $k$, a family of sets $\mathcal{S} = \{S_1, \dots, S_m\},$ for $S_i \subseteq A$, $|S_i| = 3$ for $i \in [m]$ and $\bigcup_{i \in [m]} S_i = A$, the question is whether there exists a sub-family $\mathcal{SC} = \{S_{i_1}, \dots, S_{i_k}\}$ such that $\bigcup_{j \in [k]} S_{i_j} = A$. Note that, since $n = 3k$, if the answer to the above question is positive, then the sets in $\mathcal{SC}$ are pairwise disjoint.

For each instance of the problem, we construct a graph $G$ defined as follows. The vertex set of $G$ is defined as follows:
$$
V(G) = \{x, y\} \cup \left( \bigcup_{t \in [5]} A^t \right) \cup \left( \bigcup_{t \in [5]} \mathcal{S}^t \right) \cup L,
$$
where $A^t, \mathcal{S}^t$, for $t \in [5]$, are copies of the sets $A$ and $\mathcal{S}$, respectively, and $|L| = 5n (5(m-k)-3) = n (25 (m-k) - 15)$.  The edge set of $G$ is defined as follows (see Figure~\ref{fig:reduct} for an illustration):
\begin{enumerate}
    \item $G\left[\{y\} \cup \bigcup_{t \in [5]} A^t \right]$ induces a star centred at $y$ (isomorphic to $K_{1, 5n}$),
    \item each vertex $a \in \bigcup_{t \in [5]} A^t$ is adjacent to $5(m-k)-3$ leaves that belong to $L$,
    \item $G\left[\{x\} \cup \bigcup_{t \in [5]} \mathcal{S}^t \right]$ induces a star centered at $x$ (isomorphic to $K_{1, 5m}$),
    \item for $t \in [5[, i \in [n], j \in [m]$, vertices $a^t_i \in A^t$ and $S^t_j \in \mathcal{S}^t$ are adjacent if and only if $a_i \in S_j$ in the corresponding instance of the problem.
\end{enumerate}
For any $i \in [n]$ and $t \in [5]$, we define $L^t_i = \{a^t_i\} \cup \left(N_1 \left(a^t_i\right) \cap L\right)$, that is, the vertex set of a star centred at $a^t_i$ (isomorphic to $K_{1, 5(m-k)-3}$) defined by the second condition above.

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width = 0.8\textwidth]{fig-npc.pdf}
	\end{center}
	\caption{A reduction from the $3$-EXACT SET COVER}
	\label{fig:reduct}
\end{figure}

\begin{lemma}\label{lem:NP}
Suppose that $n > m > k + 3 = n/3+3$ for some natural number $k$. For the graph $G$ defined above, one has $\pqn{G} \le \eqn{G} \le 5m$
if and only if there exists a set cover of size $k$ for the corresponding instance of the $\textsc{$3$-EXACT SET COVER}$ problem.
\end{lemma}
\begin{proof}
($\Longleftarrow$) Suppose that the desired set cover $\mathcal{SC}= \{S_{i_1}, \dots, S_{i_k}\}$ exists. We introduce the following search strategy for the first player (the algorithm) implying that $\eqn{G} \le 5m$. Query the $5k$ edges of the form $x S^t_{i_j}$ for $t \in [5], j \in [k]$. If every single reply is $x$, then the target is on a star induced by the graph $G\left[\{x\} \cup \bigcup_{t \in [5]} \mathcal{S}^t  \setminus \bigcup_{t \in [5], j \in [k]} \left\{S^t_{i_j}\right\}\right]$ (isomorphic to $K_{1, 5(m-k)}$), and can be easily localized in the next $5(m-k)$ rounds. (Actually, it can be done faster by querying edges of the form $y a^t_i$ for some carefully selected values of $t \in [5]$ and $i \in [n]$.) The target is found in at most $5m$ rounds in total, yielding the desired upper bound for $\eqn{G}$.

Suppose then that the adversary replies with vertex $S^t_{i_j}$ at some round of the initial $5k$ queries. Without loss of generality, we may assume that it was $S^1_1$ and that this vertex is adjacent to $a^1_1, a^1_2$, and $a^1_3$. It is easy to see that the target must be in $S^1_1$, $y$, or at a vertex of some star $L^1_i$ centered at $a^1_i$ ($i \in [3]$). To locate it, the algorithm queries the 3 edges adjacent to $S^1_1$, namely, edges $S^1_1 a^1_i$ ($i \in [3]$). If $S^1_1$ is the target, then $S^1_1$ is replied 3 times in a row. On the other hand, if $y$ is the target, then $S^1_1$ is not selected by the adversary even once. Suppose then that the target is located in some vertex of a star $L^1_i$ ($i \in [3]$). Clearly, the adversary replies with $a^1_i$ when this vertex is queried and, otherwise, $S^1_1$ is selected. The algorithm learns which star needs to be investigated and the target can be found in the remaining $5(m-k)-3$ queries.
This proves that $\eqn{G}\leq 5m$ and the claim follows immediately from Observation~\ref{obs:lower}.

\medskip

($\Longrightarrow$) We will prove the implication using proof by contraposition. Suppose that there is no set cover of size $k$ for the corresponding instance of the problem. Our goal is to show that $\pqn{G} \ge 5m+1$. To that end, we will provide a strategy for the second player (the adversary) that guarantees that the target is not found after $5m$ rounds of the game, that is, $|V_{5m}| \ge 2$. In fact, we will help the first player (the algorithm) slightly and announce at the beginning of the game that the target is hidden in the set
$$
V_0 = L \cup \bigcup_{t \in [5]} A^t = \bigcup_{i \in [n], t \in [5]} L_i^t \subseteq V
$$
(instead of starting with $V_0 = V$). Note that $G[V_0]$ is a family of $5n$ independent stars, each isomorphic to $K_{1, 5(m-k)-3}$. Even with that additional information, the algorithm will not be able to find the target in $5m$ rounds.

We consider two phases of the game. The first phase lasts for $5k + 4$ rounds. We will show that at the end of this phase, there exists at least one star $L_i^t$ with the property that the target can be at any vertex of that star; that is, $L_i^t \subseteq V_{5k+4}$. Here is a strategy for the adversary. Suppose that for some $i \in [5k + 4]$ the algorithm queried a pair $u_i$ and $v_i$ at round $i$.
\begin{enumerate}
    \item $u_i = y$ and $v_i = a^t_j$ for some $j \in [n], t \in [5]$. The adversary replies with $y$. Then, $V_{i-1} \setminus V_i = V_{i-1} \setminus \mathcal{C}(y, a^t_j) \subseteq L^t_j$. At most one star is eliminated.
    \item $u_i = y$ and $v_i \not \in \bigcup_{t \in [5]} A^t$. The adversary replies with $y$. Then, only $v_i$ is eliminated, provided $v_i \in L$. At most one star is (partially) eliminated.
    \item $u_i = x$ and $v_i \in L^t_j$ for some $j \in [n], t \in [5]$. The adversary replies with $x$. Then, $V_{i-1} \setminus V_i = V_{i-1} \setminus \mathcal{C}(x, v_i) \subseteq L^t_j$. At most one star is eliminated.
    \item $u_i = x$ and $v_i = S^t_\ell$ for some $\ell \in [m], t \in [5]$. Let $S_\ell = \{a_{\ell_1}, a_{\ell_2}, a_{\ell_3}\}$. The adversary replies with $x$. Then, $V_{i-1} \setminus V_i = V_{i-1} \setminus \mathcal{C}(x, S^t_\ell) \subseteq L^t_{\ell_1} \cup L^t_{\ell_2} \cup L^t_{\ell_3}$. At most three stars are eliminated.
    \item $u_i = S^t_\ell$ and $v_i = S^s_j$ for some $\ell, j \in [m]$ and $t, s \in [5]$. Let $S_\ell = \{a_{\ell_1}, a_{\ell_2}, a_{\ell_3}\}$. The adversary replies with $v_i$. Then, $V_{i-1} \setminus V_i = V_{i-1} \setminus \mathcal{C}(v_i, S^t_\ell) \subseteq L^t_{\ell_1} \cup L^t_{\ell_2} \cup L^t_{\ell_3}$. At most 3 stars are eliminated. Note that this is equivalent to the previous case ($x$ vs.\ $S^t_\ell$).
    \item $u_i = S^t_\ell$ and $v_i \in L^s_j$ for some $\ell, j \in [m]$ and $t, s \in [5]$. Let $S_\ell = \{a_{\ell_1}, a_{\ell_2}, a_{\ell_3}\}$. The adversary replies with $v_i$. Then, $V_{i-1} \setminus V_i = V_{i-1} \setminus \mathcal{C}(v_i, S^t_\ell) \subseteq L^t_{\ell_1} \cup L^t_{\ell_2} \cup L^t_{\ell_3}$. At most 3 stars are eliminated. Again, note that this is equivalent to the previous case ($x$ vs.\ $S^t_\ell$), provided $t \neq s$ or $a_j \not \in S_\ell$. If $t = s$ and $a_j \in S_\ell$, then at most two stars are eliminated.
    \item $u_i = a^t_j$ and $v_i \in L^s_\ell$ for some $j, \ell \in [m]$ and $t, s \in [5]$. The adversary replies with $a^t_j$. Then $V_{i-1} \setminus V_i = V_{i-1} \setminus \mathcal{C}(a^t_j, v_i) \subseteq L^s_\ell$, that is, at most one star is eliminated. When $s = t$ and $j = \ell$ then only $v_i$ is eliminated. In any case, at most one star is (partially) eliminated.
    \item $\{u_i, v_i\} \in L$. Let $v_i \in L^t_j$ for some $j \in [n], t \in [5]$. The adversary replies with $u_i$. Then $V_{i-1} \setminus V_i = V_{i-1} \setminus \mathcal{C}(u_i, v_i) \subseteq L^t_j$. (In particular, if $u_i \in L^t_j$, then only $v_i$ is eliminated.) At most one star is (partially) eliminated.
\end{enumerate}

Note that each query described above eliminates at most three stars, either entirely or partially. Moreover, all stars that are eliminated belong to one of the five copies of the sets $A$. More importantly, since there is no cover set of size $k$ for the corresponding instance of the problem, the algorithm cannot eliminate all $3k$ stars from one copy in $k$ queries (restricted to those that affect this copy). Hence, after $5k+4$ rounds, there is at least one star (say, $L^t_j$ centered at $a^t_j$) that may hide the target, that is, $L^t_j \subseteq V_{5k+4}$.

The strategy for the second phase is very easy. In every round of this phase, the adversary replies with a vertex that is closer to $a^t_j$ (or any vertex if both vertices that are queried are at the same distance from $a^t_j$). Clearly, at most one vertex of $L^t_j$ is eliminated in each round. Hence, since the star consists of $5(m-k)-2$ vertices, after $5(m-k)-4$ additional rounds, at least two vertices are still left in $V_{5m}$ and so the game is not over yet. This finishes the proof that $\pqn{G} \ge 5m+1$, and we are done.
\end{proof}

Since both our search problems are in $\mathcal{NP}$ (the strategy length is trivially bounded from above by the order of the graph; see also Observation~\ref{obs:lower}), Lemma~\ref{lem:NP} implies immediately Theorem~\ref{thm:NP}.