Detecting an Odd Hole

DOI10.1145/3375720MaRDI QIDQ5133961zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Sophie Spirkl, Alex Scott, Paul Seymour

Publication date 11 November 2020

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.00208

zbMATH Keywords

odd holesperfect graphsrecognition algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: A hole in a graph G is an induced cycle of length at least four; an antihole is a hole in the complement of G. In 2005, Chudnovsky, Cornuejols, Liu, Seymour and Vuskovic showed that it is possible to test in polynomial time whether a graph contains an odd hole or antihole (and thus whether G is perfect). However, the complexity of testing for odd holes has remained open. Indeed, it seemed quite likely that testing for an odd hole was NP-complete: for instance, Bienstock showed that testing if a graph has an odd hole containing a given vertex is NP-complete. In this paper we resolve the question, by giving a polynomial-time algorithm to test whether a graph contains an odd hole. This also gives a new and considerably simpler polynomial-time algorithm that tests for perfection.

Recommendations

• Detecting a long odd hole
• Detecting even holes
• Detecting a long even hole
• Finding a Shortest Odd Hole
• Finding large holes
• Finding the hole in a wall
• Fixing a hole
• Detecting holes and antiholes in graphs
• Holes and obstacles

Cited in

(17)

• Polyhedral properties of the induced cluster subgraphs
• Detecting a long odd hole
• Detecting a long even hole
• FPT and kernelization algorithms for the induced tree problem
• Finding a shortest even hole in polynomial time
• Graphs of large chromatic number
• Shortest odd paths in undirected graphs with conservative weight functions
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Thick forests
• Contractions in perfect graphs
• Even pairs in Berge graphs with no balanced skew-partitions
• The sandwich problem for odd-hole-free and even-hole-free graphs
• Odd paths, cycles, and T-joins: connections and algorithms
• First-order logic with metric betweenness – the case of non-definability of some graph classes
• Computing pivot-minors
• Improved algorithms for perfect graphs and odd holes
• On the structure of (dart, odd hole)-free graphs

This page was built for publication: Detecting an Odd Hole

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5133961)