English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Various classes of induced subgraphs are involved in the deepest results ofgraph theory and graph algorithms. A prominent example concerns the {\emperfection} of $G$ that the chromatic number of each induced subgraph $H$ of$G$ equals the clique number of $H$. The seminal Strong Perfect Graph Theoremconfirms that the perfection of $G$ can be determined by detecting odd holes in$G$ and its complement. Chudnovsky et al. show in 2005 an $O(n^9)$ algorithmfor recognizing perfect graphs, which can be implemented to run in$O(n^{6+\omega})$ time for the exponent $\omega<2.373$ of square-matrixmultiplication. We show the following improved algorithms.  1. The tractability of detecting odd holes was open for decades until themajor breakthrough of Chudnovsky et al. in 2020. Their $O(n^9)$ algorithm islater implemented by Lai et al. to run in $O(n^8)$ time, leading to the bestformerly known algorithm for recognizing perfect graphs. Our first result is an$O(n^7)$ algorithm for detecting odd holes, implying an $O(n^7)$ algorithm forrecognizing perfect graphs.  2. Chudnovsky et al. extend in 2021 the $O(n^9)$ algorithms for detecting oddholes (2020) and recognizing perfect graphs (2005) into the first polynomialalgorithm for obtaining a shortest odd hole, which runs in $O(n^{14})$ time. Wereduce the time for finding a shortest odd hole to $O(n^{13})$.  3. Conforti et al. show in 1997 the first polynomial algorithm for detectingeven holes, running in about $O(n^{40})$ time. It then takes a line ofintensive efforts in the literature to bring down the complexity to$O(n^{31})$, $O(n^{19})$, $O(n^{11})$, and finally $O(n^9)$. On the other hand,the tractability of finding a shortest even hole has been open for 16 yearsuntil the very recent $O(n^{31})$ algorithm of Cheong and Lu in 2022. Weimprove the time of finding a shortest even hole to $O(n^{23})$.

Improved Algorithms for Recognizing Perfect Graphs and Finding Shortest Odd and Even Holes