Even cycle in a simple graph

Problem1

$G = (V, E)$ is a simple graph, decide if there exist a cycle of even length in $G$ .

The problem comes from 2014 Spring UIUC Theory Qualify Exam.

1 Characterizations

Let $λ (u, v)$ denote the local edge connectivity of vertices $u$ and $v$ . It’s the same as the largest number of edge disjoint paths connecting $u$ and $v$ . $\overline{λ} (G) = max_{u, v \in V} {λ (u, v)}$ . Similarly, $κ (u, v)$ is defined as local vertex connectivity, and $\overline{κ} (G) = max_{u, v \in V} {κ (u, v)}$

Theorem2

If $κ (u, v) \geq 3$ for some $u, v \in V$ , then there exist an even cycle.

Proof

There are 3 vertex disjoint paths $p_{1}, p_{2}, p_{3}$ from $u$ to $v$ , thus it contains cycle $p_{1} p_{2}^{- 1}$ , $p_{1} p_{3}^{- 1}$ and $p_{2} p_{3}^{- 1}$ . One of them will have even length.

Theorem3

If $\overline{λ} (G) \geq 3$ , then $\overline{κ} (G) \geq 3$ .

Proof

If $λ (u, v) \geq 3$ , we consider the 3 edge paths between $u, v$ . Let them be $p_{1}, p_{2}, p_{3}$ . Notice if none of them intersect at a vertex, $κ (u, v) \geq 3$ .

If $p_{1}, p_{2}$ intersects and has their first intersection at $v^{'}$ . Let $p_{1}^{'}, p_{1}^{''}$ and $p_{2}^{'}$ be the paths following $p_{1}$ from $u$ to $v^{'}$ and $v^{'}$ to $v$ , and the paths following $p_{2}$ from $u$ to $v^{'}$ . $p_{1}^{'} p_{2}^{' - 1}$ is a cycle that contains $u$ and $v^{'}$ . $λ (u, v^{'}) \geq 3$ because there is an additional edge disjoint path $p_{3} p_{1}^{'' - 1}$ from $u$ to $v^{'}$ .

So now we can consider $u, v^{'}$ , where $λ (u, v^{'}) \geq 3$ and $u, v^{'}$ is in some cycle $C$ . Consider another path $P$ from $u$ to $v^{'}$ that is edge disjoint from the cycle. Let $t$ be the first vertex where $P$ intersects $C$ . Clearly, $κ (u, t) \geq 3$ .

It should be easy to show that

Theorem4

If $\overline{λ} (G) = 2$ , then all cycles in the graph are edge disjoint.

2 A complicated yet obvious algorithm

Compute if $\overline{λ} (G) > 2$ , 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 $3$ . After spending $O (n + m)$ time, the graph has at most $3 n$ edges. We want to find a global maximum min-cut in the resulting graph. Either $s - t$ -min-cut is the global maximum min-cut, or $s, t$ are in the same component of the global maximum min-cut. One can modify Stoer-Wagner algorithm to find $\overline{λ} (G)$ in $O (nm + n^{2} lo g n) = O (n^{2} lo g n)$ time. Since our graph is unweighted we can do it better in $O (n^{2})$ 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 $O (n^{3})$ 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[1]. Next, we can then apply a linear time minor testing algorithm on graphs with bounded branch width(which is implied by bounded treewidth)[2].

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 $O (n + m)$ 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

Corollary5

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 $d (v)$ be the depth of a vertex $v$ in the tree.
Assume there is a back edge between $x$ and $y$ , check if there is any back edge end at some node in the unique path from $x$ to $y$ .
For every vertex $v$ , if it has a back edge to some vertex $u$ , then check if $d (v) - d (u)$ is odd. If it is, return true.
Return false.

References

[1]

H. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing. 25 (1996) 1305–1317 10.1137/S0097539793251219.

[2]

I. Adler, F. Dorn, FedorV. Fomin, I. Sau, DimitriosM. 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.

Posted by Chao Xu on 2014-03-08.

Tags: algorithm.