# Algorithm for finding fixed cycles in bipartite graphs in sublinear time

Does there exist an algorithm that will compute in sublinear time whether a bipartite graph contains a cycle of fixed length? For example given a $K_{3,3}$ graph finding if it contains a cycle $C_4$.

I considered the answer to be no. As a DFS could be used and then compare to see if after a certain traversal we were back at a node we've already visited. That would be $O(n)$ time at best. However, as a counter argument to that, a complete graph will always contain a cycle, and if we know the cycle length then search time should be dependant on the cycle length which would be $O(1)$ or big-oh of the cycle length. If we know whether we're in partition A or B all we have to do is return to the first node since both sets connect to all nodes of the other.

For example, if the input is a $K_{3,3}$, you can immediately answer YES. So suppose the input graph is an arbitrary bipartite graph, and we are looking for a $k$-cycle for a fixed $k$. If $k$ is odd, we can output NO, as bipartite graphs are characterized by having no odd cycles. Otherwise, an adversary argument shows that for even $k$, sublinear time is not achievable. Similarly, it is easy to see you cannot test for bipartiteness in sublinear time. (For both cases, consider having read $m-1$ edges, and the last $m$th edge to be read decides if you have a path or a cycle).