I decided to give a one-semester course entitled "On a Cycle in a Graph" next year. At first sight it might seem that this topic is trivial, but the algorithmic aspects of finding cycles with given properties can easily get complicated. Maybe it is better to say that they almost immediately become interesting. For example, what are the fastest algorithms for finding shortest cycles in graphs? This question was the topic of two FOCS papers recently - in 2011 and 2012. These papers have shown that in directed and undirected graphs a shortest cycle can be found in O(Wn^omega) time, when the edges of the graph are integral in the range [-W,W]. On the other hand, for planar graphs we have shown last year (ESA 2011) that this problem can be solved in O(n log log n) time. The paper studies undirected graphs, but the same technique can be applied to the directed case as well. The conjecture is that this should be possible in linear time! Similarly, it should be possible to find in linear time a shortest cycle that would contain s inside and t outside, for given s and t. This is exactly the min st-cut problem in planar graphs. Here, the fastest algorithm works in O(n log log n) time (STOC 2011). This, for me, is currently the most intriguing open problem in planar graphs. There are much more aspects of shortest cycles, e.g., finding shortest even length cycle seems much easier then finding shortest odd length cycle (ICALP '96).

By just adding another condition "passing through every vertex" to "shortest" one gets the TSP problem - this is what tigers like most. This problem in graphical case has witnessed some interesting progress in the last year (starting from FOCS 2011). Nevertheless, for the (general) metric case the Christofides algorithm remains the best. Finding longest cycles starts yet another related story, and leads us to techniques like color-coding (STOC '94).

General cycles are complicated, but even length 3 cycles -- triangles -- are not so easy. Finding minimum weight triangle (when edges are negative), seems to be as hard as the general problem as long as we want to get subqubic algorithms (FOCS 2010). Similarly, counting triangles in graphs has become one of the challenges in streaming algorithms. The number of triangles seems to be the simplest criteria to tell a random network form a social network apart. The social networks tend to be huge, so "subcubic" can here only mean linear time.

One of my favorite topic is the connection between cycles and matchings, which manifests itself in several nice relations. A minimum weight cycle cover problem (2-factor problem) can be solved using minimum weight perfect matchings. Or the problem of computing shortest distances from given source, can be seen as the dual problem to the shortest cycle problem - as shown by Gabow (FOCS '83). Finally, one should mention the tramp-steamer problem, i.e., the minimum mean-weight cycle problem. It is somewhat astonishing that such globally minimum cycle can be efficiently found, whereas the application to finding min-cost max-flow is a nice story as well.

To summarize, there is a lot to tell and it looks rather easy to fill a course with topics related to cycles in graphs. There are much more topics that can be added and probably you could name a few. However, more importantly huge fraction of these results happened just very recently. These topic are interesting for the algorithmic community (it is easy to get into good conferences) and there are a lot of nice open problems.