Finding a Shortest Odd Hole
Abstract
An odd hole in a graph is an induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an odd hole. We subsequently showed that, for every t , there is a polynomial-time algorithm to test whether a graph contains an odd hole of length at least t . In this article, we give an algorithm that finds a shortest odd hole, if one exists.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 19, 2021
- Source ID
- 10.1145/3447869
Entities
People
- Alex Scott
- Maria Chudnovsky
- Paul Seymour
Organizations
- Air Force Office of Scientific Research
- Army Research Office
- National Science Foundation
- Princeton University
- University of Oxford