Finding a shortest even hole in polynomial time

DOI10.1002/JGT.22748MaRDI QIDQ6057650zbMATH OpenFDO

Authors Hsueh-I Lu

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

data structureinduced subgraphpolynomial-time algorithmshortest even hole

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Paths and cycles (05C38)

Abstract: An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock [DM 1991 and 1992] proved that detecting an even (respectively, odd) hole containing a given vertex is NP-complete. Conforti, Chornu'ejols, Kappor, and Vuv{s}kovi'{c} [FOCS 1997] gave the first known polynomial-time algorithm to determine whether a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour [JGT 2005] estimated that Conforti et al.'s algorithm runs in $O(n^{40})$ time on an $n$-vertex graph and reduced the required time to $O(n^{31})$. Subsequently, da~Silva and Vuv{s}kovi'{c}~[JCTB 2013], Chang and Lu [JCTB 2017], and Lai, Lu, and Thorup [STOC 2020] improved the time to $O(n^{19})$, $O(n^{11})$, and $O(n^9)$, respectively. The tractability of determining whether a graph contains odd holes has been open for decades until the algorithm of Chudnovsky, Scott, Seymour, and Spirkl [JACM 2020] that runs in $O(n^9)$ time, which Lai et al. also reduced to $O(n^8)$. By extending Chudnovsky et al.'s techniques for detecting odd holes, Chudnovsky, Scott, and Seymour [Combinatorica 2020 to appear] (respectively, [arXiv 2020]) ensured the tractability of finding a long (respectively, shortest) odd hole. They also ensured the NP-hardness of finding a longest odd hole, whose reduction also works for finding a longest even hole. Recently, Cook and Seymour ensured the tractability of finding a long even hole. An intriguing missing piece is the tractability of finding a shortest even hole, left open for at least 15 years by, e.g., Chudnovsky et al. [JGT 2005] and Johnson [TALG 2005]. We resolve this long-standing open problem by giving the first known polynomial-time algorithm, running in $O(n^{31})$ time, for finding a shortest even hole in an $n$-vertex graph that contains even holes.

Recommendations

• Finding a Shortest Odd Hole
• A polynomial-time algorithm to find shortest paths with recourse
• Shortest two disjoint paths in polynomial time
• Shortest two disjoint paths in polynomial time
• Finding short cycles in embedded graph in polynomial time
• A faster algorithm to recognize even-hole-free graphs
• A faster algorithm to recognize even-hole-free graphs
• On the complexity of testing for odd holes and induced odd paths
• Finding a Polytope from Its Graph in Polynomial Time
• Efficient edge domination on hole-free graphs in polynomial time

Cites work

• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3902654 (Why is no real title available?)
• scientific article; zbMATH DE number 1496606 (Why is no real title available?)
• scientific article; zbMATH DE number 7650229 (Why is no real title available?)
• A bound on the treewidth of planar even-hole-free graphs
• A faster algorithm to recognize even-hole-free graphs
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• A note on chromatic number of (cap, even hole)-free graphs
• Algorithms for Perfectly Contractile Graphs
• Bisimplicial vertices in even-hole-free graphs
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Corrigendum to: ``Bisimplicial vertices in even-hole-free graphs
• Corrigendum to: ``Even pairs and prism corners in square-free Berge graphs
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• Dense induced bipartite subgraphs in triangle-free graphs
• Detecting a Theta or a Prism
• Detecting a long odd hole
• Detecting an Odd Hole
• Detecting an induced subdivision of K₄
• Detecting even holes
• Even pairs and prism corners in square-free Berge graphs
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Even-hole-free graphs. I: Decomposition theorem
• Even-hole-free graphs: A survey
• FPT and kernelization algorithms for the induced tree problem
• Finding a Shortest Odd Hole
• Finding an induced path of given parity in planar graphs in polynomial time
• Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
• Induced paths in 5-connected graphs
• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• On the complexity of testing for odd holes and induced odd paths
• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• On the structure of (even hole, kite)-free graphs
• Recognizing Berge graphs
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• The NP-completeness column
• The strong perfect graph theorem
• The three-in-a-tree problem
• Three-in-a-tree in near linear time
• Triangulated neighborhoods in even-hole-free graphs

Cited in

(8)

• Smallest odd holes in claw-free graphs (extended abstract)
• Hole and antihole detection in graphs
• Detecting holes and antiholes in graphs
• Detecting a long even hole
• A faster algorithm to recognize even-hole-free graphs
• Detecting even holes
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• A faster algorithm to recognize even-hole-free graphs

This page was built for publication: Finding a shortest even hole in polynomial time

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