Return to Answer

If we restrict to the class of planar graphs, then there is a linear time algorithm due to Eppstein. It is also linear for graphs of bounded tree-width since the problem of finding a cycle of fixed length can easily be encoded as a monadic second-order logic formula, and we can then appeal to Courcelle's theorem. I suspect that the answer for general graphs is actually polynomial.

Edit. The related problem of finding a cycle of length $a$ (mod $k$) has not been proven to be polynomial (except in the case $a=0$).

If we restrict to the class of planar graphs, then there is a linear time algorithm due to Eppstein. It is also linear for graphs of bounded tree-width since the problem of finding a cycle of fixed length can easily be encoded as a monadic second-order logic formula, and we can then appeal to Courcelle's theorem.

Edit. The related problem of finding a cycle of length $a$ (mod $k$) has not been proven to be polynomial (except in the case $a=0$).

If we restrict to the class of planar graphs, then there is a linear time algorithm due to Eppstein. It is also linear for graphs of bounded tree-width since the problem of finding a cycle of fixed length can easily be encoded as a monadic second-order logic formula, and we can then appeal to Courcelle's theorem. I suspect that the answer for general graphs is actually polynomial, although I am sure that this hasn't been proven. I believe that the related problem of finding a cycle of length 0 (mod k) has not been proven to be polynomial.

If we restrict to the class of planar graphs, then there is a linear time algorithm due to Eppstein. It is also linear for graphs of bounded tree-width since the problem of finding a cycle of fixed length can easily be encoded as a monadic second-order logic formula, and we can then appeal to Courcelle's theorem. I suspect that the answer for general graphs is actually polynomial.

Edit. The related problem of finding a cycle of length $a$ (mod $k$) has not been proven to be polynomial (except in the case $a=0$).

If we restrict to the class of planar graphs, then there is a linear time algorithm due to Eppstein. It is also linear for graphs of bounded tree-width since the problem of finding a cycle of fixed length can easily be encoded as a monadic second-order logic formula, and we can then appeal to Courcelle's theorem. I suspect that the answer for general graphs is actually polynomial, although I am sure that this hasn't been proven. I believe that the related problem of finding a cycle of length 0 (mod k) also has not been proven to be polynomial.

If we restrict to the class of planar graphs, then there is a linear time algorithm due to Eppstein. It is also linear for graphs of bounded tree-width since the problem of finding a cycle of fixed length can easily be encoded as a monadic second-order logic formula, and we can then appeal to Courcelle's theorem. I suspect that the answer for general graphs is actually polynomial, although I am sure that this hasn't been proven. I believe that the related problem of finding a cycle of length 0 (mod k) has not been proven to be polynomial.