Even cycle in a simple graph
is a simple graph, decide if there exist a cycle of even length in .
The problem comes from 2014 Spring UIUC Theory Qualify Exam.
Let denote the local edge connectivity of vertices and . It’s the same as the largest number of edge disjoint paths connecting and . . Similarly, is defined as local vertex connectivity, and
If for some , then there exist an even cycle.
There are 3 vertex disjoint paths from to , thus it contains cycle , and . One of them will have even length.
If , then .
If , we consider the 3 edge paths between . Let them be . Notice if none of them intersect at a vertex, .
If intersects and has their first intersection at . Let and be the paths following from to and to , and the paths following from to . is a cycle that contains and . because there is an additional edge disjoint path from to .
So now we can consider , where and is in some cycle . Consider another path from to that is edge disjoint from the cycle. Let be the first vertex where intersects . Clearly, .
It should be easy to show that
If , then all cycles in the graph are edge disjoint.
2 A complicated yet obvious algorithm
- Compute if , if so, return true.
- Compute if there is an even cycle in linear time.
We first sparsify the graph with Nagamochi and Ibaraki’s linear time algorithm that preserves the edge connectivity up to . After spending time, the graph has at most edges. We want to find a global maximum min-cut in the resulting graph. Either -min-cut is the global maximum min-cut, or are in the same component of the global maximum min-cut. One can modify Stoer-Wagner algorithm to find in time. Since our graph is unweighted we can do it better in time.
Another approach is to show the graph cannot contain a diamond graph as a minor and use any general graph minor recognition algorithm. The fastest I know is the one from the original Robertson–Seymour paper. There are some discussion on cstheory on what is know about this algorithm.
However we can do it better, because we can easily check graphs without a diamond as a minor has treewidth two. So we can first check if the graph have a fixed treewidth in linear time. Next, we can then apply a linear time minor testing algorithm on graphs with bounded branch width(which is implied by bounded treewidth).
The second step is computationally easy. Do a DFS, whenever we find a cycle, check if the cycle is even, delete all those edges, and keep going. The number of steps we take is at most time. In fact, we don’t really need to delete the edges once we find a cycle, as we know they will never get used by another cycle.
3 A much simpler algorithm
Our algorithm above is pretty general and uses some heavy machinery. That’s the kind of solution I would give during a qualify exam due to time constraints(well, always use the most powerful technique possible).
The theorems we proved implies one nice corollary
If a graph has no even cycles, then all cycles in the graph are edge disjoint.
This kind of graph has a name, a cactus graph. It is so special we can recognize it in linear time. A graph is a cactus if once we build a DFS tree, every vertex has at most one back edge.
This implies a extremely simple algorithm
- Run a DFS to build a DFS tree. Let be the depth of a vertex in the tree.
- Assume there is a back edge between and , check if there is any back edge end at some node in the unique path from to .
- For every vertex , if it has a back edge to some vertex , then check if is odd. If it is, return true.
- Return false.
 H. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing. 25 (1996) 1305–1317 10.1137/S0097539793251219.
 I. Adler, F. Dorn, F. Fomin, I. Sau, D. Thilikos, Faster parameterized algorithms for minor containment, in: H. Kaplan (Ed.), Algorithm Theory - Swat 2010, Springer Berlin Heidelberg, 2010: pp. 322–333 10.1007/978-3-642-13731-0_31.