Find Cycle Length

Question

Suppose I have an undirected graph which is stored as an adjacency matrix. The graph contains a single cycle; all other vertices are isolated.

How can I efficiently find the length of the cycle?

The best I've been able to come up with:

1. Starting at row 0 of the matrix, traverse through rows until an initial 1 is found, say at row startVertex and column k. Increment a counter.
2. Search column k for its other 1, say at row j. Increment the counter.
3. Search row j for its other 1 value. Increment the counter.
4. Repeat steps 2 and 3 until a row or column which matches startVertex is found.

The complexity of this algorithm is $\mathcal{O}(V^2)$.

Is there a better algorithm out there?

Answer 1

$\Omega(V^2)$ is a lower bound on the running time. You can't do better than $O(V^2)$.

Consider a graph $G_3$ with a 3-cycle $a,b,c,a$ and a graph $G_4$ with a 4-cycle $a,b,c,d,a$. To distinguish these two graphs, the algorithm must examine the adjacency matrix at one or more cells corresponding to the 5 edges involved in these cycles.

If we randomly permute the vertices, an algorithm that reads a single entry in the adjacency matrix has at most a $5/{V \choose 2} \le 10/(V-1)^2$ probability of hitting one of those 5 edges. Therefore, an algorithm that reads at most $m$ entries in the adjacency matrix has (by a union bound) at most an $10m/(V-1)^2$ probability of reading at least one entry in the matrix that corresponds to one of those five edges. If $m < (V-1)^2/20$, this success probability is at most $1/2$.

Thus, there cannot be a deterministic algorithm that always succeeds in distinguishing a graph with a 3-cycle from a graph with a 4-cycle, whose running time is at most $(V-1)^2/20$.