boolean circuit to decide if there's a path of at most $k$ edges from $u$ to $v$ in graph $G$ Let an undirected graph and $k\in\mathbb{N}$. Prove that there's a circuit of depth $2$, size of $n^{O(k)}$ and unlimited fan-in, which gets $\langle G,v,u\rangle$ as an input and checks if there's a path from $u$ to $v$ of at most $k$ edges.


So I'm familiar with Warshall's algorithm and I think I should utilize it here. The problem is that it seems impossible to do that with a depth-$2$ circuit.

I'd be glad if you could direct me what to do.

Thanks
Since you are allowed an $n^{O(k)}$ size circuit, you could go over all possible $k$-length paths originating at $u$. The first level will contain $n^{O(k)}$ AND gates, one for every possible sequence of vertices $v_1=u,v_2,...,v_l=v$, for $l\le k$, and in the second level you input the results of the previous level to an OR gate.