Proof. Let \(\mathcal{A}\) be the optimal (randomized/quantum) algorithm for the problem \(\mathtt{P}'\). We first construct a new algorithm \(\mathcal{B}\) with majority voting, where we run \(\mathcal{A}\) on the same input a total of \(\Theta(\log(1/p))\) times, so that it decides between yes and no inputs with probability at least \(1-p/4\).

Now, we run the algorithm \(\mathcal{B}\) on an instance \(G'\) generated through the randomized reduction. Then, if \(G\) is a positive input, this procedure will succeed with probability at least \(p(1-p/4) > 3p/4\), whereas if \(G\) is a negative input, this procedure will succeed with probability at most \(p/4\). Thus, by running this procedure a total of \(\Theta(1/p)\) times, we can distinguish between these two cases with high probability. As such, the total number of calls to \(\mathcal{A}\) is \(\Theta((1/p)\log(1/p))\), which is constant as \(p \in \Omega(1)\). Thus, \(\mathsf{M}(\mathtt{P}) \in O(\mathsf{M}(\mathtt{P}'))\), for \(\mathsf{M} \in \{\mathsf{Q},\mathsf{R}\}\). ◻

Proof. For the upper bound, we randomly divide the free vertices \([n] \setminus \{1, \dots, m\}\) into \(\ell\) groups \(I_1, \dots, I_{\ell}\) of size \(\Theta(n/\ell)\), and we define the subgraphs \(G_{\ell'}\) as the input graph restricted to \(I_{\ell'} \cup \{i^{\ell'}_1, \dots, i^{\ell'}_{m_{\ell'}}\}\), for all \(\ell' \in [\ell]\). If \(H\) was not present in \(G\), then there must be an \(\ell' \in [\ell]\) such that \(H_{\ell'}\) is not present in \(G_{\ell'}\). On the other hand, if \(H\) was present in \(G\), then with constant probability, \(H_{\ell'}\) will be contained in \(G_{\ell'}\) for all \(\ell' \in [\ell]\). Thus, we now use 2 to argue that \[\mathsf{M}\left(\mathtt{Subgraph}^{H,v_1, \dots, v_m}_{[n],1,\dots,m}\right) \in O\left(\mathsf{M}\left(\bigwedge_{\ell'=1}^{\ell} \mathtt{Subgraph}^{H_{\ell'},v_{i_1^{\ell'}}, \dots, v_{i_{m_{\ell'}}^{\ell'}}}_{I_{\ell'} \cup \{i^{\ell'}_1, \dots, i^{\ell'}_{m_{\ell'}}\}, i_1^{\ell'}, \dots, i_{m_{\ell'}}^{\ell'}}\right)\right).\] Finally, we use that \(\ell\) is constant, and \(\mathsf{M}(\mathtt{P}_1 \land \mathtt{P}_2) \in \Theta(\max\{\mathsf{M}(\mathtt{P}_1), \mathsf{M}(\mathtt{P}_2)\})\), for total problems \(\mathtt{P}_1\) and \(\mathtt{P}_2\).

For the lower bound, suppose that \(\ell' \in [\ell]\) maximizes the expression on the right-hand side. Suppose we have an input on \(n\) vertices for the \(\mathtt{Subgraph}^{H_{\ell'}}_{[n],v_{i_1^{\ell'}}, \dots, v_{i_{m_{\ell'}}^{\ell'}}}\) problem. Then, we add a constant number of vertices \(n_0 \in \Theta(1)\) containing the subgraphs \(H_{\ell''}\) for all \(\ell'' \in [\ell] \setminus \{\ell'\}\). Now, the new input contains \(H\) if and only if the original input contains \(H_{\ell'}\), and so \(\mathsf{M}(\mathtt{Subgraph}^H_{[n+n_0],v_1,\dots,v_m}) \geq \mathsf{M}(\mathtt{Subgraph}_{[n],v_{i_1^{\ell'}}, \dots, v_{i_{m_{\ell'}}^{\ell'}}})\). ◻

Proof. In the first case, there is only one possibility for the injective map, and so we simply (deterministically) check whether all the required edges exist in the input.

In the second case, let \(V_H \setminus \{v_1, \dots, v_m\} = \{w_1, \dots, w_{\ell}\}\). Similar to the proof of 3, the query complexity is upper bounded by searching for an image of each of the vertices \(w_{\ell'}\) individually, for \(\ell' \in [\ell]\). As for each \(\ell' \in [\ell]\), checking whether a given vertex plays the role of \(w_{\ell'}\) takes \(O(1)\) (deterministic) queries, the total query complexity is \(O(\sqrt{n})\) in the quantum setting and \(O(n)\) in the randomized setting.

In the third case, we have the trivial upper bound of \(O(n^2)\) in the randomized setting, because we can simply learn the entire input with \(\binom{n}{2} \in \Theta(n^2)\) queries.

For the lower bounds, observe in the second case that we can consider an input that contains all edges except for the ones that are connected to \(w_1\). Now, we can reduce a search problem of size \(n\) to this subgraph containment problem, and so we find that \(\mathsf{Q}(\mathtt{Subgraph}^H_{v_1, \dots, v_m}) \in \Omega(\sqrt{n})\) and \(\mathsf{R}(\mathtt{Subgraph}^H_{v_1, \dots, v_m}) \in \Omega(n)\).

Finally, in the third case, we can embed all of \(H\) except for the connections between \(v\) and \(w\), with \(\{v,w\} \in E_{H - \{v_1, \dots, v_m\}}\). Now, we add \(n\) candidate vertices for \(v\) and \(n\) candidate vertices for \(w\), and we connect them up to their respective neighbors in \(H\). Now, we can embed a search problem on \(\binom{n}{2}\) items into the bipartite graph between the candidate vertices for \(v\) and \(w\). Hence, we find that \(\mathsf{Q}(\mathtt{Subgraph}^H_{v_1, \dots, v_m}) \in \Omega(\sqrt{\binom{n}{2}}) = \Omega(n)\) and \(\mathsf{R}(\mathtt{Subgraph}^H_{v_1, \dots, v_m}) \in \Omega(\binom{n}{2}) = \Omega(n^2)\). ◻

Proof. It is clear that \(\mathsf{M}(\mathtt{Subgraph}^H_{v1,\dots,v_m}) \in O(\mathsf{M}(\mathtt{FindSubgraph}^H_{v_1, \dots, v_m}))\), since we can run an algorithm for the finding problem, and then output \(1\) if its output was non-zero. Thus, it remains to prove the reverse direction. In the randomized setting, it is clear that the finding versions of the subgraph containment problems follow the same classification as in 4, since in the second case, we can learn the entire neighborhoods for all the vertices \(v_1, \dots, v_m\) with \(O(n)\) queries, and that is sufficient to find the subgraph, if it exists. Thus it remains to focus on the quantum setting.

To that end, observe that if we are in the first case of 4, there is only one possible place where \(H\) could be embedded in the input, and so the finding version of the subgraph-containment problem also has constant query complexity as well. thus without loss of generality we are in the second or third case in 4. Now, we describe a randomized reduction that solves the finding problem, using the detection algorithm as a black box. To that end, suppose that for every \(n \in \mathbb{N}\), the optimal algorithm makes \(T_n\) quantum queries to the input to solve the \(\mathsf{Subgraph}_{[n],1, \dots, m}^{H,v_1, \dots, v_m}\)-problem. It is immediate that \((T_n)_{n=1}^{\infty}\) is increasing, since we can always trivially embed an instance of \(n\) vertices into an instance with \(n+1\) vertices by ignoring one of the vertices in the input.

Then, by considering an integer \(\ell > 1\), we can embed an OR of \(\ell\) disjoint instances of the boolean function \(\mathtt{Subgraph}^{H,v_1, \dots, v_m}_{[n],1, \dots, m}\) into \(\mathrm{Subgraph}^{H,v_1, \dots, v_m}_{[m+\ell(n-m)],1,\dots,m}\), and so \[\begin{align} \mathsf{Q}(\mathtt{Subgraph}^{H,v_1, \dots, v_m}_{[m + \ell (n-m)],1,\dots,m}) &\geq \mathsf{Q}(\mathtt{OR}_{\ell} \circ \mathtt{Subgraph}^{H,v_1, \dots, v_m}_{[n],1,\dots,m}) \\ &\in \Theta(\sqrt{\ell} \cdot \mathsf{Q}(\mathtt{Subgraph}^{H,v_1, \dots, v_m}_{[n],1, \dots, m})), \end{align}\] where in the last step we use that quantum query complexity is multiplicative under composition up to constants [28]. Thus, \(T_{m + \ell(n-m)} \in \Omega(\sqrt{\ell} \cdot T_n)\) and so by fixing \(\ell \in \mathbb{N}\) large enough, we obtain that \(T_{\ell n} \geq T_{m + \ell(n-m)} \geq KT_n\) for large enough \(n\), for some constant \(K > 1\). We will without loss of generality also assume that \(\ell > 9\).

Now, we consider the finding problem of size \(\ell n\). We can randomly choose \(n\) of the \(\ell n\) available vertices, and remove all the others. Then, if \(H\) was present in the original input, it will still be present in the new input with probability at least \(\Omega(\ell^{-|V_H|}) = \Omega(1)\), where we use that \(n\) is large enough. On the other hand, if \(H\) was not present in the original input, it will still not be present in the new input. Thus, using the generic amplification procedure, 2, we can with \(O(T_n)\) queries build a procedure that outputs \(0\) if \(H\) is not present in the graph, and that outputs a subset of size \(n\) that contains \(H\) if it is, with probability at least \(5/6\). Then, in the latter case we can subsequently run the finding routine with size \(n\) on this subset, with three runs and certificate checking to have a failure probability of at most \(1/6\) in this step as well. The total cost of the finding routine, which we denote by \(F_{\ell n}\), then satisfies for some constant \(C > 0\), \[F_{\ell n} \leq C \cdot T_n + 3 F_n.\] Now since \(T_n\) satisfies the regularity condition, as we argued earlier, and since \(\log_\ell(3) < 1/2\) and \(T_n \in \Omega(\sqrt{n})\) by 4, we can use the master theorem [29] to conclude that \(F_n \in O(T_n)\), and so \(\mathsf{Q}(\mathtt{FindSubgraph}^H_{v_1, \dots, v_m}) \in O(\mathsf{Q}(\mathtt{Subgraph}^H_{v_1, \dots, v_m}))\). ◻

Proof. We provide a randomized reduction. Indeed, suppose that we have an instance to the undirected version of the subgraph containment problem. We now generate an input to the directed version of the problem by randomly associating a direction to each edge. We observe that if \(H\) was not present in the undirected input, then \(\vec{H}\) will definitely also not be present in the new input. On the other hand, if \(H\) was present in the original input, now \(\vec{H}\) will be contained in the new input with probability at least \(2^{-|E_H|} \in \Omega(1)\). Thus, we can now use the generic amplification procedure 2 to solve the undirected version of the problem, with constant overhead. ◻

Proof. As \(\mathtt{Subgraph}^{H'}\) is a boolean function on \(|V|(|V|-1)\) bits, we can also interpret it as a function on \(\binom{V}{2}\) \(2\)-tuples, where the \(2\)-tuple labeled by \(\{v,w\}\) contains the information whether the arcs \((v,w)\) and \((w,v)\) are present in the input. Now, we have \[\mathtt{Subgraph}^{H'} : \{0,1\}^{\binom{V}{2}} \to \{0,1\}, \qquad \text{and} \qquad \mathtt{Subgraph}^H : (\{0,1\}^2)^{\binom{V}{2}} \to \{0,1\}.\]

In particular, we observe that the index labels into the input are now the same. We argue that on top of that, the certificate structures for both functions, as defined in [30], are also the same. To that end, observe that both graph properties are monotone, and so all the minimal positive certificates contain exactly a single copy of \(H'\) and \(H\), respectively. As such, we conclude that the (non-adaptive) learning-graph complexities for both problems are also equal, due to [30].

Finally, we observe that the two learning-graph algorithms presented in [4] are both non-adaptive. As such, the upper bound stated in 1 is in fact an upper bound on the non-adaptive learning graph complexity of the undirected subgraph-containment problem with subgraph \(H'\). This means it is also an upper bound on the non-adaptive learning graph complexity for the directed subgraph-containment problem with subgraph \(H\), which in turn upper bounds \(\mathsf{Q}(\mathtt{Subgraph}^H)\). ◻

Proof. It is clear that \(\mathsf{Q}(\mathtt{PromP}) \in O(\mathsf{Q}(\mathtt{P}))\), because the function that is to be computed in the promise version of the problem is a restriction of the one in the non-promise problem. The same follows for \(\mathsf{Q}(\mathtt{PromFindP}) \in O(\mathtt{FindP})\) by comparing the relations to one another. Thus, it remains to show the reverse direction in the finding case.

To that end, suppose that we have an instance of the \(\mathtt{FindP}\)-problem. Any accepting instance will also be a valid instance for the promise version as well, and so in that case the algorithm for \(\mathtt{PromFindP}\) should output a valid path with high probability. In the rejecting case, though, the promise might not be satisfied, so the promise problem could output anything. However, we can simply check whether the path it outputs actually exists in the graph, and reject if not. Since in the rejecting case no path exists, this procedure always rejects, and it adds only constant additive overhead to the query complexity. ◻

Proof. Given a graph instance \(G = (V,E)\) of \(\mathtt{DirPath}^{= \ell}_{s,t}\), we construct a graph instance \(G' =(V,E')\) of \(\mathtt{DirPath}^{= k}_{s,t}\) using the color-coding technique as follows. Color \(s\) with color \(0\), color \(t\) with color \(k\), and for each vertex \(v\) in \(V \setminus \{s,t\}\), color \(v\) uniformly at random from \([\ell-1]\) colors. For each \(v \in V\), let \(c(v)\) denote the color of \(v\). Choose a color \(i^* \in [\ell-1]\) and make \(k-\ell\) copies of each vertex colored \(i^*\). For each \(j \in [k-\ell+1]\), let \(v_j\) denote the \(j\)th copy of the vertex \(v\) with \(c(v) = i^*\). For all vertices \(v\) with \(c(v) = i^*\) and \(j \in [k-\ell]\), add edges \((v_j,v_{j+1})\) in \(E'\). For each edge \((u,v) \in E\) with \(c(v) = c(u) + 1\), add an edge \((u,v)\) if \(c(u),c(v) \neq i^*\), add an edge \((u_{k-\ell+1},v)\) in \(E'\) if \(c(u) = i^*\) and add an edge \((u,v_1)\) if \(c(v) = i^*\). It is easy to see that if \(G\) has a directed \(s-t\) path of length \(=\ell\), \(G'\) will have a directed \(s-t\) path of length \(=k\) with probability at least \(1/(\ell-1)^{\ell-1} \in \Omega(1)\), and if \(G\) did not have a directed \(s-t\) path of length \(=\ell\), then \(G'\) will not have a directed \(s-t\) path of length \(=k\). Invoking 2 proves the desired claim. ◻

Proof. We will prove all these statements one by one via reductions.

1. Given a graph instance \(G = (V,E)\) of \(\mathtt{Path}^{=k}_{s,t}\), we construct a graph instance \(G' =(V,E')\) of \(\mathtt{Path}^{\leq k}_{s,t})\) using the color-coding technique as follows. Color \(s\) with color \(0\), color \(t\) with color \(k\), and for each vertex \(v\) in \(V \setminus \{s,t\}\), color \(v\) uniformly at random from \([k-1]\) colors, and for each edge \({u,v} \in E\), add \(\{u,v\}\) in \(E'\) if \(u\) and \(v\) have consecutive colors. If \(G\) had an \(s-t\) path of length \(=k\), \(G'\) will have an an \(s-t\) path of length \(=k\) with probability at least \(1/(k-1)^{k-1} \in \Omega(1)\), and if \(G\) did not have an \(s-t\) path of length \(=k\), then \(G'\) will not have it either. Moreover, any \(s-t\) path in \(G'\) will be of length at least \(k\). Invoking 2 proves the desired statement.

2. This follows from a reduction similar to 6 and invoking 2.

3. From 8, we have that \(\mathsf{Q}(\mathtt{DirPath}^{= \ell}_{s,t})) \in O(\mathsf{Q}(\mathtt{DirPath}^{= k}_{s,t}))\) for all \(3 \leq \ell \leq k\). To decide if \(G\) has a directed \(s-t\) path of length \(\leq k\), we loop over all \(3 \leq \ell \leq k\) and run the above procedure to decide if \(G\) has a directed \(s-t\) path of length \(=\ell\), and output yes if it outputs yes for any \(\ell \in [k]\).

