Graduate Student Seminar: Detecting a Long Even Hole, Speaker: Linda Cook

Graduate Student Seminars
  • Linda Cook
  • PACM
  • Detecting a Long Even Hole
Sep 17, 2019
12:30 pm
Fine Hall 214

Title:  Detecting a Long Even Hole

Abstract:  

We call a subgraph of G induced if its vertices are a subset of the vertices of G and it contains any edge of G with both its endpoints in this subset. We call an induced cycle of even length in G an even hole. In 1991, Bienstock showed that it is NP-Hard to test whether a graph G has an even hole containing a specified vertex v in G. In 2002, Conforti, Cornuéjols, Kapoor and Vušković gave a polynomial-time algorithm to test whether a graph contains an even hole by applying a theorem about the structure of even-hole-free graphs from an earlier paper [3]. In 2003, Chudnovsky, Kawarabayashi and Seymour provided a simpler polynomial time algorithm that searches for even holes directly [3]. We extend this result by presenting a polynomial time algorithm to determine whether a graph has an even hole of length at least k for a given k ≥ 4.  (Joint work with Paul Seymour)

[1] D. Bienstock, On complexity of testing for odd holes and induced paths, Discrete Mathematics 90 (1991) 85-92.

[2] Maria Chudnovsky, Ken-ichi Kawarabayashi, and Paul Seymour. Detecting even holes. Journal of Graph Theory, 48(2):85–111, 2005.

[3] Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vušković. Even-hole-free graphs Part ii: Recognition algorithm. Journal of graph theory, 40(4):238–266, 2002.