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?

  • 2
    $\begingroup$ If you are using an adjacency matrix, then you are likely to be stuck with $\mathcal O\left(\left|V\right|^2\right)$, since that is the size of the input, and you probably have to read all of the input in the worst case. Using some sort of adjacency list would probably be easier. $\endgroup$
    – Realz Slaw
    Nov 5, 2013 at 23:49

1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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