4. Given a graph instance \(G = (V,E)\) of \(\mathtt{DirPath}^{= k}_{s,t}\), we construct a graph instance \(G' =(V,E')\) of \(\mathtt{Path}^{= k}_{s,t}\) using the color-coding technique as follows. Color \(s\) with color \(0\), color \(t\) with color \(k\), and for each vertex \(v\) in \(V \setminus \{s,t\}\), color \(v\) uniformly at random from \([k-1]\) colors, and for each edge \((u,v) \in E\), add \(\{u,v\}\) in \(E'\) if \(c(v) = c(u) + 1\). Now, note that if \(G\) has a directed \(s-t\) path of length \(=k\), \(G'\) will have an \(s-t\) path of length \(=k\) with probability at least \(1/(k-1)^{k-1} \in \Omega(1)\), and if \(G\) did not have a directed \(s-t\) path of length \(=k\), then \(G'\) will not have an \(s-t\) path of length \(=k\). Invoking 2 proves the desired statement.

 ◻

Proof. We will prove both these statements via reductions.

1. Given a graph instance \(G = (V,E)\) of \(\mathtt{DirPath}^{= k}\), we construct a graph instance \(G' =(V \cup \{s,t\},E')\) of \(\mathtt{DirPath}^{= k+2}_{s,t}\) using the color-coding technique as follows. For each vertex \(v\) in \(V\), color \(v\) uniformly at random from \([k+1]\) colors, and for each edge \((u,v) \in E\), add it in \(E'\) if \(c(v) = c(u) + 1\). Also add edges \((s,v)\) for all vertices \(v\) with color \(1\) and edges \((v,t)\) for all vertices \(v\) with color \(k+1\). Now, note that if \(G\) has a directed path of length \(=k\), \(G'\) will have a directed \(s-t\) path of length \(=k+2\) with probability at least \(1/(k+1)^{k+1} \in \Omega(1)\), and if \(G\) did not have a directed path of length \(=k\), then \(G'\) will not have a directed \(s-t\) path of length \(=k+2\). Invoking 2 proves the desired statement.

2. Given a graph instance \(G = (V,E)\) of \(\mathtt{DirPath}^{= k}_{s,t}\), we construct a graph instance \(G' =(V \setminus \{s,t\},E')\) of \(\mathtt{DirPath}^{= k-2}\) using the color-coding technique as follows. For each vertex \(v\) in \(V \setminus \{s,t\}\), color \(v\) uniformly at random from \([k-1]\) colors, and for each edge \((u,v) \in E\) with \(u,v \notin \{s,t\}\), add \((u,v)\) in \(E'\) if \(c(v) = c(u) + 1\) and either \(c(u) \neq 1\) and \(c(v) \neq k-1\) or \(c(u) = 1\) and \((s,u) \in E\) or \(c(v) = k-1\) and \((v,t) \in E\). Now, note that if \(G\) has a directed \(s-t\) path of length \(=k\), \(G'\) will have a directed path of length \(=k-2\) with probability at least \(1/(k-1)^{k-1} \in \Omega(1)\), and if \(G\) did not have a directed path of length \(=k\), then \(G'\) will not have a directed \(s-t\) path of length \(=k+2\). Invoking 2 proves the desired statement.

 ◻

Proof. We will prove all these statements one by one via reductions.

1. Note that the promise of \(\mathtt{PromDirPath}^{=k}_{s,t}\) is stronger than the promise of \(\mathtt{PromDirPath}^{\leq k}_{s,t})\) since the yes and no instances of the former are also yes and no instances of the latter respectively. Thus, an algorithm for the latter will also be an algorithm for the former.

