Hardness of Finding Kings and Strong Kings

Towards a contradiction, suppose $u$ is not a strong king. Then, there must exist some vertex $v$ such that $v\to u$ and $\delta (v,u)\ge \delta (u,v)$.

Define $W=\{w\in V\setminus \{u,v\}:u\to w\text{ and }v\to w\}$. Note that $d^{+}(u)=\delta (u,v)+|W|$ and $d^{+}(v)=\delta (v,u)+|W|+1>d^{+}(u)$, which is a contradiction since we assumed $u$ to be a maximum-out-degree vertex. $◀$

A set of vertices $S\subseteq V$ is a dominating set in $T=(V,E)$ if, for every $v\in V$, either $v\in S$ or there exists $w\in S$ such that $w\to v$. A dominating pair is a dominating set of exactly two vertices.

We show both directions below.

• $\mathrm{■}$

  Let us first show the implication ($\Rightarrow$): that is, any pair $\{i,j\}$ where $j=n-1$ is dominating. According to Construction 8, and as depicted in Figure 1, vertex $n-1$ dominates all vertices except $n-2$. However, it is easy to see that all other vertices are either $n-2$ or dominate $n-2$. Therefore, pairing $n-1$ with any of those vertices produces a dominating pair.

• $\mathrm{■}$

  To show the implication in the other direction ($\Leftarrow$), assume, for the sake of contradiction, that $j\ne n-1$ and $\{i,j\}$ is a dominating pair. Then, $i\in {[n-2]}_0$ and either $j\in {[n-2]}_0$, or $j=n-2$ (recall that ).

  • –

    If $j\in {[n-2]}_0$, then $\{i,j\}$ does not dominate $n-1$, a contradiction.

  • –

    If $j=n-2$, then $i\in {[n-2]}_0$ must dominate all other vertices in ${[n-2]}_0$, and thus must be a source in ${\mathrm{\Delta }}_n[{[n-2]}_0]$. However, since all (of the at least 3) vertices in ${\mathrm{\Delta }}_n[{[n-2]}_0]$ are kings by Lemma 9, this contradicts Lemma 5. Thus, the pair $\{i,j\}$ is not a dominating pair.

This concludes the proof. $◀$

Simply, the only dominating pairs in ${\mathrm{\Delta }}_n$ are $\{0,n-1\},\{1,n-1\},\mathrm{\dots },\{n-2,n-1\}$. Using the above property, we show below that the deterministic and randomized query complexity of finding a king in an arbitrary $n$-vertex digraph is $\mathrm{\Theta }(n^2)$.

The upper bound is trivial. Assume that $n$ is odd. If $n$ is even, an argument similar to that given in the last paragraph of the proof of Theorem 18 can be used. Let $A=({[n]}_0,E_A)$ be an arbitrary balanced tournament on $n$ vertices. Consider the $n$-vertex tournament ${\mathrm{\Delta }}_n$ from Construction 8 and relabel all vertex labels by adding $n$ to them. Let the resultant graph be called $A^{\prime }$. Construct a tournament $C$ on $2n$ vertices labelled in ${[2n]}_0$ as follows:

1. 1.

   Consider the disjoint union of $A$ and $A^{\prime }$, and

2. 2.

   add edges from every vertex in $A$ to vertex $(2n-1)$ in $A^{\prime }$.

Figure 3 illustrates the construction of $C$. Clearly, $C$ does not have a king: indeed, no vertex in $A^{\prime }$ reaches any vertex in $A$, and every vertex in $A$ dominates $(2n-1)$, which does not dominate $(2n-2)$ (by construction, see Construction 8).

For $i\in {[n]}_0$ and $j\in {[n-1]}_0$, define $C_{i,j}$ as the tournament obtained by adding the edge $i\to (n+j)$ in $C$. Observe that $i$ is a king in $C_{i,j}$, since:

• $\mathrm{■}$

  $i$ 2-step dominates all vertices in $A$ (as $C_{i,j}[A]$ is a balanced tournament), and

• $\mathrm{■}$

  $i$ dominates $(2n-1)$ and $n+j$, which form a dominating pair in $C_{i,j}[A^{\prime }]$ by Lemma 13.

Define the distribution $\mu$ on $2n$-vertex tournaments as follows:

Equivalently, $\mu$ can be defined by the following sampling procedure: Start with the tournament $C$; then, with probability $1/2$, do nothing, or, with probability $1/2$, add a uniformly random (over $i\in {[n]}_0$ and $j\in {[n-1]}_0$) edge $i\to n+j$. Towards a contradiction using Lemma 7, let $𝒜$ be a deterministic algorithm with cost less than $n^2/100$ that decides whether a king exists in digraphs w.r.t. $\mu$ of error $\le 1/3$.

