2
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

In general, you can't determine if there is a e.g., 4-cycle in an arbitrary graph in sublinear time. This is shown by a simple adversary argument: if you don't read the whole input (this is what sublinear means), how can you possibly know if a critical edge is present that creates the 4-cycle? There are similar questions asked already, but these appear in a different context (usually, these are related to sorting). For instance, see this question.

If you assume the input graph is complete, or has some other structure that guarantees the existence of a 4-cycle, an algorithm for solving the problem can immediately output YES. But if the input graph is arbitrary, again by an adversary argument you cannot determine if the graph is say complete in sublinear time.

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.