2. This follows directly by the definitions of \(\mathtt{PromDirPath}^{\leq k}_{s,t}\) and \(\mathtt{DirPath}^{\leq k}_{s,t}\).

3. This follows from [pt:3] of 17.

4. Given a graph instance \(G = (V,E)\) of \(\mathtt{DirPath}^{= k}_{s,t}\), we construct a graph instance \(G' =(V,E')\) of \(\mathtt{PromDirPath}^{= k}_{s,t}\) using the color-coding technique as follows. Color \(s\) with color \(0\), color \(t\) with color \(k\), and for each vertex \(v\) in \(V \setminus \{s,t\}\), color \(v\) uniformly at random from \([k-1]\) colors, and for each edge \((u,v) \in E\), add \((u,v)\) in \(E'\) if \(c(v) = c(u) + 1\). Now, note that any directed \(s-t\) path in \(G\) of length \(\neq k\) will not be preserved in \(G'\). Thus, \(G'\) is a valid instance of \(\mathtt{PromDirPath}^{= k}_{s,t}\). Also, any directed \(s-t\) path of length \(=k\) in \(G\) is preserved in \(G'\) with probability at least \(1/(k-1)^{k-1} \in \Omega(1)\). Therefore, invoking 2 proves the desired statement.

 ◻

Proof. The proof is identical to 7. ◻

Proof. We prove all these statements one by one via reductions.

1. We will prove that, for any \(\ell \in [k]\setminus \{1,2\}\), \(\mathsf{Q}(\mathtt{DirCycle}^{=\ell})\in O(\mathsf{Q}(\mathtt{DirCycle}^{=k}))\). Let \(G = (V,E)\) be the input of \(\mathtt{DirCycle}^{= \ell}\), we construct an \((\ell,k-\ell)\)-color cyclic construction corresponding to \(G\) as sketched in 7; let us denote the resultant directed graph by \(G'' =(V'',E'')\). If \(G\) has a directed cycle of length \(=\ell\) then \(G''\) will have a directed cycle of length \(=k\) with probability at least \(1/\ell^{\ell} \in \Omega(1)\). In any other case, \(G''\) will not have any directed cycle of length \(=k\). Invoking 2 proves that for any \(\ell \in [k]\setminus \{1,2\}\) we have \(\mathsf{Q}(\mathtt{DirCycle}^{=\ell}) \in O(\mathsf{Q}(\mathtt{DirCycle}^{=k}))\).

2. The argument for showing \(\mathsf{Q}(\mathtt{PromDirCycle}^{=\ell}) \in O(\mathsf{Q}(\mathtt{PromDirCycle}^{= k}))\) for any \(\ell \in [k]\setminus \{1,2\}\) is via the same reduction that is stated in the proof of [item:MonotonicityDirCycle]. What remains to be established is that the promise for \(\mathtt{PromDirCycle}^{= k}\) is not “badly” violated for any of the reduced instances. Let \(G\) be the input instance of \(\mathtt{PromDirCycle}^{=\ell}\). Let \(G''\) denote a \((\ell,k-\ell)\)-color cyclic construction corresponding to \(G\).

   1. \(G\) is a no instance of \(\mathtt{PromDirCycle}^{=\ell}\). This means there is no directed cycle of any length in \(G\) and, note that the construction of \(G''\) doesn’t create any new cycles. This means that \(G''\) constructed from such a \(G\) will also not have any cycle. Hence, a no instance of \(\mathtt{PromDirCycle}^{=\ell}\) maps to a well-defined promise-satisfying no instance of \(\mathtt{PromDirCycle}^{= k}\).

   2. \(G\) is a yes instance of \(\mathtt{PromDirCycle}^{=\ell}\). First observe that, When \(G\) is a yes instance of \(\mathtt{PromDirCycle}^{=\ell}\) then with probability \(\Omega(1)\) the constructed \(G''\) will also be a promise-satisfying yes instance of \(\mathtt{PromDirCycle}^{= k}\). For the remaining fraction, the \(\ell\)-length cycle from \(G\) is not preserved due to the random color coding but other length \(>\ell\) cycles could be present. Which would then translates to no cycle of length \(=k\) to be present in \(G''\) but length \(>k\) cycles being present in \(G''\), and this is not in the promise of \(\mathtt{PromDirCycle}^{= k}\).

   Inspite of the occasional violation of promise in the yes case, the reduction can be made to work. When \(G\) is a no instance the constructed \(G''\) fully satisfies the promise for \(\mathtt{PromDirCycle}^{= k}\) while being a no instance itself. And, \(G''\) satisfies the promise for \(\mathtt{PromDirCycle}^{= k}\) while being a yes instance with probability \(\Omega(1)\) when \(G\) is a yes instance. Therefore, running an algorithm for \(\mathtt{PromDirCycle}^{= k}\) on \(G''\) for \(O(1)\) many times is sufficient to deduce whether or not \(G\) is a yes or a no instance with high probability. This concludes the argument.

3. Let \(G=(V,E)\) be an undirected graph that is input to \(\mathtt{Cycle}^{\leq(k-1)}\). Let \(\mathcal{A}\) denote an algorithm for \(\mathtt{Cycle}^{\leq k}\). We loop over \(\ell \in [k-1]\) and run \(\mathcal{A}\) on \(G''(\ell)\) where \(G''(\ell)\) denotes a random \((\ell,k-\ell)\)-cyclic construction of \(G\). If \(\mathcal{A}\) outputs no for \(G''(\ell)\) for all \(\ell \in [k-1]\) (more precisely, for constant many constructions of \(G''(\ell)\) for each \(\ell\)) then we know that \(G\) has cycles of only length \(>k-1\) and therefore we output no. On the other hand, if \(\mathcal{A}\) outputs yes on any of the above runs then that is because either there was a \(\leq (k-1)\) cycle in \(G\) that got encoded in one of the \(G''(\ell)\) with probability \(> 1/\ell^{\ell} \in \Omega(1)\) for at least one \(\ell \in [k-1]\) or there was length-\(k\) cycle in the original graph \(G\) that survived in \(G''\). Fortunately, enforcing \(k\) is odd ensures that any valid length-\(k\) cycle in \(G''\) passes through the color-coded layers and as well as the inserted dummy layers which then corresponds to some length-\(\ell\) (where \(\ell < k\)) cycle of \(G\). Without enforcing that \(k\) is odd we cannot get rid of the original length-\(k\) cycles of \(G\). Finally, invoking 2 concludes the proof.