Consider the computation path taken by $𝒜$ that answers all edges consistent with $C$, and answers $0$ (i.e., “no edge present”) to all queries of the form $i\to j$ for $i\in [n]$, $j\in \{n,n+1,\mathrm{\dots },2n-1\}$. We consider two cases.

1. 1.

   Suppose the output at this leaf of $𝒜$ is $1$ (i.e., “a king exists”). The algorithm errs on the input $C$, which has a $\mu$-mass of 1/2. This is not possible since we assumed $𝒜$ to make an error of at most $1/3$ w.r.t. $\mu$.

2. 2.

   Suppose the output at this leaf of $𝒜$ is $0$ (i.e., “no king exists”). Since the number of queries on this path was assumed to be at most $n^2/100$, there must be at least $99n^2/100-n$ edges of the form $i\to (n+j)$ that have not been queried, where $i\in {[n]}_0$ and $j\in {[n-1]}_0$. For each such $i,j$, the graph $C_{i,j}$ also follows this computation path. However, the vertex $i$ is a king in $C_{i,j}$. Hence $𝒜$ errs on $C_{i,j}$. Thus, the total error made by $𝒜$ is at least $(\frac{99n^2}{100}-n)\cdot \frac{1}{2n(n-1)}>1/3$ for sufficiently large $n$. This again contradicts our assumption that $𝒜$ made error at most $1/3$ w.r.t. $\mu$, and hence the theorem follows.

This concludes the proof. $◀$

As an easy corollary, we obtain the same deterministic lower bound for determining the existence of a king in a digraph.

Define the parity function $p(x)=x(mod2)$. From the proof of Lemma 11, each vertex $i$ in $U_n$ dominates all lesser vertices of the same parity as $i$, and all greater vertices of opposite parity.

• $\mathrm{■}$

  Assume that $j>i$. Since $j\to i$, Construction 10 implies $p(j)=p(i)$. The vertex $j$ dominates all vertices with $p(v)=p(i)$ and all vertices $w>j$ with $p(w)\ne p(i)$.

  To count length-2 paths from $i$ to $j$, we first show that if $i\to v\to j$, then .

  • –

    If , then $p(v)=p(i)$ (since $i\to v$), but also $p(v)\ne p(j)$ (since $v\to j$ and ), contradicting $p(i)=p(j)$.

  • –

    If $v>j$, then $p(v)\ne p(i)$ (since $i\to v$), but also $p(v)=p(j)$ (since $v\to j$ and $v>j$); again, a contradiction.

  Thus, $v$ must satisfy , and since $i\to v$, it follows that $p(v)\ne p(i)$. This means .

  Using nearly the same argument, one can show that .

• $\mathrm{■}$

  The case where follows from the case where $j>i$ by symmetry (Lemma 12). Indeed, let $i^{\prime }$ and $j^{\prime }$ be the new labels of $i$ and $j$ in $\sigma (U_n,n-i)$, respectively. Then, , and given that $\sigma (U_n,n-i)\in \mathrm{Aut}(U_n)$, the lemma follows.

Therefore, we have $\delta (i,j)-\delta (j,i)=\frac{j-i}{2}-(\frac{j-i}{2}-1)=1$. $◀$

For the tournament $U_n$ and a vertex $v$ of it, define $D(v)$ be the set of edges such that, if the direction of exactly one edge in $D(v)$ were flipped, $v$ would no longer be a strong king.

Now, we show that $|D(v)|=\mathrm{\Theta }(n^2)$.

We show below that $|D(0)|=(n^2-1)/4$. The result for general $v$ immediately follows by symmetry (Lemma 12), as $|D(0)|=|D(1)|=\mathrm{\cdots }=|D(n-1)|$.

We first consider the effect of flipping an edge connected to 0.

• $\mathrm{■}$

  Let $j\in {[n]}_0$ be odd. The construction of $U_n$ ensures the direction of the edge between $0$ and $j$ to be $0\to j$. Flipping $(0,j)$ decreases $\delta (0,n-1)$ by 1 as the path $0\to j\to n-1$ is gone, and does not affect $\delta (n-1,0)$.

