Even Cycles

Created: Jan 1, 1995; last updated: Feb 1, 2026

Introduction

My graduate advisor, Dr. Victor Klee, suggested the topic of finding even cycles (cycles of even length) in directed graphs for my Master of Science thesis.

The main unsolved question at the time was:

Question:

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).