The argument for monotonicity for \(\mathtt{P}_{s}\) where \(\mathtt{P} \in \{\mathtt{DirCycle},\mathtt{PromDirCycle},\mathtt{Cycle}\}\), works in the same way as above except for the difference that while constructing \((\ell,k-\ell)\)-color cyclic construction, the color coding construction goes through \(s\) as described in 6. Note that, this difference changes the exact probability of success for mapping the yes instances to yes instances but is still \(\Omega(1)\). ◻

Proof. We will prove all these statements one by one via reductions.

1. First, we prove \(\mathsf{Q}(\mathtt{DirCycle}^{=k}) \in O(\mathsf{Q}(\mathtt{DirCycle}^{\leq k}))\). We want to decide if a directed input graph \(G=(V, E)\) has a directed cycle of length \(=k\) using an algorithm \(\mathcal{A}\) that decides whether a directed graph has a cycle of length \(\leq k\). We construct a \(k\)-color cyclic construction of \(G\) as sketched in 6; let us denote the resultant graph (which is a directed graph) as \(G'=(V',E')\). If \(G\) had a directed cycle of length \(k\) then \(G'\) will also have a cycle of length \(=k\) with probability at least \(1/k^k \in \Omega(1)\), and if \(G\) did not have a directed cycle of length \(k\) then \(G'\) will not have it either. Moreover, any cycle in \(G'\) will be of length at least \(k\). Invoking 2 proves the desired direction.

   In the other direction, from [item:MonotonicityDirCycle] of 10 we have a reduction that establishes \(\mathsf{Q}(\mathtt{DirCycle}^{=\ell}) \in O(\mathsf{Q}(\mathtt{DirCycle}^{=k}))\) for any \(\ell \in [k]\setminus \{1,2\}\). To decide if \(G\) has a directed cycle of length \(\leq k\), we loop over all \(\ell \in [k]\setminus \{1,2\}\) and run the above procedure to decide if \(G\) has a directed cycle of length \(=\ell\), and output yes if it outputs yes for any \(\ell \in [k]\setminus \{1,2\}\). Hence, proving that \(\mathsf{Q}(\mathtt{DirCycle}^{\leq k}) \in O(\mathsf{Q}(\mathtt{DirCycle}^{=k}))\).

2. The reductions to prove both these relations are similar to the arguments presented for [item:DirCycleEqLeqk]. What remains to be argued is that the arguments hold in the promise setting as well. To prove the relation \(\mathsf{Q}(\mathtt{PromDirCycle}^{= k})\in O(\mathsf{Q}(\mathtt{PromDirCycle}^{\leq k}))\) we use the same idea of its non-promise counterparts. It is easy to see that when \(G\) (the input for \(\mathtt{PromDirCycle}^{= k}\)) is a no instance then because of the promise there will be no cycle of any length in \(G\) which means \(G'\) (the input for \(\mathtt{PromDirCycle}^{\leq k}\)) will also have no cycles as the construction doesn’t create new cycles. When \(G\) is a yes instance, \(G'\) is also a yes instance with probability \(\Omega(1)\). Even though the promise of \(\mathtt{PromDirCycle}^{\leq k}\) may not be satisfied for the rest of the times, invoking 2 concludes the argument.

   To show the other relation, i.e., \(\mathsf{Q}(\mathtt{PromDirCycle}^{\leq k}) \in O(\mathsf{Q}(\mathtt{PromDirCycle}^{= k}))\), we invoke [item:PromMonotonicityDirCycle] of 10 and then use the same reduction used for its non-promise counterparts as stated in [item:DirCycleEqLeqk].

3. We will show that \(\mathsf{Q}(\mathtt{Cycle}^{\leq k}) \in O(\mathsf{Q}(\mathtt{Cycle}^{=k}))\). Let \(G\) be the input to \(\mathtt{Cycle}^{\leq k}\). The idea is to loop over \(\ell \in [3,k]\) and construct an \((\ell,k-\ell)\)-cyclic construction of \(G\) (as sketched in 7) for every value of \(\ell \in [3,k]\); let the constructed instance be denoted by \(G''(\ell)\). The idea is to now run an algorithm for \(\mathtt{Cycle}^{=k}\), let us denote by \(\mathcal{A}\), on every \(G''(\ell)\) and output yes if \(\mathcal{A}\) outputs yes on \(G''(\ell)\) for any value of \(\ell \in [3,k]\), otherwise output no. This reduction works because of the following reasons. Suppose that \(G\) did not contain any cycle of length \(\leq k\), i.e., \(G\) is a no instance of \(\mathtt{Cycle}^{\leq k}\). Then either \(G\) contains cycles of length \(>k\) or no cycle at all. In either of the cases none of the \(G''(\ell)\)s will not contain a cycle of length \(=k\) because the construction enforces that no new cycles are created and the length of the cycles (if present) in \(G\) doesn’t decrease in length. This means a no instance of \(\mathtt{Cycle}^{\leq k}\) maps to a no instances of \(\mathtt{Cycle}^{=k}\). On the other hand, if \(G\) was a yes instance of \(\mathtt{Cycle}^{\leq k}\) then \(G''(\ell)\) will be a yes instance of \(\mathtt{Cycle}^{=k}\) with probability \(>1/\ell^{\ell} \in \Omega(1)\) for at least one \(\ell \in [3,k]\). Finally, invoking 2 concludes the proof.

   (It is beneficial to note that the reduction in the other direction doesn’t hold; at least we don’t know how to prove it yet. Mainly, because we don’t know how to get rid of smaller cycles.)