• $\mathrm{■}$

  Let $k\in {[n]}_0\setminus \left\{0\right\}$ be even. The construction of $U_n$ ensures the direction of the edge between $0$ and $k$ to be $k\to 0$. Flipping the $(k,0)$ edge cannot increase $\delta (j,0)$ for any $j$, and cannot decrease $\delta (0,j^{\prime })$ for any $j^{\prime }$. Since 0 was a strong king in $U_n$, this means 0 is a strong king in the new tournament with $(k,0)$ flipped as well.

The first case above contributes $(n-1)/2$ elements to $D(0)$. Next, we consider the effect of flipping an edge between $j$ and $k$ where $j\ne 0$ and $k\ne 0$.

• $\mathrm{■}$

  If $j$ and $k$ are both odd, then neither of them is an in-neighbor of $0$, and hence 0 remains a strong king.

• $\mathrm{■}$

  If $j$ and $k$ are both even and $j\to k$ is flipped, the construction of $U_n$ ensures that $j>k$, and both $j,k$ are in-neighbors of $0$. We have $\delta (k,0)$ increase by 1 due to the new path $k\to j\to 0$, and $\delta (0,k)$ is unchanged as $j\to 0$. By Lemma 16, the new tournament now has $\delta (k,0)=\delta (0,k)$, and hence 0 is no longer a strong king.

• $\mathrm{■}$

  If $j$ is even and $k>j$ is odd, the direction of the edge between $j$ and $k$ is $j\to k$. The vertex $j$ is an in-neighbor of $0$, and $k$ is not. Flipping the edge increases $\delta (0,j)$ by 1 due to the new path $0\to k\to j$, and $\delta (j,0)$ is unaffected. No other values of $\delta (0,\cdot )$ or $\delta (\cdot ,0)$ are affected for in-neighbors of 0. Thus, 0 remains a strong king in this case.

• $\mathrm{■}$

  The final case is when $j$ is odd and $k>j$ is even. Recall that $k$ is an in-neighbor of 0. We have $\delta (0,k)$ reduce by 1 due to the removal of the path $0\to j\to k$ (as the $j\to k$ edge is now flipped), and $\delta (k,0)$ is unaffected. By Lemma 16, we have $\delta (0,k)=\delta (k,0)$ in the new tournament, and hence 0 is no longer a strong king.

The number of edges from the second case above equals the number of ways of choosing two even numbers, none of which is 0: this is $\left(\genfrac{}{}{0pt}{}{(n-1)/2}{2}\right)$. The number of edges from the fourth case is the number of choices of an odd vertex and a higher even vertex, which equals $(n-1)/2+(n-3)/2+\mathrm{\cdots }+1=(n^2-1)/8$. Combining the above, we have

This concludes the proof. $◀$

We now analyze the randomized query complexity of ${\text{STRONG-KING}}_n$.

The upper bound is trivial. Assume that $n$ is odd. For $i,j\in {[n]}_0$, let $U_n^{i,j}$ denote the tournament that is obtained from $U_n$ by flipping the direction of the edge between $i$ and $j$. Consider $\mu$ to be the following distribution on $n$-vertex tournaments:

Towards a contradiction using Lemma 7, let $𝒜$ be a deterministic algorithm with cost less than $c\cdot n(n-1)$ (for some constant $c\in (0,1)$ to be fixed later in the proof, it will turn out that any works) computing ${\text{STRONG-KING}}_n$ to error less than $1/3$ when inputs are drawn from the distribution $\mu$. Consider the computation path of $𝒜$ that outputs the answers of all queries consistently with the input $U_n$. Say the output at this leaf of $𝒜$ is vertex $v$. The algorithm errs on all inputs of the form $U_n^{i,j}$ where $(i,j)\in D(v)$ (recall that $D(v)$ consists of precisely those edges that, on being flipped in $U_n$, cause $v$ to no longer be a strong king). There are at least $|D(v)|-cn(n-1)$ such edges $(i,j)$ which are unqueried (and thus $U_n^{i,j}$ reaches this leaf). The error probability of $𝒜$ is at least its error probability on this leaf, which by Lemma 17 is at least $\frac{1}{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}\left(\frac{n^2-1}{4}-cn(n-1)\right)>\frac{2}{n(n-1)}\left(\frac{n(n-1)}{4}-cn(n-1)\right)=\frac{1-4c}{2}>1/3$ for . Lemma 7 yields the required lower bound.

The proof can be easily made to work for the case where $n$ is even by assuming that one vertex is a sink, and applying the argument above on the subtournament induced on the remaining vertices (this sink vertex does not affect the proof above in any way). $◀$

A deterministic lower bound follows as an immediate corollary.