The Art Gallery Guardian

Even cycle in a simple graph


Problem1

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

The problem comes from 2014 Spring UIUC Theory Qualify Exam.

1 Characterizations

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

Theorem2

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

Proof

There are 3 vertex disjoint paths p1,p2,p3p_1,p_2,p_3 from uu to vv, thus it contains cycle p1p21p_1 p_2^{-1},p1p31p_1 p_3^{-1} and p2p31p_2 p_3^{-1}. One of them will have even length.

Theorem3

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

Proof

If λ(u,v)3\lambda(u,v)\geq 3, we consider the 3 edge paths between u,vu,v. Let them be p1,p2,p3p_1,p_2,p_3. Notice if none of them intersect at a vertex, κ(u,v)3\kappa(u,v)\geq 3.

If p1,p2p_1,p_2 intersects and has their first intersection at vv'. Let p1,p1p_1',p_1'' and p2p_2' be the paths following p1p_1 from uu to vv' and vv' to vv, and the paths following p2p_2 from uu to vv'. p1p21p_1' p_2'^{-1} is a cycle that contains uu and vv'. λ(u,v)3\lambda(u,v')\geq 3 because there is an additional edge disjoint path p3p11p_3 p_1''^{-1} from uu to vv'.

So now we can consider u,vu,v', where λ(u,v)3\lambda(u,v')\geq 3 and u,vu,v' is in some cycle CC. Consider another path PP from uu to vv' that is edge disjoint from the cycle. Let tt be the first vertex where PP intersects CC. Clearly, κ(u,t)3\kappa(u,t)\geq 3.

It should be easy to show that

Theorem4

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

2 A complicated yet obvious algorithm

  1. Compute if λ(G)>2\overline{\lambda}(G)>2, if so, return true.
  2. 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 33. After spending O(n+m)O(n+m) time, the graph has at most 3n3n edges. We want to find a global maximum min-cut in the resulting graph. Either sts-t-min-cut is the global maximum min-cut, or s,ts,t are in the same component of the global maximum min-cut. One can modify Stoer-Wagner algorithm to find λ(G)\overline{\lambda}(G) in O(nm+n2logn)=O(n2logn)O(nm+n^2\log n)=O(n^2\log n) time. Since our graph is unweighted we can do it better in O(n2)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(n3)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)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

  1. Run a DFS to build a DFS tree. Let d(v)d(v) be the depth of a vertex vv in the tree.
  2. Assume there is a back edge between xx and yy, check if there is any back edge end at some node in the unique path from xx to yy.
  3. For every vertex vv, if it has a back edge to some vertex uu, then check if d(v)d(u)d(v)-d(u) is odd. If it is, return true.
  4. 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, 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.

Posted by Chao Xu on .
Tags: algorithm.