Even Cycles
by Michael Brundage Created: 01 Jan 1995 Updated: 24 May 2014
Introduction
My Master of Science thesis examined the topic of finding even cycles (cycles of even length) in graphs, and related problems. This topic was suggested by my graduate advisor, Dr. Victor Klee. The main unsolved question at the time was:
Does there exist a polynomial-time algorithm for finding even cycles in directed graphs?
For undirected graphs, an \(O(N^2)\) solution was published a year later in Finding Even Cycles Even Faster (Yuster & Zwick, 1997).
The question for directed graphs was positively answered three years later in Permanents, Pfaffian orientations, and even directed circuits (Robertson, Seymour & Thomas, 1999), who acknowledged the solution came from McCuaig, who later published his own proof as Pólya’s Permanent Problem (McCuaig, 2004).