4. The relation \(\mathsf{Q}(\mathtt{PromCycle}^{\leq k}) \in O(\mathsf{Q}(\mathtt{PromCycle}^{=k}))\) follows from the definitions of the respective promise problems, along with the reduction we use for [item:CycleEqLeqk] and by invoking 2.

   For the other direction, \(\mathsf{Q}(\mathtt{PromCycle}^{=k}) \in O(\mathsf{Q}(\mathtt{PromCycle}^{\leq k}))\), we run the \(\mathtt{PromCycle}^{\leq k}\) algorithm on the \(k\)-color cyclic construction of \(G=(V,E)\), let us denote by \(G'=(V',E')\) where \(G\) is the input to the \(\mathtt{PromCycle}^{=k}\) problem. The promise on our input \(G\) ensures that there won’t be any cycle in the no case so running algorithm for \(\mathtt{PromCycle}^{\leq k}\) on \(G'\) will give no. And, in the yes case the construction \(G'\) will have a cycle of length \(k\) with probability \(> 1/k^k \in \Omega(1)\). Invoking 2 gives us the desired result.

5. We will now argue \(\mathsf{Q}(\mathtt{DirCycle}^{=k}) \in O(\mathsf{Q}(\mathtt{Cycle}^{=k})\) holds for odd values of \(k\). Let \(G=(V,E)\) be an input to \(\mathtt{DirCycle}^{=k}\) problem. We first construct a \(k\)-color cyclic construction of \(G\), let us denote it by \(G'=(V',E')\). Note that \(G'\) will also be a directed graph and will contain a directed cycle of length \(=k\) with probability at least \(1/k^k \in \Omega(1)\). Moreover, if at all \(G'\) contains directed cycles then it will be of length at least \(k\) and furthermore “cycles” with inconsistent edge directions won’t exist in \(G'\) because of the color-coding. We now construct an undirected simple graph from \(G'\), let us denote by \(G''=(V'',E'')\). We do so by forgetting the directions of all the edges in \(E'\). We then run an algorithm for \(\mathtt{Cycle}^{=k}\) on \(G''\). If \(k\) is even, then forgetting the edge directions in \(G'\) could induce undirected cycles of length \(=k\) that were not present in the directed \(G'\); for example - a cycle could be just a multipartite matching between a few adjacent colors. But this is not a problem in the case when \(k\) is odd because any multipartite matching would only induce cycles of even length. Invoking 2 gives us the desired relation.

For [item:promCleqkNonprom,item:promDirCleqkNonprom], the relations follow from a straightforward application of 9. And, for [item:CEqKDir,item:ClEqKdir,item:PromCEqKPromDir], the relations follow from 6. ◻

Proof. The reductions for [item:DirCycleEqLeqks,item:PromDirCycleEqLeqks,item:CycleEqLeqksPartA,Item:PromCycleEqLeqks] follow (almost) exactly via the reductions used for their problem counterparts in 20 where the subgraph doesn’t have to go through vertex \(s\). The only change needed here is that we use the color coding construction that goes through \(s\) as described in 6; this difference changes the exact probability of success for yes instances but is still \(\Omega(1)\) as required.

For the item in [item:CycleEqLeqksPartB] we want to argue that \(\mathsf{Q}(\mathtt{Cycle}^{=k}_{s}) \in O(\mathsf{Q}(\mathtt{Cycle}^{\leq k}_{s}))\). Let \(G=(V,E)\) and \(s \in V\) be the input to \(\mathtt{Cycle}^{=k}_{s}\). The main idea for this reduction is to try and get rid of all the small (i.e., length \(<k\)) cycles in \(G\). Towards establishing that, we first learn the neighborhood of \(s\) with \(n\) queries to \(G\); let us denote its neighborhood by \(N(s)\). As \(\mathsf{Q}(\mathtt{Cycle}^{=k}_{s}) \in \Omega(n)\) from 4 we can now treat our input \(G,s\) as \(G,s\) equipped with query-free access to \(N(s)\). We will now construct an instance \(G'=(V',E')\) from \(G=(V,E)\) in the following way. For every \(w \in N(s)\), we assign \(w\) to one of the three groups, let us denote by \(N^{\texttt{red}}(s),N^{\texttt{yellow}}(s),N^{\texttt{blue}}(s)\), uniformly at random. Consequently, \(N(s)=N^{\texttt{red}}(s) \sqcup N^{\texttt{yellow}}(s) \sqcup N^{\texttt{blue}}(s)\). Set \(V'=V\setminus N(s)\). For every \(\{u,v\} \in E\) add it to \(E'\) only when \(u,v \notin N(s)\cup\{s\}\). We now add vertices \(r,b\) in \(V'\); here \(r,b\) corresponds to a vertex after “contracting” the vertices in \(N^{\texttt{red}}(s),N^{\texttt{blue}}(s)\), respectively. Add \(\{s,r\}, \{s,b\}\) to \(E'\) and additionally for every \(\{u,v\} \in E\) such that \(u \in N^{\texttt{red}}(s)\) and \(v \neq s\) add \(\{u,r\}\) to \(E'\). Similarly,for every \(\{u,v\} \in E\) such that \(u \in N^{\texttt{blue}}(s)\) and \(v \neq s\) add \(\{u,b\}\) to \(E'\). We now construct \(G''=(V'',E'')\) by color-coding \(G'=(V',E')\) by assigning colors \(1,2,k\) to \(s,r,b\), respectively and color coding the rest of the vertices into the rest of the \(k-3\) colors as done in other reductions. We can now run an algorithm for \(\mathtt{Cycle}^{\leq k}_{s}\) on \(G'',s\). First note that any cycle in \(G''\) going through \(s\) (if present) has to pass through both \(r,b\) and therefore must is of length \(\geq k\). If there is a cycle of length \(=k\) in \(G\) (yes instance) then with probability \(\Omega(1)\) there will be a cycle of length \(=k\) through \(s\) in \(G''\) and the algorithm will output yes. If there was no cycle through \(s\) in \(G\) then \(G''\) also has no cycle through \(s\) because the construction doesn’t create new cycles. Moreover, any smaller cycles in \(G\) passing through \(s\) don’t survive in \(G''\). And, cycles of length \(>k\) in \(G\) map to no instance of \(G'',s\) either by not surviving or by being too long. Therefore, the reduction maps the no instance \(G,s\) to a no instance \(G'',s\). Invoking 2 concludes the argument.

For the relation in [item:dirCycleEqkCycleEqks], i.e., towards proving \(\mathsf{Q}(\mathtt{DirCycle}^{=k}_{s}) \in O(\mathsf{Q}(\mathtt{Cycle}^{=k}_{s}))\), we use a similar trick as done in [item:CycleEqLeqksPartB]. Let \(G=(V,E)\) be a directed graph that is input to \(\mathtt{DirCycle}^{=k}_{s}\). We first learn the neighborhood of \(s\) using \(n\) queries and that is fine because \(\mathsf{Q}(\mathtt{DirCycle}^{=k}_{s}) \in \Omega(n)\); see 4. Now we construct \(G''=(V'',E'')\) exactly as we did in the previous argument except that the constructed graph is directed. We now forget the directions of the edges in the constructed graph and then running an algorithm for \(\mathtt{Cycle}^{=k}_{s}\) on this graph suffices. If \(G\) was a no instance then the final constructed graph undirected-\(G''\) is also a no instance because undirected-\(G''\) will have cycles of length \(>k\). And in the case when \(G\) is a yes instance then the final constructed graph undirected-\(G''\) is also a yes instance with probability \(\Omega(1)\). Invoking 2 concludes the proof.

For the relation in [item:PromDirCycleEqksDirCycleEqks], one direction is straightforward application of 9. We now argue the other direction, i.e., \(\mathsf{Q}(\mathtt{DirCycle}^{=k}_{s}) \in O(\mathsf{Q}(\mathtt{PromDirCycle}^{= k}_{s}))\). Let the directed graph \(G=(V,E)\) and vertex \(s\) be the input to \(\mathtt{DirCycle}^{=k}_{s}\) problem. We first construct a \(k\)-color cyclic construction of \(G\) through \(s\) using 6. Let us denote this new directed graph by \(G'=(V',E')\). Note that, the construction ensures if \(G'\) has any cycle then it will only have cycles of length \(=k\) and not any other integral multiples of \(k\) because there is only one single vertex of color \(0\) in \(G'\) (which is \(s\)) and to have any bigger cycle in \(G'\) one needs to have another vertex \(\neq s\) of color \(0\), which is not possible because of the construction. Which means the graph \(G'\) either has a directed cycle of length \(=k\) through \(s\), which happens with probability \(\Omega(1)\) when the original graph \(G\) has a length \(=k\) cycle, or \(G'\) has no directed cycle passing through \(s\) when \(G\) is a no instance. These requirements perfectly align with the promise of \(\mathtt{PromDirCycle}^{= k}_{s}\). Therefore, it suffices to run an algorithm for \(\mathtt{PromDirCycle}^{= k}_{s}\) on \(G'\) to solve \(\mathtt{DirCycle}^{=k}_{s}\) on \(G\). And, invoking 2 gives us the desired relation.

For [item:promCleqkNonproms,item:promDirCleqkNonproms], the relations follow from a straightforward application of 9. And, for [item:PromCEqKPromDirs,item:CEqKDirs,item:ClEqKdirs], the relations follow from 6. ◻

Proof. Let the graph \(G=(V,E)\) and vertex \(s\) be the input to the \(\mathtt{DirCycle}^{=k}_{s}\) problem. We construct a \(k\)-color cyclic construction of \(G\) through \(s\) as described in 6; let us denote the resultant graph as \(G'=(V',E')\). The construction ensures that the only directed cycles of length \(=k\) that go through \(s\) has a chance to survive in \(G'\). Hence, running an algorithm \(\mathtt{DirCycle}^{=k}\) on \(G'\) will detect such a cycle (if it existed in \(G\)) with probability \(\Omega(1)\) and if there were no cycles of length \(=k\) in \(G\) through \(s\) then \(G'\) will also not have any cycle of length \(k\). Invoking 2 concludes the proof. Thus, \(\mathsf{Q}(\mathtt{DirCycle}^{=k}_{s}) \in O(\mathsf{Q}(\mathtt{DirCycle}^{=k}))\).

Observe that, the reduction described earlier can also be used to strengthen the result in their respective promise versions. Consequently, implying \(\mathsf{Q}(\mathtt{PromDirCycle}^{= k}_{s}) \in O(\mathsf{Q}(\mathtt{PromDirCycle}^{= k}))\). ◻

Proof. Let the graph \(G=(V,E)\) and vertex \(s\) be the input to \(\mathtt{DirCycle}^{=k}_{s}\). Construct a new directed \(G'=(V',E')\) in the following way:

1. set \(V'=V \sqcup \{t\}\) where \(t\) denotes a new vertex that is not already present in \(V\);

2. for every \((u,v) \in E\) with \(v\neq s\), keep \((u,v)\) in \(E'\) and for all \((u,s) \in E\) create edge \((u,t)\) in \(E'\). Basically, we are directing all the incoming edges of \(s\) to \(t\) in our new graph \(G'\).

Observe that, every length-\(\ell\) directed cycle in \(G\) passing through \(s\) maps to a length-\(\ell\) \(s \rightarrow t\) path in \(G'\). Moreover, no other \(s \rightarrow t\) paths are created in \(G'\) in this process. Therefore, with this construction, we can solve \(\mathtt{DirCycle}^{=k}_{s}\) on \(G,s\) by solving \(\mathtt{DirPath}_{s,t}^{=k}\) on graph \(G',s,t\). ◻

Proof. Let the graph \(G=(V,E)\) along with the vertices \(s,t\) be the input to \(\mathtt{PromDirPath}_{s,t}^{=k}\). We will construct a directed graph \(G'=(V',E')\) by first setting \(V'=V\). Color \(s\) with \(0\) and color \(t\) with \(k\). Additionally, for all \(v \in V'\setminus \{s,t\}\) assign a color from \([k-1]\) chosen uniformly at random. And, for each edge \((u,v) \in E\), add \((u,v)\) to \(E'\) if \(c(v)=c(u)+1\). We now construct \(G''=(V'',E'')\) from \(G'\) by merging the vertices \(s,t\) into say \(s''\) - basically means, for all edges \((s,u) \in E'\) add edge \((s'',u)\) to \(E''\) and for all \((u,t) \in E'\) add edge \((u,s'')\) to \(E''\). We will run the algorithm for \(\mathtt{PromDirCycle}^{= k}_{s}\) on graph \(G''\) and vertex \(s''\).

Let us now see why the reduction holds. The yes instance of \(\mathtt{PromDirPath}_{s,t}^{=k}\) constructs a yes instance \(G'\) to \(\mathtt{PromDirPath}_{s,t}^{=k}\) with probability \(1/(k-1)^{k-1} \in \Omega(1)\). And, a yes instance \(G'\) maps to a yes instance \(G''\) of \(\mathtt{PromDirCycle}^{= k}_{s}\) with probability \(1\). Moreover, the construction ensures that there are no directed cycles that go through only \(s\) or only \(t\) in graph \(G'\) because \(s\) only contains outgoing edges and \(t\) only contains incoming edges in \(G'\) - this means if algorithm for \(\mathtt{PromDirCycle}^{= k}_{s}\) on \(G'',s''\) outputs yes then there is corresponding \(s \rightarrow t\) path of length \(k\) in \(G'\) (and hence in \(G\)). Additionally, the promise of \(\mathtt{PromDirPath}^{=k}_{s,t}\) ensures that if there is no \(s \rightarrow t\) path in \(G\) then there is no path at all from \(s \rightarrow t\) in \(G\). This promise is satisfied even in the color coded version \(G'\) and satisfies the promise for \(\mathtt{PromDirCycle}^{= k}_{s}\) as well. Therefore, invoking 2 gives us the desired relation. ◻

Proof. To prove \(\mathsf{Q}(\mathtt{PromCycle}^{=k}_{s}) \in O(\mathsf{Q}(\mathtt{PromPath}_{s,t}^{=k}))\), we use the following argument. Let the graph \(G=(V,E)\) and vertex \(s\) be the input of \(\mathtt{PromCycle}^{=k}_{s}\). We construct graph \(G'=(V',E')\) from \(G=(V,E)\) in the following way:

1. set \(V'=V \sqcup \{t\}\) where \(t\) is a new vertex that was not present in \(V\);

2. for every \(\{u,v\} \in E\) such that \(u\neq s\) and \(v \neq s\), add the edge \(\{u,v\}\) in \(E'\), and, for every \(\{u,s\} \in E\), choose uniformly at random to either add \(\{u,s\}\) to \(E'\) or (exclusive or) to add \(\{u,t\}\) to \(E'\).

We will run the algorithm for \(\mathtt{PromPath}_{s,t}^{=k}\) on graph \(G'=(V',E')\) and vertices \(s,t\). Observe that, if there was a length-\(k\) cycle through \(s\) in graph \(G\) then with probability \(1/2 \in \Omega(1)\) there will be length \(k\) path between \(s,t\) in \(G'\). In the case where the algorithm for \(\mathtt{PromPath}^{=k}_{s,t}\) outputs yes then there are two distinct neighbors of \(s\) in the original graph \(G\) with a path of length \(k-2\) which means there is a cycle through \(s\) in \(G\). Invoking 2 concludes the reduction. ◻

Proof. Let graph \(G=(V,E)\) and vertices \(s,t\) be the input to \(\mathtt{PromPath}_{s,t}^{=k}\). Using \(2n\) many queries to \(G\), we learn the neighborhood of \(s,t\) which we denote by \(N(s), N(t)\), respectively. It is fine to do so because \(\mathtt{PromPath}_{s,t}^{=k} \in \Omega(n)\). We will now construct an instance \(G'=(V',E')\) from \(G=(V,E)\) in the following way. For every \(u \in N(s)\), we assign \(u\) to one of the two groups, let us denote by \(N^{\textit{red}},N^{\textit{yellow}}\), uniformly at random. Similarly, for every \(v \in N(t)\setminus N(s)\), we assign \(v\) to either \(N^{\textit{yellow}}\) or to a new group, let us denote by \(N^{\textit{blue}}\), uniformly at random. Similarly to the idea in [item:CycleEqLeqksPartB] of 22 we construct a new graph \(G'=(V',E')\) by contracting all the vertices in \(N^{\textit{red}},N^{\textit{blue}}\) and denoting them as \(r,b\), respectively and preserving all the edges from \(E\) to \(E'\) that are incident on \(N^{\textit{red}},N^{\textit{blue}}\) (except the ones to \(s,t\)) as edges to/from \(r,b\), respectively. We also add all the edges from \(E\) in \(E'\) that don’t involve any of the vertices in \(\{s,t\}\cup N(s) \cup N(t)\) as either of its end points. Additionally, we add the edges \(\{r,s'\}, \{b,s'\}\) to \(E'\). To solve \(\mathtt{PromPath}_{s,t}^{=k}\) on \(G\) we now run an algorithm for \(\mathtt{PromCycle}^{=k}_{s}\) on \(G',s'\). If \(G\) has a length \(k\) path between \(s,t\) then with probability \(\Omega(1)\) there will be a length \(k\) cycle through \(s'\) in graph \(G'\). If \(G\) is a no instance then because of the promise there is no path between \(s,t\) in \(G\) and the construction ensures that there is no cycle (of any length) going through \(s'\) in graph \(G'\). Invoking 2 concludes the proof. ◻

Proof. For the negative case, we observe that the new graph \(G'\) only contains a subset of the arcs in \(G\). Therefore, if the original graph \(G\) does not contain a directed path of length \(k\), then neither does \(G'\).

For the positive case, we observe that every vertex obtains any given color with probability \(1/(k+1)\). Thus, the probability that every vertex in the directed path receives the correct color is \((k+1)^{-(k+1)} \in \Omega(1)\). ◻

Proof. We use a quantum walk. To that end, we first construct the graph that we will be walking over.

Let \(J_1\) be the Johnson graph of all subsets of size \(s\) from \(V_1\). Similarly, let \(J_{k-1}\) be the Johnson graph of all subsets of size \(s\) from \(V_{k-1}\). We will be walking over the Cartesian product of these graphs, i.e., \(G = J_1 \Box J_{k-1}\). We compute the spectral gap of \(G\) as \[\delta(G) = \min\{\delta(J_1), \delta(J_{k-1})\} = \frac{n}{s(n-s)} \in \Theta\left(\frac{1}{s}\right).\]

Now, we describe the marked set. We say that a vertex of \(G\), denoted by \((W_1, W_{k-1})\) where \(W_1 \subseteq V_1\) and \(W_{k-1} \subseteq V_{k-1}\) is marked whenever there exits a directed path of length \(k\) from \(V_0\) to \(V_k\) that passes through \(W_1\) and \(W_{k-1}\). If there exists one such path, then we easily compute that the fraction of marked vertices, i.e., \(\varepsilon\), satisfies \[\varepsilon \geq \frac{\binom{|V_1|-1}{s-1}}{\binom{|V_1|}{s}} \cdot \frac{\binom{|V_{k-1}|-1}{s-1}}{\binom{|V_{k-1}|}{s}} = \frac{s}{|V_1|} \cdot \frac{s}{|V_{k-1}|} \in \Theta\left(\left(\frac{s}{n}\right)^2\right).\]

Next, we desribe the data structure that we store along the way. At every vertex \((W_1,W_{k-1})\), we store for every vertex \(v \in W_1\) whether it can be reached from at least one vertex in \(V_0\), and similarly for every vertex \(v \in W_{k-1}\) whether there exists an edge going from \(v\) to a vertex in \(V_k\). Since these are simple search problems, we observe that the setup cost becomes \(\mathsf{S} \in O(s\sqrt{r})\), and since in the update routine we always only exchange a constant number of vertices, we have \(\mathsf{U} \in O(\sqrt{r})\). Finally, the checking routine, is the recursive procedure that only considers the vertices in \(W_1\) and \(W_{k-1}\) that are marked in the database, which results in a checking cost \(\mathsf{C} = C_{n,s}^{(k-2)}\).

Now, plugging everything into the MNRS-framework, i.e., 15, yields the claimed result. ◻

Proof. We first observe that if \(k = 1\), then we simply need to search over \(\binom{r}{2}\) possible edges, which requires \(O(r) = O(n^{\alpha_r}) = O(n^{\alpha_{1,r}})\) queries.

Next, for \(k = 2\), then we first search for the middle vertex, and then check whether there is a connection from the middle vertex to both the first and last layer. This requires a number of queries that satisfies \(O(\sqrt{nr}) = O(n^{\frac{1}{2} + \frac{1}{2}\alpha_r}) = O(n^{\alpha_{2,r}})\).

Then, for every \(k\), we observe by induction and 12 that the number of queries required to solve the layered-path problem with length \(k+2\) and first and last layer size \(r\) satisfies \[\begin{align} C_{n,r}^{(k+2)} &\in \widetilde{O}\left(\min_{\substack{s \in \mathbb{N}\\ 1 \leq s \leq n}} s\sqrt{r} + \left(\frac{n}{s}\right)\left(\sqrt{sr} + C_{n,s}^{(k)}\right)\right) \\ &\subseteq O\left(\min_{\alpha_s \in [0,1]} n^{\alpha_s + \frac{1}{2}\alpha_r} + n^{1-\frac{1}{2}\alpha_s+\frac{1}{2}\alpha_r} + n^{1-\alpha_s+\alpha_{k,s}}\right) = O(n^{\alpha_{k+2,r}}). \end{align}\]

Thus, it remains to solve the recurrence relation. To that end, we prove the following claim:

For future reference, we compute the first few values for \(x_k\) and \(y_k\).

Finally, we plug in \(r = n\), and hence \(\alpha_r = 1\), to conclude that \(\alpha_{k,n} = x_k + y_k \in 3/2 - \Theta(c^{-k})\), where \(c \approx 1.33\). ◻

Proof. We combine 11 with 2 to obtain that solving the layered path-finding problem with length \(k\) and first and last layer size \(n\) is sufficient for finding a directed path of length \(k\) in a directed graph. The result then follows from plugging in \(r = n\) in 13. ◻

Proof. Our algorithm is very similar to that of 29 by [5]. The checking cost of their quantum walk procedure is \(0\) since their walk database contains a \(k\)-cycle whenever a vertex is marked. In a nutshell. for the \(k\)-cycle problem, we improve the complexity of the setup and update steps in their walk at the cost of increasing the checking complexity (which will still be bounded by the complexity corresponding to the setup and update steps). We provide the algorithm and the complexity analysis for completeness.

We use 1 to decide if the number of edges \(m\) in the input graph is at least \(\overline{m}\) or at most \(\overline{m}/3\) edges with probability at least \(1-1/n\) using \(\widetilde{O}(\sqrt{n^2/\overline{m}}) \subseteq \widetilde{O}(\sqrt{n})\) queries. If this procedure accepts, we accept; otherwise, we suppose that \(m \in O(\overline{m})\) and proceed as follows.

We will assume that \(k\) is odd since for the case when \(k\) is even, we get the desired result directly from 11.

We will partition the vertex set \(V\) into \(\lceil \log n \rceil\) many parts according to its degree. We will not explicitly compute this partition; instead, we will maintain the relevant information about this partition in our quantum walk (as we explain below).

For \(i \in [\ell]\), fix \(p_i \in [\lceil \log n \rceil]\) and \(q_i = 2^{p_i}\). We will describe an algorithm for determining if there are vertices \(v_i\) for \(i \in [\ell]\) with degree close to \(q_i\) (i.e. \([q_i/2, 3q_i/2]\)) such that \(v_1, \dots, v_\ell\) are non-adjacent vertices of a \(k\)-cycle. We can run this procedure for all \(\lceil \log n \rceil^\ell\) tuples of length \(\ell\) comprising of elements from \([\lceil \log n \rceil]\), incurring a polylogarithmic overhead.

We will use a quantum walk procedure on a Johnson graph invoking 15. In the walk database, for each \(i \in [\ell]\), we will store \(r_i\) vertices whose degree is close to \(q_i\) and their neighborhoods. Note that the number of vertices whose degree is in \([q_i/2, 3q_i/2]\) is \(t_i \in O(\overline{m}/q_i)\).

To determine if a vertex \(v\) has degree at least \(q_i/2\) or at most \(q_i/6\) with probability at least \(1-1/n^3\), we can use the approximate degree counting algorithm in 2 using \(\tilde{O}(\sqrt{n/q_i})\) queries. Similarly, to determine if a vertex \(v\) has degree at least \(9q_i/2\) or at most \(3q_i/2\) with probability at least \(1-1/n^3\), we can use the approximate degree counting algorithm in 2 using \(\tilde{O}(\sqrt{n/q_i})\) queries. Thus, for a vertex \(v\), if \(\deg(v) \in [q_i/2, 3q_i/2]\), then it is accepted by the first check and rejected by the second check with probability at least \(1-2/n^3\). Since there are \(t_i\) vertices with degree in \([q_i/2, 3q_i/2]\), the probability that a randomly sampled vertex has such degree is \(t_i/n\). Thus, via Grover’s algorithm, the total cost of searching for a vertex with degree close to \(q_i\) is \(\widetilde{O}(\sqrt{n/t_i} \cdot \sqrt{n/q_i}) \subseteq \widetilde{O}(n/\sqrt{t_i})\). Computing the neighborhood for any \(v\) with its degree close to \(q_i\) will cost \(\widetilde{O}(\sqrt{n \deg(v)}) = \widetilde{O}(\sqrt{n \cdot q_i})\) by 1.

For each update step of our walk, for each \(i \in [\ell]\), we randomly remove \(s_i\) of the \(r_i\) vertices (and their neighbors) and add \(s_i\) other vertices with degree close to \(q_i\) and their neighborhoods. We say that a vertex of our walk is marked if the database associated with this vertex contains \(\ell\) non-adjacent vertices of a \(k\)-cycle and their neighborhood in \(\ell\) different blocks.

We are now ready to compute the cost of our quantum walk. The setup (and update) cost involves, for each \(i \in [\ell]\), searching for \(r_i\) (respectively \(s_i\)) vertices with degree close to \(q_i\) and computing their neighborhoods. We earlier noticed that for each vertex, the former step costs \(\widetilde{O}(n/\sqrt{t_i})\) and the latter step costs \(\widetilde{O}(\sqrt{n \cdot q_i})\) queries. Thus, the total cost for each vertex is \(\widetilde{O}(n/\sqrt{t_i} + \sqrt{n \cdot q_i}) \subseteq \widetilde{O}(\sqrt{n \overline{m}/t_i})\) since \(t_i \cdot q_i \in O(\overline{m})\) and \(\overline{m} \in \Omega(n)\). It follows that the setup and update costs are \(S \in \widetilde{O}(\sum_{i \in [\ell]} r_i \cdot \sqrt{n \overline{m}/t_i})\) and \(U \in \widetilde{O}(\sum_{i \in [\ell]} s_i \cdot \sqrt{n \overline{m}/t_i})\) respectively. The checking procedure involves determining if the database contains \(\ell\) non-adjacent vertices of a \(k\)-cycle in \(\ell\) different blocks. Since we also store the neighborhoods of all the vertices, we need to decide if there are \(\ell\) vertices in \(\ell\) different blocks forming a length-\(2\ell\) path that can be extended to a cycle of length \(k = 2\ell+1\). This can be done by searching for an edge that connects a pair of endpoints of any such path in \(O(\sqrt{n^2}) = O(n)\) queries using Grover’s algorithm. The spectral gap \(\delta\) of our walk is \(\Omega(\min_{i \in [\ell]}s_i/r_i)\) and the probability \(\epsilon\) of marked vertices of our walk is \(\Omega(\prod_{j \in [\ell]} r_j/t_j)\). Therefore, the total cost of our walk is \[S + \frac{1}{\sqrt{\epsilon}} \left( \frac{1}{\sqrt{\delta}}U + C\right) \in \widetilde{O}\left(\sum_{i \in [\ell]} r_i \cdot \sqrt{\frac{n \overline{m}}{t_i}} + \prod_{j \in [\ell]} \sqrt{\frac{t_j}{r_j}} \left(\max_{i \in [\ell]} \sqrt{\frac{r_i}{s_i}} \left(\sum_{i \in [\ell]} s_i \cdot \sqrt{\frac{n \overline{m}}{t_i}}\right) + n \right)\right)\]

We will let \[\frac{r_i}{r_j} = \frac{s_i}{s_j} = \sqrt{\frac{t_i}{t_j}}, \qquad \qquad s_1 = 1, \qquad \qquad r_1 = \sqrt{t_1} n^{\frac{1}{2}-\frac{1}{\ell+1}},\] and argue that all the three terms in the above expression are bounded by \(\widetilde{O}(\sqrt{\overline{m}}n^{1-\frac{1}{\ell+1}})\). First, notice that

\[\begin{align} \sum_{i \in [\ell]} r_i \cdot \sqrt{\frac{n \overline{m}}{t_i}} = \ell \cdot r_1 \cdot \sqrt{\frac{n \overline{m}}{t_1}} \in O (\sqrt{\overline{m}} n^{1-\frac{1}{\ell+1}}). \end{align}\]

For the second term, we first simplify \[\begin{align} \prod_{j \in [\ell]} \frac{t_j}{r_j} = \left(\frac{\sqrt{t_1}}{r_1}\right)^\ell \cdot \prod_{j \in [\ell]}\sqrt{t_j} = \frac{t_1}{r_1} \cdot \left(\frac{\sqrt{t_1}}{r_1}\right)^{\ell-1} \prod_{j \in [2,\ell]}\sqrt{t_j} \leq \frac{t_1}{r_1} \cdot \left(\frac{\sqrt{t_1 n}}{r_1}\right)^{\ell-1} = \frac{t_1}{r_1} n^{\frac{\ell-1}{\ell+1}} \end{align}\] so \[\begin{align} \prod_{j \in [\ell]} \sqrt{\frac{t_j}{r_j}} = \sqrt{\frac{t_1}{r_1}} n^{\frac{\ell-1}{2(\ell+1)}}. \end{align}\]

We also simplify \[\begin{align} \max_{i \in [\ell]} \sqrt{\frac{r_i}{s_i}} \left(\sum_{i \in [\ell]} s_i \cdot \sqrt{\frac{n \overline{m}}{t_i}}\right) = \ell \cdot \sqrt{r_1 s_1} \cdot \sqrt{\frac{n \overline{m}}{t_1}} \in O\left(\sqrt{r_1 s_1} \cdot \sqrt{\frac{n \overline{m}}{t_1}} \right) = O\left(\sqrt{\frac{r_1}{t_1}} \cdot \sqrt{n \overline{m}} \right). \end{align}\]

Taking their products gives us \[\begin{align} \prod_{j \in [\ell]} \sqrt{\frac{t_j}{r_j}} \left(\max_{i \in [\ell]} \sqrt{\frac{r_i}{s_i}} \left(\sum_{i \in [\ell]} s_i \cdot \sqrt{\frac{n \overline{m}}{t_i}}\right) \right) \in O\left(\sqrt{n \overline{m}} \cdot n^{\frac{\ell-1}{2(\ell+1)}}\right) = O (\sqrt{\overline{m}} n^{1-\frac{1}{\ell+1}}). \end{align}\]

It remains to argue that the term corresponding to the checking cost is bounded by \(O (\sqrt{\overline{m}} n^{1-\frac{1}{\ell+1}})\). To show this, it is sufficient to argue that \(C \in O(1/\sqrt{\delta} \cdot U)\), which we do as follows. \[\begin{align} \frac{1}{\sqrt{\delta}} U \geq \sqrt{\frac{r_1}{t_1}} \cdot \sqrt{n \overline{m}} = \sqrt{\frac{n^{\frac{1}{2}-\frac{1}{\ell+1}}}{\sqrt{t_1}}} \cdot \sqrt{n \overline{m}} \geq n^{\frac{1}{2}-\frac{1}{2(\ell+1)}} \cdot \sqrt{\overline{m}} \in \Omega(n) \subseteq \Omega(C). \end{align}\] where the last step follows since \(\overline{m} \in \Omega(n^{1+1/(\ell+1)})\). ◻

Proof. Let \(\ell = \lfloor k/2 \rfloor\). The general strategy of our algorithm is to first check if \(G\) is dense enough to already have a \(\mathcal{C}_{2\ell}\) using 31. If it is not, then we know that \(E(G) \in O(n^{1+1/\ell})\), which we can use to efficiently compute if there is a \(\mathcal{C}_j\) for any \(j \in [3,k]\) using 30. See 6 for a formal description of this algorithm.

The correctness is easy to check. It remains to argue the desired complexity. For the density reduction stage, it follows from 1 that \(\widetilde{O}(\sqrt{n^2/\overline{m}}) = \widetilde{O}(\sqrt{n^{1-1/\ell}})\) queries would be sufficient. If the algorithm does not abort in the density reduction stage, then we can suppose that \(E(G) \in O(\overline{m}) = O(n^{1+1/\ell})\). The complexity expression in 30 is non-decreasing in \(k\) so the complexity contribution for the iteration where \(j=k\) will dominate the cost of the for loop in the sparse case stage. In fact, this step will dominate the cost of 6 since the cost of the density reduction stage is sublinear. From 11, we deduce that the cost will be \[\widetilde{O}(\sqrt{\overline{m}} n^{1-\frac{1}{\ell+1}}) = \widetilde{O}(n^{\frac{3}{2} - \frac{\ell-1}{2\ell (\ell+1)}}) = \begin{cases} \widetilde{O}(n^{\frac{3}{2} - \frac{k-2}{k(k+2)}}), & \text{if k is even}, \\ \widetilde{O}(n^{\frac{3}{2} - \frac{k-3}{(k-1)(k+1)}}), & \text{if k is odd}. \end{cases}\qedhere\]

 ◻

Proof. Let \(G = (V,E)\) be any graph on \(n\) vertices, where we write \(V = \{v_1, \dots, v_n\}\). We will reduce \(\mathtt{GC}_G \circ \mathtt{OR}_n\) to \(\mathtt{Cycle}_s^{\leq k}\). That is, given query access to individual bits of \(n\) strings \(x^{(i)} \in \{0,1\}^n\) with \(x^{(i)}\) associated with \(v_i\), which forms an instance of \(\mathtt{GC}_G \circ \mathtt{OR}_n\), we construct a graph instance \(G' =(V',E')\) of \(\mathtt{Cycle}_s^{=5}\) as follows. Let \(V' = \{v_j^{(\ell)} : j \in [n], \ell \in [4]\} \cup \{s\}\). We define \[\overline{E} = \{\{s,v_j^{(1)}\},\{s,v_j^{(4)}\} : j \in [n]\} \cup \{\{v_j^{(2)}, v_k^{(3)}\}, \{v_k^{(2)}, v_j^{(3)}\} : \{v_j,v_k\} \in E\},\] and \[E_x = \{\{v_j^{(1)},v_k^{(2)}\},\{v_k^{(3)}, v_j^{(4)}\} : x_j^{(k)} = 1\}.\]

We now argue that \(G' = (V',\overline{E} \cup E_x)\) is a positive input to \(\mathtt{Cycle}^{=5}\) if and only if \(x\) is a positive input to \(\mathtt{GC}_G \circ \mathtt{OR}_n\). To that end, suppose that \(x\) is a positive input for \(\mathtt{GC}_G \circ \mathtt{OR}_n\). Then, there exist \(j,k \in [n]\) such that \(\{v_j,v_k\} \in E\), and that there are \(\ell_j, \ell_k \in [n]\) such that \(x_{\ell_j}^{(j)} = x_{\ell_k}^{(k)} = 1\), and so we have a cycle \(s\) — \(v_{\ell_j}^{(1)}\) — \(v_j^{(2)}\) — \(v_k^{(3)}\) — \(v_{\ell_k}^{(4)}\) — \(s\) of length \(5\) in \(G'\).

For the reverse direction, suppose that \(G'\) has a cycle of length \(5\) passing through \(s\). As \(G'\) is a color-coded graph with an odd number of layers, any cycle of length \(5\) must traverse through all the layers, which means its path can be written as \(s\) — \(v_{\ell_j}^{(1)}\) — \(v_j^{(2)}\) — \(v_k^{(3)}\) — \(v_{\ell_k}^{(4)}\) — \(s\), for suitable choices of \(\ell_j, j, k, \ell_k \in [n]\). This then implies that \(\{v_j,v_k\} \in E\), and \(x_{\ell_j}^{(j)} = x_{\ell_k}^{(k)} = 1\), which means that \(x\) is a positive instance for \(\mathtt{GC}_G \circ \mathtt{PromOR}_n\).

Thus, we find that \(\mathsf{Q}(\mathtt{Cycle}_s^{=5}) \geq \mathsf{Q}(\mathtt{GC}_G \circ \mathtt{OR}_n) \in \Theta(\sqrt{n} \cdot \mathsf{Q}(\mathtt{GC}_G))\), for all graphs \(G\) with \(n\) vertices, using that the quantum query complexity multiplies under composition [28]. Finally, we can take the maximum over all such \(G\) on the right-hand side of the equation to obtain the claimed result. ◻