Finding a Shortest Odd Hole

Maria Chudnovsky; Alex Scott; Paul Seymour

doi:10.1145/3447869

Finding a Shortest Odd Hole

Maria Chudnovsky, Alex Scott, Paul Seymour

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

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.

Original language	American English
Article number	3447869
Journal	ACM Transactions on Algorithms
Volume	17
Issue number	2
DOIs	https://doi.org/10.1145/3447869
State	Published - Jun 2021

ASJC Scopus subject areas

Mathematics (miscellaneous)

Keywords

Induced subgraph
recognition algorithm
shortest odd hole

Access to Document

10.1145/3447869

Cite this

@article{67a4368a6af14d38a73545950e6396f6,

title = "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.",

keywords = "Induced subgraph, recognition algorithm, shortest odd hole",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.",

year = "2021",

month = jun,

doi = "10.1145/3447869",

language = "American English",

volume = "17",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - Finding a Shortest Odd Hole

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

PY - 2021/6

Y1 - 2021/6

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

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

KW - Induced subgraph

KW - recognition algorithm

KW - shortest odd hole

UR - http://www.scopus.com/inward/record.url?scp=85107757606&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85107757606&partnerID=8YFLogxK

U2 - 10.1145/3447869

DO - 10.1145/3447869

M3 - Article

SN - 1549-6325

VL - 17

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 2

M1 - 3447869

ER -

Finding a Shortest Odd Hole

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this