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

Yung-Chung Chiu111Department of Computer Science and Information Engineering,
National Taiwan University. Kai-Yuan Lai222Department of Computer Science and
Information Engineering, National Taiwan University. Hsueh-I
Lu333Corresponding author. Department of Computer Science and Information
Engineering, National Taiwan University. Email<EMAIL_ADDRESS>Research
of this author is supported by MOST grant 110–2221–E–002–075–MY3.

###### Abstract

An _induced_ subgraph of an $n$-vertex graph $G$ is a graph that can be
obtained by deleting a set of vertices together with its incident edges from
$G$. A _hole_ of $G$ is an induced cycle of $G$ with length at least four. A
hole is _odd_ (respectively, _even_) if its number of edges is odd
(respectively, even). Various classes of induced subgraphs are involved in the
deepest results of graph theory and graph algorithms. A prominent example
concerns the _perfection_ of $G$ that the chromatic number of each induced
subgraph $H$ of $G$ equals the clique number of $H$. The seminal Strong
Perfect Graph Theorem proved in 2006 by Chudnovsky, Robertson, Seymour, and
Thomas, conjectured by Berge in 1960, confirms that the perfection of $G$ can
be determined by detecting odd holes in $G$ and its complement. Based on the
theorem, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković show in 2005 an
$O(n^{9})$-time algorithm for recognizing perfect graphs, which can be
implemented to run in $O(n^{6+\omega})$ time for the exponent $\omega<2.373$
of square-matrix multiplication. We show the following improved algorithms for
detecting or finding induced subgraphs in $G$.

  1. 1.

The tractability of detecting odd holes in $G$ was open for decades until the
major breakthrough of Chudnovsky, Seymour, and Spirkl in 2020\. Their
$O(n^{9})$-time algorithm is later implemented by Lai, Lu, and Thorup to run
in $O(n^{8})$ time, leading to the best formerly known algorithm for
recognizing perfect graphs. Our first result is an $O(n^{7})$-time algorithm
for detecting odd holes, immediately implying a state-of-the-art
$O(n^{7})$-time algorithm for recognizing perfect graphs. Finding an odd hole
based on Chudnovsky et al.’s $O(n^{9})$-time (respectively, Lai et al.’s
$O(n^{8})$-time) algorithm for detecting odd holes takes $O(n^{10})$
(respectively, $O(n^{9})$) time. Nonetheless, our algorithm finds an odd hole
within the same $O(n^{7})$ time bound.

  2. 2.

Chudnovsky, Scott, and Seymour extend in 2021 the $O(n^{9})$-time algorithms
for detecting odd holes (2020) and recognizing perfect graphs (2005) into the
first polynomial-time algorithm for obtaining a shortest odd hole in $G$,
which runs in $O(n^{14})$ time. Our second result is an $O(n^{13})$-time
algorithm for finding a shortest odd hole in $G$.

  3. 3.

Conforti, Cornuéjols, Kapoor, and Vušković show in 1997 the first polynomial-
time algorithm for detecting even holes, running in about $O(n^{40})$ time. It
then takes a line of intensive 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 in $G$ has
been open for 16 years until the very recent $O(n^{31})$-time algorithm of
Cheong and Lu in 2022. Our third result is two improved algorithms for finding
a shortest even hole in $G$ that run in $O(n^{25})$ and $O(n^{23})$ time,
respectively.

##  1 Introduction

Let $G$ be an $n$-vertex undirected and unweighted graph. Let $V(G)$ consist
of the vertices of $G$. For any graph $H$, let $G[H]$ be the subgraph of $G$
induced by $V(H)$. A subgraph $H$ of $G$ is _induced_ if $G[H]=H$. That is, an
induced subgraph of $G$ is a graph that can be obtained from $G$ by deleting a
set of vertices in tandem with its incident edges. To _detect_ an (induced)
graph $H$ in $G$ is to determine whether $H$ is isomorphic to an (induced)
subgraph of $G$. To _find_ an (induced) graph $H$ in $G$ is to report an
(induced) subgraph of $G$ that is isomorphic to $H$, if there is one. Various
classes of induced subgraphs are involved in the deepest results of graph
theory and graph algorithms. One of the most prominent examples concerns the
_perfection_ of $G$ that the chromatic number of each induced subgraph $H$ of
$G$ equals the clique number of $H$. A graph is _odd_ (respectively, _even_)
if it has an odd (respectively, even) number of edges. A _hole_ of $G$ is an
induced cycle of $G$ having at least four edges. The seminal Strong Perfect
Graph Theorem of Chudnovsky, Robertson, Seymour, and Thomas [20, 25],
conjectured by Berge in 1960 [5, 6, 7], confirms that the perfection of a
graph $G$ can be determined by detecting odd holes in $G$ and its complement.
Based on the theorem, the first known polynomial-time algorithms for
recognizing perfect graphs take $O(n^{18})$ [35] and $O(n^{9})$ [17] time. The
$O(n^{9})$-time version can be implemented to run in $O(n^{6+\omega})$ time
[57, §6.2] via efficient algorithms for the _three-in-a-tree_ problem [24]
that detects induced subtrees of $G$ spanning three prespecified vertices,
where $\omega<2.373$ [2, 34, 58, 69] is the exponent of square-matrix
multiplication.

Detecting induced subgraphs, even the most basic ones like paths, trees, and
cycles, is usually more challenging than detecting their counterparts that
need not be induced. For instance, detecting paths spanning three prespecified
vertices is tractable (via, e. g., [55, 64]). However, the _three-in-a-path_
problem that detects induced paths spanning three prespecified vertices is NP-
hard (see, e. g., [47, 57]). The _two-in-a-path_ problem that detects induced
paths spanning two prespecified vertices is equivalent to determining whether
the two vertices are connected. Nonetheless, the corresponding two-in-an-odd-
path and two-in-an-even-path problems are NP-hard [9, 10], whose state-of-the-
art algorithms on a planar graph take $O(n^{7})$ time [54]. Finding a non-
shortest $uv$-path is easy. A $k$-th shortest $uv$-path can also be found in
near linear time [40]. Nevertheless, the first polynomial-time algorithm for
finding a non-shortest $uv$-path takes $O(n^{18})$ time [8], which is reduced
to $\tilde{O}(n^{2\omega})$ time very recently [16].

Detecting trees spanning a given set of vertices is easy via the connected
components, but detecting induced trees spanning a set of prespecified
vertices is NP-hard [46]. The three-in-a-tree problem is shown to be solvable
first in $O(n^{4})$ time [24] and then in $\tilde{O}(n^{2})$ time [57] via
involved structural theorems and dynamic data structures. The tractability of
the corresponding $k$-in-a-tree problem for any fixed $k\geq 4$ is still
unknown, although the problem can be solved in $O(n^{4})$ time on a graph of
girth at least $k$ [59].

Cycle detection has a similar situation. Detecting cycles of length three,
which have to be induced, is the classical triangle detection problem that can
be solved efficiently by matrix multiplications (see, e. g., [70]). It is
tractable to detect cycles of length at least four spanning two prespecified
vertices (via, e. g., [55, 64]), but the _two-in-a-cycle_ problem that detects
holes spanning two prespecified vertices is NP-hard (and so are the
corresponding one-in-an-even-cycle and one-in-an-odd-cycle problems) [9, 10].
See, e. g., [63, §3.1] for graph classes on which the two-in-a-cycle problem
is tractable.

Detecting cycles without the requirement of spanning prespecified vertices is
straightforward. Even and odd cycles are also long known to be efficiently
detectable (see, e. g., [3, 38, 71]). It takes an $O(n^{2})$-time depth-first
search to detect odd cycles even if the graph is directed (see, e. g., [11,
Table 1]). While detecting holes (i. e., recognizing chordal graphs) is
solvable in $O(n^{2})$ time [66, 67, 68], detecting odd (respectively, even)
holes is more difficult. There are early $O(n^{3})$-time algorithms for
detecting odd and even holes in planar graphs [50, 62], but the tractability
of detecting odd holes was open for decades (see, e. g., [26, 28, 31]) until
the recent major breakthrough of Chudnovsky, Seymour, and Spirkl [23]. Their
$O(n^{9})$-time algorithm is later implemented to run in $O(n^{8})$ time [57],
immediately implying the best formerly known algorithm for recognizing perfect
graphs based on the Strong Perfect Graph Theorem. Finding an odd hole based on
Chudnovsky et al.’s $O(n^{9})$-time (respectively, Lai et al.’s
$O(n^{8})$-time) algorithm for detecting odd holes takes $O(n^{10})$
(respectively, $O(n^{9})$) time. We improve the time of detecting and finding
odd holes and recognizing perfect graphs to $O(n^{7})$.

######  Theorem 1.

For an $n$-vertex $m$-edge graph $G$,

  1. (1)

it takes $O(mn^{5})$ time to either obtain an odd hole of $G$ or ensure that
$G$ is odd-hole-free and, hence,

  2. (2)

it takes $O(n^{7})$ time to determine whether $G$ is perfect.

A shortest cycle of $G$ can be found in $\tilde{O}(n^{\omega})$ time (even if
$G$ is directed) [51]. The time becomes $O(n)$ when $G$ is planar [12]. A
shortest odd cycle of $G$ can be found in $O(n^{3})$ time even if $G$ is
directed (see, e. g., [11, §1]). However, the previously only known
polynomial-time algorithm to find a shortest odd hole of $G$ takes $O(n^{14})$
time [22]. We further reduce the required time to $O(n^{13})$.

######  Theorem 2.

For an $n$-vertex $m$-edge graph, it takes $O(m^{3}n^{7})$ time to either
obtain a shortest odd hole of $G$ or ensure that $G$ is odd-hole-free.

Detecting even cycles in $G$ takes $O(n^{2})$ time [4] and $O(n^{3})$ time
even if $G$ is directed [60, 65]. The first polynomial-time algorithm for
detecting even holes, running in about $O(n^{40})$ time [27, 29, 30]. It takes
a line of intensive efforts in the literature to bring down the complexity to
$O(n^{31})$ [18], $O(n^{19})$ [37], $O(n^{11})$ [13], and finally $O(n^{9})$
[57]. A shortest even cycle of $G$ is long known to be computable in
$O(n^{2})$ time [71]. Very recently, a shortest even cycle of a directed $G$
is shown to be obtainable in $\tilde{O}(n^{4+\omega})$ time with high
probability via an algebraic approach [11]. On the other hand, the
tractability of finding a shortest even hole, open for $16$ years [18, 53], is
recently resolved by an $O(n^{31})$-time algorithm [15] which mostly adopts
the $O(n^{31})$-time algorithm for detecting even holes [18]. We show two
improved algorithms. The less (respectively, more) involved one runs in
$O(n^{25})$ (respectively, $O(n^{23})$) time.

######  Theorem 3.

For an $n$-vertex $m$-edge graph $G$, it takes $O(m^{7}n^{9})$ time to either
obtain a shortest even hole of $G$ or ensure that $G$ is even-hole-free.

###  1.1 Technical overview and related work

Recognizing perfect graphs via detecting odd holes  The first known
polynomial-time algorithm of Chudnovsky, Scott, Seymour, and Spirkl [23] for
detecting odd holes consists of the four subroutines:

  1. (1)

Detecting “jewels” in $O(n^{6})$ time [17, 3.1].

  2. (2)

Detecting “pyramids” in $O(n^{9})$ time [17, 2.2].

  3. (3)

Detecting “heavy-cleanable” shortest odd holes in a graph having no jewel and
pyramid in $O(n^{8})$ time [23, Theorem 2.4].

  4. (4)

Detecting odd holes in a graph having no jewel, pyramid, and heavy-cleanable
shortest odd hole in $O(n^{9})$ time [23, Theorem 4.7].

Lai, Lu, and Thorup [57] improve the complexity to $O(n^{8})$ by reducing the
time of (2), (3), and (4) to $\tilde{O}(n^{5})$ [57, Theorem 1.3], $O(n^{5})$
[57, Lemma 6.8(2)], and $O(n^{8})$ [57, Proof of Theorem 1.4], respectively.
Finding odd holes based on Chudnovsky et al.’s $O(n^{9})$-time (respectively,
Lai et al.’s $O(n^{8})$-time) algorithm for detecting odd holes takes
$O(n^{10})$ (respectively, $O(n^{9})$) time. We further improve the time of
detecting and finding odd holes to $O(n^{7})$ by the following arrangement.

  * •

Extending the concept of a graph containing jewels (respectively, heavy-
cleanable shortest holes and pyramids) to that of a shallow (respectively,
medium and deep) graph (defined in §2).

  * •

Generalizing

    * –

(1) to an $O(n^{7})$-time subroutine for finding a shortest odd hole in a
shallow graph (Lemma 2.2),

    * –

(2) to an $\tilde{O}(n^{6})$-time subroutine for finding an odd hole in a deep
graph (Lemma 2.1), and

    * –

(3) to an $O(n^{5})$-time subroutine for finding a shortest odd hole in a non-
shallow, medium, and non-deep graph (Lemma 2.3).

  * •

Specializing

    * –

(4) to an $O(n^{7})$-time subroutine for finding a shortest odd hole in a non-
shallow, non-medium, and non-deep graph (Lemma 2.4).

Chudnovsky et al.’s $O(n^{9})$-time subroutine for (4) has six procedures. The
$i$-th procedures with $i\in\\{1,2\\}$ (respectively, $i\in\\{3,\ldots,6\\}$)
enumerate all $O(n^{6})$ six-tuples $x=(x_{0},\ldots,x_{5})$ (respectively,
$O(n^{7})$ seven-tuples $x=(x_{0},\ldots,x_{6})$) of vertices and spend
$O(n^{3})$ (respectively, $O(n^{2})$) time for each $x$ to examine whether
there is an odd hole of the $i$-th type that contains all vertices of $x$
other than $x_{0}$. Lai et al.’s $O(n^{8})$-time subroutine for (4) achieves
the improvement by

  1. (a)

reducing the number of enumerated vertices to five and keeping the examination
time in $O(n^{3})$ for the $i$-th procedures with $i\in\\{1,3,5\\}$ and

  2. (b)

keeping the number of enumerated vertices in six and reducing the examination
time to $O(n^{2})$ for the $i$-th procedures with $i\in\\{2,4,6\\}$.

Our specialized $O(n^{7})$-time subroutine for (4) is based on a new
observation that at most five of the vertices in $x$ suffice for each of the
six procedures to pin down an odd hole. Skipping a vertex (i.e., $x_{1}$ or
$x_{2}$ in the proof of Lemma 2.4) to reduce the number of rounds from
$O(n^{6})$ to $O(n^{5})$ complicates the task of examining the existence of an
odd hole containing the remaining five vertices other than $x_{0}$. We manage
to complete the task within the same $O(n^{2})$ time bound via some data
structures.

Finding a shortest odd hole  Our $O(n^{7})$-time algorithm above is almost one
for finding a shortest odd hole. Among the four subroutines, only the one for
(2) may find a non-shortest odd hole. Indeed, our $O(n^{13})$-time algorithm
for finding a shortest odd hole is obtained by replacing our subroutine for
(2) above with an $O(n^{13})$-time one for finding a shortest odd hole in a
deep and non-shallow graph (Lemma 3.1), which improves upon Chudnovsky, Scott,
and Seymour’s $O(n^{14})$-time subroutine [22, 3.2] for finding a shortest odd
hole in a graph containing “great pyramids”, no “jewelled” shortest odd hole,
and no $5$-hole. Chudnovsky et al.’s subroutine enumerates all $O(n^{12})$
twelve-tuples $y=(y_{0},\ldots,y_{11})$ of vertices and finds for each $y$ in
$O(n^{2})$ time with the assistance of $(y_{0},\ldots,y_{4})$ a great pyramid
$H$ containing $\\{y_{5},\ldots,y_{11}\\}$. Specifically, $y_{5}$ is the
“apex” of $H$, $\\{y_{6},y_{7},y_{8}\\}$ forms the “base" of $H$ (see §2), and
$\\{y_{9},y_{10},y_{11}\\}$ consists of the interior marker (defined in §3.1)
vertices of a path of $H$ between its apex and base. Our improved
$O(n^{13})$-time subroutine is based on a new observation (Claim 1 in the
proof of Lemma 3.1, which strengthens [22, 7.2]) that a vertex in the base
$\\{y_{6},y_{7},y_{8}\\}$ of $H$ can be omitted in the enumeration, reducing
the number of rounds from $O(n^{12})$ to $O(n^{11})$, without increasing the
time $O(n^{2})$ to pin down a shortest odd hole.

Finding a shortest even hole  Both of our algorithms follow the approach of
Cheong and Lu [15] and Chudnovsky, Kawarabayashi, and Seymour [18], which is
different from that of Lai et al. [57, §6] for detecting even holes in
$O(n^{9})$ time. Their $O(n^{31})$-time algorithm consists of the following
subroutines:

  1. (1)

Obtaining $O(n^{23})$ sets $X_{i}\subseteq V(G)$ such that at least one
$G_{i}=G-X_{i}$ contains a shortest even hole $C$ of $G$ that is “neat” in
$G_{i}$ (i.e., being either good or shallow in [15, §2], which roughly means
that each shortest $uv$-path of $C$ is a shortest $uv$-path of $G_{i}$) [18,
4.5]. Specifically, Chudnovsky et al. [18, 3.1] show that if a shortest even
hole $C$ of $G$ is not neat in $G$, then $G$ contains “major” vertices [18,
§2] or “clear shortcuts” [18, §3] for $C$. They obtain $O(n^{9})$ subsets
$Y_{j}$ of $V(G)\setminus V(C)$ [18, 2.5] and $O(n^{14})$ subsets $Z_{j,k}$ of
each $V(G-Y_{j})\setminus V(C)$ [18, 4.3 and 4.4]) such that at least one
$Y_{j}$ contains all major vertices of $G$ for $C$ and at least one $Z_{j,k}$
intersects all clear shortcuts of $G-Y_{j}$ for $C$. Thus, $C$ is neat in at
least one of $G-X_{i}$ for the $O(n^{23})$ subsets $X_{i}=Y_{j}\cup Z_{j,k}$
of $V(G)$.

  2. (2)

Finding in $O(n^{8})$ time a shortest even hole in $G_{i}$ that is neat in
$G_{i}$ [15, Lemmas 4 and 5] (see also Lemma 4.3). Specifically, they show
that if $C$ is neat in $G_{i}$, then $8$ equally spaced vertices of $C$
suffice to pin down a shortest even hole of $G_{i}$ via their $O(1)$ pairwise
shortest paths in $G_{i}$.

Based on an observation of Chang and Lu [13, Lemma 3.4] (see also Lemma 4.5),
we reduce the number of the above subsets $Y_{j}$ from $O(n^{9})$ to
$O(n^{3})$ (see Lemma 4.1), immediately leading to an $O(n^{25})$-time
algorithm for finding a shortest even hole (see Theorem 4 in §4). To further
improve the time to $O(n^{23})$, we reduce the number of vertices for (2) from
$8$ to $6$ (see Lemma 4.7 and Figure 5) based on an observation that the
distance of two far apart vertices of $C$ in $G$ can be bounded.

Related work  Finding a longest $uv$-path in $G$ that has to (respectively,
need not) be induced is NP-hard [43, GT23] (respectively, [43, ND29]). See
[41, 42, 61] for how an induced even $uv$-path of $G$ affects the perfection
of $G$. See [56] for a conjecture by Erdős on how an induced $uv$-path of $G$
affects the connectivity between $u$ and $v$ in $G$. See [45, 52] for longest
or long induced paths in special graphs. The presence of long induced paths in
$G$ affects the tractability of coloring $G$ [44]. See also [1] for the first
polynomial-time algorithm for finding a minimum feedback vertex set of a graph
having no induced path of length at least five. See [21, 33] for detecting a
hole with prespecified parity and length lower bound. See [1, 19] for the
first polynomial-time algorithm for finding an independent set of maximum
weight in a graph having no hole of length at least five. See [39] for upper
and lower bounds on the complexity of detecting an $O(1)$-vertex induced
subgraph. See [48] for listing induced paths and holes. See [14, §4] for the
parameterized complexity of detecting an induced path of a prespecified
length. See [32, 49] for determining whether all holes of $G$ have the same
length.

###  1.2 Preliminaries and roadmap

For integers $i$ and $k$, let $[i,k]$ consist of the integers $j$ with $i\leq
j\leq k$ and let $[k]=[1,k]$. Let $|S|$ denote the cardinality of a set $S$.
Let $R\setminus S$ for sets $R$ and $S$ consist of the elements of $R$ that
are not in $S$. Let $E(G)$ for a graph $G$ consist of the edges of $G$ and
$\|G\|=|E(G)|$. A _$k$ -graph_ (e. g., $2$-path or $5$-hole) is a graph having
$k$ edges. A _triangle_ is a 3-cycle. The _length_ of a path or a cycle is its
number of edges. Let $H\subseteq G$ for a graph $H$ denote $V(H)\subseteq
V(G)$ and $E(H)\subseteq E(G)$. Let $G-V$ for a set $V$ of vertices denote
$G[V(G)\setminus V]$. Let $G-v$ for a vertex $v$ be $G-\\{v\\}$. Let
$G\setminus E$ for a set $E$ of edges denote the graph obtained from $G$ by
deleting its edges in $E$. For any $u\in V(G)$, let $N_{G}(u)$ consist of the
vertices $v$ with $uv\in E(G)$ and $N_{G}[u]=\\{u\\}\cup N_{G}(u)$. The
_degree_ of $u$ in $G$ is $|N_{G}(u)|$. A _leaf_ of a graph $G$ is a
degree-$1$ vertex of $G$. Let _$\text{int}(P)$_ consist of the interior
vertices of a path $P$. A _$uv$ -path_ for vertices $u$ and $v$ is a path with
ends $u$ and $v$. A _$UV$ -path_ for vertex sets $U$ and $V$ is a $uv$-path
with $u\in U$ and $v\in V$. Let $T[u,v]$ with $\\{u,v\\}\subseteq V(T)$ for a
tree $T$ denote the simple $uv$-path of $T$. If vertices $u$ and $v$ of $G$
are connected in $G$, then let $d_{G}(u,v)$ denote the length of a shortest
$uv$-path of $G$. Otherwise, let $d_{G}(u,v)=\infty$. For any graph $H$, let
$N_{G}(H)$ consist of the vertices $v\notin V(H)$ with $uv\in E(G)$ for some
$u\in V(H)$ and $N_{G}[H]=V(H)\cup N_{G}(H)$. For any graphs $D$ and $H$, let
$N_{G}(u,D)=N_{G}(u)\cap V(D)$ and $N_{G}(H,D)=N_{G}(H)\cap V(D)$. Graphs $H$
and $D$ are _adjacent_ (respectively, _anticomplete_) in $G$ if
$N_{G}(H,D)\neq\varnothing$ (respectively, $N_{G}[H]\cap V(D)=\varnothing$).

It is convenient to assume that the $n$-vertex $m$-edge graph $G$ of Theorems
1, 2, and 3 are connected for the rest of the paper, which is organized as
follows. Section 2 proves Theorem 1. Section 3 proves Theorem 2. Section 4
proves Theorem 3. Section 5 concludes the paper.

##  2 Recognizing perfect graphs via detecting odd holes

The section assumes without loss of generality that $G$ contains no $5$\- or
$7$-hole, which can be listed in $O(mn^{5})$ time. A $D\subseteq V(G)$ with
$|D|\leq 5$ is a _spade_ for a hole $C$ of $G$ if (1) $C[D]$ is a $uv$-path,
(2) $G[D]$ contains an induced $uv$-path with length $\|C[D]\|+1$ or
$\|C[D]\|-1$, and (3) $C-B$ with
$B=N_{G}[D\setminus\\{u,v\\}]\setminus\\{u,v\\}$ is a shortest $uv$-path of
$G-B$. A hole $C$ of $G$ is _shallow_ if $C$ is a shortest odd hole of $G$ and
there is a spade for $C$. We comment that a jewelled [22] shortest odd hole of
$G$ need not be a shallow hole of $G$ but implies a shallow hole of $G$. Let
$M_{G}(C)$ consist of the (major [18]) vertices $x$ of $G$ such that
$N_{G}(x,C)$ is not contained by any 2-path of $C$. A hole $C$ of $G$ is
_medium_ if $C$ is a shortest odd hole of $G$ and $M_{G}(C)\subseteq N_{G}(e)$
holds for an $e\in E(C)$. Thus, $5$-holes are medium. A medium hole is a
heavy-cleanable shortest odd hole in [22]. A triple $T=(T_{1},T_{2},T_{3})$ of
$ab_{i}$-paths $T_{i}$ for $i\in[3]$ with $\|T_{1}\|<\|T_{2}\|\leq\|T_{3}\|$
is a _tripod_ of $G$ if $\|T_{1}\|$ is minimized over all triples $T$
satisfying the following _Conditions Z_ :

  1.     1. _Z1:_

$B(T)=\\{b_{1},b_{2},b_{3}\\}$ induces a triangle of $G$.

    2. _Z2:_

$U(T)=T_{1}\cup T_{2}\cup T_{3}$ is an induced tree of $G\setminus E(G[B(T)])$
with the leaf set $B(T)$.

    3. _Z3:_

$a(T)=a$ is the only degree-3 vertex of $U(T)$.

    4. _Z4:_

$C(T)=G[T_{2}\cup T_{3}]$ is a shortest odd hole of $G$.

A hole of $G$ is _deep_ if it is $C(T)$ for a tripod $T$ of $G$. Such a
$G[U(T)]$ is called an optimal great pyramid of $G$ with apex $a(T)$ and base
$B(T)$ in [22]. A graph is _shallow_ (respectively, _medium_ and _deep_) if it
contains a shallow (respectively, medium and deep) hole.

######  Lemma 2.1 (Lai, Lu, and Thorup [57, Theorem 1.3]).

It takes $O(mn^{4}\log^{2}n)$ time to obtain a $C\subseteq G$ such that (1)
$C$ is an odd hole of $G$ or (2) $G$ is non-deep.

######  Lemma 2.2.

It takes $O(mn^{5})$ time to obtain a $C\subseteq G$ such that (1) $C$ is a
shortest odd hole of $G$ or (2) $G$ is non-shallow.

######  Lemma 2.3.

It takes $O(mn^{3})$ time to obtain a $C\subseteq G$ such that (1) $C$ is a
shortest odd hole of $G$ or (2) $G$ is shallow, deep, or non-medium.

######  Lemma 2.4.

It takes $O(mn^{5})$ time to obtain a $C\subseteq G$ such that (1) $C$ is a
shortest odd hole of $G$ or (2) $G$ is shallow, medium, deep, or odd-hole-
free.

Lemma 2.2 corresponds to the algorithm for jewelled shortest odd holes in [22,
2.1]. Lemma 2.3 improves on the $O(m^{2}n^{4})$-time algorithm of [22, 6.2].
Lemma 2.4 improves on the $O(m^{2}n^{5})$-time algorithm of [22, 6.3] and the
$O(m^{2}n^{4})$-time algorithm in [57, Proof of Theorem 1.4]. We reduce
Theorem 1 to Lemmas 2.2, 2.3, and 2.4 via Lemma 2.1. Lemmas 2.2, 2.3, and 2.4
are proved in §2.1, §2.2, and §2.3.

###### Proof of Theorem 1.

It suffices to prove (1). It takes $O(m)$ time to determine if one of the four
$C$ is an odd hole of $G$. If there is one, then (1) holds. Otherwise, $G$ is
non-deep by Lemma 2.1, non-shallow by Lemma 2.2, and non-medium by Lemma 2.3,
implying that $G$ is odd-hole-free by Lemma 2.4. ∎

###  2.1 Proving Lemma 2.2

###### Proof of Lemma 2.2.

It takes $O(m)$ time to determine for each $D\subseteq V(G)$ with $|D|\leq 5$
whether $G$ contains odd holes for which $D$ is a spade. If $G$ contains such
odd holes, then let $C_{D}$ be a shortest of them. Otherwise, let
$C_{D}=\varnothing$. If all $C_{D}$ are empty, then let the $O(mn^{5})$-time
obtainable $C$ be empty. Otherwise, let $C$ be a non-empty $C_{D}$ with
minimum $\|C_{D}\|$. If $G$ contains a shallow hole $C^{*}$, then
$0<\|C\|\leq\|C_{D}\|\leq\|C^{*}\|$ holds for a spade $D$ for $C^{*}$,
implying that $C$ is a shortest odd hole of $G$. ∎

###  2.2 Proving Lemma 2.3

A _clean_ hole of $G$ is a medium hole $C$ of $G$ with $M_{G}(C)=\varnothing$.

######  Lemma 2.5.

Let $H$ be an induced subgraph of $G$ containing a shortest odd hole of $G$.

  1. (1)

If $G$ is non-shallow, then so is $H$.

  2. (2)

If $G$ is non-deep, then so is $H$.

######  Lemma 2.6 (Chudnovsky, Scott, and Seymour [22, Proof of Lemma 6.1]).

If $u$ and $v$ are vertices of a clean hole $C$ of a non-shallow and non-deep
graph $H$, then the graph obtained from $C$ by replacing the shortest
$uv$-path of $C$ with a shortest $uv$-path of $H$ remains a clean hole of $H$.

We first reduce Lemma 2.3 to Lemma 2.5 via Lemma 2.6 and then prove Lemma 2.5
in §2.2.1. We also include a proof of Lemma 2.6 in §2.2.2 to ensure that it is
implicit in [22, Proof of Lemma 6.1]. Lemma 2.6 is stronger than [17, Theorem
4.1(2)] in that $G$ is allowed to contain jewels or pyramids. As a matter of
fact, the original proof of [17, Theorem 4.1(2)] already works for Lemma 2.6:
Their careful case analysis shows that if the resulting subgraph is not a
clean hole of $G$, then $G$ contains a jewel or pyramid. It is not difficult
to further infer that each such jewel (respectively, pyramid) in $G$ contains
a shallow (respectively, deep) hole of $G$.

###### Proof of Lemma 2.3.

(Inspired by [57, Proof of Lemma 6.8(2)].) For each $e\in E(G)$ and $u\in
V(G)$, spend $O(m)$ time to obtain a shortest-path tree of
$G-N_{G}(e)\setminus\\{u\\}$ rooted at $u$, from which spend $O(n)$ time for
each $v\in V(G)$ to obtain a shortest $uv$-path $P_{e}(v,u)$, if any, of
$G_{e}(u,v)=G-(N_{G}(e)\setminus\\{u,v\\})$. Let $P_{e}(u,v)=P_{e}(v,u)$ for
each $\\{u,v\\}\subseteq V(G)$ without loss of generality. Thus, it takes
overall $O(mn^{3})$ time to obtain for all edges $e$ and distinct vertices $u$
and $v$ of $G$ with defined $P_{e}(u,v)$ (i) $p_{e}(u,v)=\|P_{e}(u,v)\|$ and
(ii) the neighbor $\phi_{e}(u,v)$ of $u$ in $P_{e}(u,v)$. Let
$p_{e}(u,v)=\infty$ for undefined $P_{e}(u,v)$. Spend $O(mn^{3})$ time to
determine if the following equation holds for any edge $e$ and distinct
vertices $b,c,$ and $d$ of $G$:

$\displaystyle p_{e}(c,d)$ $\displaystyle=3$ (1) $\displaystyle
p_{e}(c,\phi_{e}(d,b))$ $\displaystyle>3$ $\displaystyle
p_{e}(d,\phi_{e}(c,b))$ $\displaystyle>3$ $\displaystyle p_{e}(c,b)$
$\displaystyle=p_{e}(d,b)=p_{e}(c,\phi_{e}(b,d))-1=p_{e}(d,\phi_{e}(b,c))-1.$

If Equation (1) holds for some $(e,b,c,d)$, then let $C=P_{e}(b,c)\cup
P_{e}(b,d)\cup P_{e}(c,d)$ for such an $(e,b,c,d)$ that minimizes
$p_{e}(b,c)+p_{e}(b,d)+p_{e}(c,d)$. Otherwise, let $C=\varnothing$.

We show that if $C^{*}$ is a medium hole of a non-shallow and non-deep graph
$G$, then $C$ is a shortest odd hole of $G$. Let $e$ be an edge of $C^{*}$
with $M_{G}(C^{*})\subseteq N_{G}(e)$. $C^{*}$ is a clean hole of the non-
shallow and non-deep graph $H=G_{e}(c,d)$ with $\\{c,d\\}=N_{C^{*}}(e)$ by
Lemma 2.5. For each $\\{u,v\\}\subseteq V(C^{*})$ such that $\\{c,d\\}$ is
disjoint from the interior of the shortest $uv$-path of $C^{*}$, $P_{e}(u,v)$
is a shortest $uv$-path of $H$. Therefore, Lemma 2.6 implies that
$P_{e}(b,c)\cup P_{e}(b,d)\cup P_{e}(c,d)$ for the $b\in V(C^{*})$ with
$d_{C^{*}}(b,c)=d_{C^{*}}(b,d)$ is a clean hole of $H$ and hence a shortest
odd hole of $G$. One can verify from $\|C^{*}\|\geq 9$ that Equation (1) holds
for this $(e,b,c,d)$. Thus, $C\neq\varnothing$. It remains to show that
Equation (1) for any choice of $(e,b,c,d)$ implies that $P_{e}(b,c)\cup
P_{e}(b,d)\cup P_{e}(c,d)$ is an odd hole of $G$ with length
$p_{e}(b,c)+p_{e}(b,d)+p_{e}(c,d)$: Both $P_{e}(b,c)$ and $P_{e}(b,d)$ are
induced paths. By

$p_{e}(c,b)=p_{e}(d,b)=p_{e}(c,\phi_{e}(b,d))-1=p_{e}(d,\phi_{e}(b,c))-1,$

paths $P_{e}(b,c)-b$ and $P_{e}(b,d)-b$ are anticomplete. The interior of
$P_{e}(c,d)$ is anticomplete to $(P_{e}(c,b)-c)\cup(P_{e}(d,b)-d)$, since
otherwise $p_{e}(c,\phi_{e}(d,b))\leq 3$, $p_{e}(d,\phi_{e}(c,b))\leq 3$,
$p_{e}(c,b)\geq p_{e}(c,\phi_{e}(b,d))$, or $p_{e}(d,b)\geq
p_{e}(d,\phi_{e}(b,c))$ holds, violating Equation (1). ∎

####  2.2.1 Proving Lemma 2.5

###### Proof of Lemma 2.5.

For the first statement, let $H$ contain a shallow hole $C$ for which $D$ is a
spade, implying that $C$ is a shortest odd hole of $G$. Let $C[D]$ be a
$uv$-path. $H[D]$ contains an induced $uv$-path $R$ with length $\|C[D]\|+1$
or $\|C[D]\|-1$. Hence, $G[D]=H[D]$ contains an induced $uv$-path
$Q\in\\{C[D],R\\}$ such that the union $C^{*}$ of $Q=C[D]$ and a shortest
$uv$-path $P$ of $G-N_{G}[D\setminus\\{u,v\\}]\setminus\\{u,v\\}$ is an odd
hole of $G$. Since $G[D]$ contains an induced $uv$-path, i.e., $C[D]$ or $R$
with length $\|C^{*}[D]\|+1$ or $\|C^{*}[D]\|-1$, $D$ is a spade for $C^{*}$
in $G$. Since $H-N_{H}[D\setminus\\{u,v\\}]\setminus\\{u,v\\}$ is an induced
subgraph of $G-N_{G}[D\setminus\\{u,v\\}]\setminus\\{u,v\\}$, we have
$\|P\|\leq\|C\|-\|C[D]\|$. By $\|C^{*}[D]\|\leq\|C[D]\|+1$, $C^{*}$ is a
shortest odd hole of $G$ and thus a shallow hole of $G$.

For the second statement, let $H$ contain a tripod $T$, implying that $C(T)$
is a shortest odd hole of $G$. Either $T$ is a tripod of $G$ or $G$ contains a
tripod $T^{*}$ with $\|T_{1}^{*}\|<\|T_{1}\|$. Thus, $G$ is deep. ∎

####  2.2.2 Proving Lemma 2.6

###### Proof of Lemma 2.6.

(Included to ensure that the lemma is implicit in [22].) Let $u$ and $v$ be
vertices of a clean hole $C$ of a non-shallow and non-deep graph $H$. By [22,
Lemma 4.1], we have $d_{H}(u,v)=d_{C}(u,v)$. By [22, Lemmas 4.2 and 4.3], the
graph obtained from $C$ by replacing the shortest $uv$-path of $C$ with a
$uv$-path of $H$ with length $d_{C}(u,v)$ remains a clean hole of $H$. Hence,
the lemma holds. ∎

###  2.3 Proving Lemma 2.4

Let $M_{G}^{*}(C)=\\{x\in M_{G}(C):|N_{G}(x,C)|\geq 4\\}$, whose elements are
called big major vertices for $C$ in [22].

######  Lemma 2.7.

A shortest odd hole $C$ of $G$ with $M_{G}^{*}(C)\neq M_{G}(C)$ implies a
tripod $T$ of $G$ with $\|T_{1}\|=1$.

######  Lemma 2.8.

If $C$ is a non-shallow shortest odd hole of $G$, then each $x\in
M_{G}^{*}(C)$ admits an $e\in E(C)$ with $M_{G}^{*}(C)\subseteq N_{G}(e)\cup
N_{G}(x)$.

Lemma 2.8 is stronger than [22, Theorem 5.3] in that $G$ can be shallow. We
first reduce Lemma 2.4 to Lemmas 2.7 and 2.8 via Lemmas 2.5 and 2.6. We then
prove Lemmas 2.7 and 2.8 in §2.3.1 and §2.3.2.

(1)$x_{0}$$x_{2}$$x_{1}$$x_{3}$$x_{4}$$x_{5}$

(2)$x_{0}$$y$$x_{2}$$x_{1}$$x_{5}$$x_{4}$$x_{3}$

Figure 1: (1) An example for the proof of Lemma 2.4 with $j=1$ and $k=5$. The
red arc is the shortest $x_{1}x_{k}$-path $P$ of $H$. The blue arc is
$P_{1}(x_{2})$ and the green arc is $P_{k}(x_{2})$. $C_{1}(x_{2})=P\cup
P_{1}(x_{2})\cup P_{k}(x_{2})$ is a shortest odd hole of (1). (2) An example
for the proof of Lemma 2.4 with $j=2$ and $k=4$. The red arc is the shortest
$x_{2}x_{k}$-path $P$ of $H$. The red vertices denote the vertices in $X_{1}$.
Although $y\notin V(H_{1})$ and $y\notin I_{1}$, we have $y\in X_{1}$.
Although $y\in V(G_{1})$, we have $y\notin V(G_{0}(x_{1}))$. The blue arc is
$P_{2}(x_{1})$ and the green arc is $P_{k}(x_{1})$. $C_{2}(x_{1})=P\cup
P_{2}(x_{1})\cup P_{k}(x_{1})$ is a shortest odd hole of (2).

###### Proof of Lemma 2.4.

We first show an $O(n^{2})$-time two-case subroutine that obtains a graph for
each $k\in[3,5]$ and

$\\{x_{0},x_{j},x_{3},x_{4},x_{5}\\}\subseteq V(G)$

with $j\in[2]$ and $x_{4}x_{5}\in E(G)$. If all $O(mn^{3})$ of them are empty,
then let the $O(mn^{5})$-time obtainable graph $C$ be empty. Otherwise, let
$C$ be a shortest of the nonempty ones. We then prove that $C$ is a shortest
odd hole of a non-shallow, non-medium, and non-deep $G$ based on the next
corollary of Lemmas 2.6 and 2.5: If the shortest $uv$-path $C^{*}(u,v)$ of a
shortest odd hole $C^{*}$ of $G$ is contained by a subgraph $H$ of the non-
shallow and non-deep

$G^{*}=G-M_{G}(C^{*}),$

then each shortest $uv$-path $P$ of $H$ is a shortest path of $G^{*}$ and we
call $H$ a _witness_ for $P$.

Case 1: $j=1.$ Let $P$ be a shortest $x_{1}x_{k}$-path of the graph

$H=G-(N_{G}[\\{x_{0},x_{4},x_{5}\\}]\setminus\\{x_{1},x_{3},x_{4},x_{5}\\}),$

as illustrated by Figure 1(a). Let $I$ consist of the interior vertices of all
shortest $x_{1}x_{k}$-paths of $H$. Let

$G_{0}=G-((N_{G}(x_{1})\cap
N_{G}(x_{k}))\cup(N_{G}[I]\setminus\\{x_{1},x_{k}\\})).$

Spend overall $O(n^{2})$ time to obtain for each $i\in\\{1,k\\}$ and $v\in
V(G_{0})$ an arbitrary, if any, shortest $x_{i}v$-path $P_{i}(v)$ of $G_{0}$
and $R_{i}(v)=N_{G_{0}}[P_{i}(v)-v]$. For each $v\in V(G)$, it takes $O(n)$
time to determine if

$C_{1}(v)=P\cup P_{1}(v)\cup P_{k}(v)$

is an odd hole of $G$ via $\|P\|+\|P_{1}(v)\|+\|P_{k}(v)\|\equiv 1$
$(\text{mod }2)$ and $R_{1}(v)\cup V(P_{k}(v))=\\{v\\}$. If none of the $O(n)$
graphs $C_{1}(v)$ is an odd hole of $G$, then report the empty graph.
Otherwise, report a shortest one of the graphs $C_{1}(v)$ that are odd holes.

Case 2: $j=2.$ Let $P$ be a shortest $x_{2}x_{k}$-path of the graph

$H=G-(N_{G}[\\{x_{0},x_{4},x_{5}\\}]\setminus\\{x_{3},x_{4},x_{5}\\}),$

as illustrated by Figure 1(b). Let $I$ consist of the interior vertices of all
shortest $x_{2}x_{k}$-paths of $H$. With

$H_{1}=G-(N_{G}[\\{x_{0},x_{4},x_{5}\\}\cup I]\setminus\\{x_{2}\\}),$

let $I_{1}$ consist of the vertices $v$ with $d_{H_{1}}(v,x_{2})\leq\|P\|-3$.
With $X_{1}=N_{G}(I_{1})$ and

$G_{1}=G-((N_{G}(X_{1})\cap N_{G}(x_{k}))\cup(N_{G}(I_{1}\cup
I)\setminus(X_{1}\cup\\{x_{2},x_{3},x_{4},x_{5}\\}))),$

let each $P_{i}(v)$ with $i\in\\{2,k\\}$ and $v\in V(G)$ be a shortest
$x_{i}v$-path of the graph

$G_{0}(v)=G_{1}-(X_{1}\setminus\\{v\\}).$

It takes overall $O(n^{2})$ time to determine whether $C_{2}(v)=P\cup
P_{2}(v)\cup P_{k}(v)$ is an odd hole of $G$ for any $v\in V(G)$ using similar
data structures in Case 1. If none of the $O(n)$ graphs $C_{2}(v)$ is an odd
hole of $G$, then report the empty graph. Otherwise, report a shortest one of
the graphs $C_{2}(v)$ that are odd holes.

The rest of the proof shows that the next choice of
$j\in[2],k\in[3,5],x_{0}\in M_{G}(C^{*})$, and
$\\{x_{1},\dots,x_{5}\\}\subseteq V(C^{*})$ with $x_{4}x_{5}\in E(C^{*})$
yields a shortest odd hole $C_{j}(x_{3-j})$ of $G$: $M_{G}(C^{*})$ is non-
empty or else $C^{*}$ is medium in $G$. Let $B$ be a longest induced cycle of
$G[C^{*}\cup M_{G}(C^{*})]$ with $|V(B)\cap M_{G}(C^{*})|=1$. Let
$B^{*}=B-x_{0}$ for the vertex $x_{0}\in V(B)\cap M_{G}(C^{*})$. By
$M_{G}(C^{*})\not\subseteq N_{G}(e)$ for any $e\in E(C^{*})$ (or else $C^{*}$
is medium in $G$), we have $\|B^{*}\|\geq 3$. Lemmas 2.7 and 2.8 imply an
$x_{4}x_{5}\in E(C^{*})$ with

$M_{G}(C^{*})\subseteq N_{G}[\\{x_{0},x_{4},x_{5}\\}]$ (1)

Let $k=|V(B^{*})\cap\\{x_{4},x_{5}\\}|+3$. Let $B^{*}$ (respectively,
$B^{*}-\\{x_{4},x_{5}\\})$) be an $x_{1}x_{k}$-path (respectively,
$x_{1}x_{3}$-path) such that an $x_{1}x_{5}$-path of $C^{*}$ contains $x_{3}$
and $x_{4}$. Thus, $N_{G}(x_{4}x_{5})\cap V(B^{*})\subseteq\\{x_{3}\\}$ and
$x_{1},x_{3},x_{4}$, and $x_{5}$ are in order in $C^{*}$. By maximality of
$\|B\|$, we have

$M_{G}(C^{*})\subseteq(N_{G}(x_{1})\cap N_{G}(x_{k}))\cup
N_{G}(\text{int}(B^{*})).$ (2)

Let $j\in[2]$ such that $j=1$ if and only if
$\|B^{*}\|=\|C^{*}(x_{1},x_{k})\|$. $B$ is a hole of $G$ shorter than $C^{*}$
by $x_{0}\in M_{G}(C^{*})$, so $\|B^{*}\|$ is even. Let $x_{2}$ be the
interior vertex of the non-shortest $x_{1}x_{k}$-path of $C^{*}$ with

$\|C^{*}(x_{1},x_{2})\|=\|C^{*}(x_{2},x_{k})\|-j.$ (3)

Thus, $C^{*}(x_{j},x_{k})\subseteq H$. By $x_{0}\in M_{G}(C^{*})$ and
$\|B^{*}\|\geq 3$, we have $\|C^{*}(x_{1},x_{k})\|\geq 3$. By Equation (3), we
have

$C^{*}=C^{*}(x_{1},x_{k})\cup C^{*}(x_{2},x_{k})\cup C^{*}(x_{1},x_{2}).$

Based upon Lemma 2.6, we prove for either case of $j\in[2]$ that

$C_{j}(x_{3-j})=P\cup P_{j}(x_{3-j})\cup P_{k}(x_{3-j})$

is a shortest odd hole of $G$ by the following statements via the
aforementioned corollary of Lemmas 2.6 and 2.5. See Figure 1.

1\. $P$ is a shortest $x_{j}x_{k}$-path of $G^{*}$: By Equation (1), we have
$C^{*}(x_{j},x_{k})\subseteq H\subseteq G^{*}$. $H$ is a witness for $P$.

2\. Each $P_{i}(x_{3-j})$ with $i\in\\{j,k\\}$ is a shortest
$x_{i}x_{3-j}$-path of $G^{*}$: If $j=1$, then $B^{*}=C^{*}(x_{1},x_{k}).$ By
$\text{int}(B^{*})\subseteq I$ and Equation (2), we have
$C^{*}(x_{i},x_{2})\subseteq G_{0}\subseteq G^{*}$ for each $i\in\\{1,k\\}$.
$G_{0}$ is a witness for $P_{1}(x_{2})$ and $P_{k}(x_{2})$. If $j=2$, then
$B^{*}=C^{*}(x_{1},x_{2})\cup C^{*}(x_{2},x_{k}).$ By
$V(C^{*}(x_{1},x_{2})-x_{1})\subseteq I_{1}$ and
$\text{int}(C^{*}(x_{2},x_{k}))\subseteq I$, we have $x_{1}\in X_{1}$ and
$\text{int}(B^{*})\subseteq I_{1}\cup I$. By Equation (2), we have
$B^{*}\subseteq G_{1}$ and $V(G_{1})\cap M_{G}(C^{*})\subseteq X_{1},$
implying $C^{*}(x_{1},x_{i})\subseteq G_{0}(x_{1})\subseteq G^{*}$ for each
$i\in\\{2,k\\}$. $G_{0}(x_{1})$ is a witness for $P_{2}(x_{1})$ and
$P_{k}(x_{1})$. ∎

####  2.3.1 Proving Lemma 2.7

A path $P$ of $C$ is an _$x$ -gap_ (see, e. g., [23]) with $x\in M_{G}(C)$ if
$G[P\cup\\{x\\}]$ is a hole of $G$ (and thus $\|P\|\geq 2)$. The shortestness
of $C$ implies that each $x$-gap is even.

###### Proof of Lemma 2.7.

Let $x\in M_{G}(C)\setminus M_{G}^{*}(C)$, implying that $|N_{G}(x,C)|\leq 3$.
Since $\|C\|$ is odd, there is an edge not in an $x$-gap, implying that
$C[N_{G}(x,C)]$ contains exactly one edge of $C$. Since $x\in M_{G}(C)$, we
have $|N_{G}(x,C)|=3$ and thus $C=C(T)$ for a tripod $T$ of $G$ with
$\|T_{1}\|=1$. ∎

####  2.3.2 Proving Lemma 2.8

A $v\in V(G)$ (respectively, $uv\in E(G)$) is _$X$ -complete_ with $X\subseteq
V(G)$ if $v\in N_{G}(x)$ (respectively, $\\{u,v\\}\subseteq N_{G}(x))$ holds
for each $x\in X$. Abbreviate $\\{x\\}$-complete with $x\in V(G)$ as
$x$-complete. Lemma 2.9 is stronger than [22, Theorem 5.1] in that $G$ can be
shallow.

######  Lemma 2.9.

For any stable $X\subseteq M_{G}^{*}(C)$ for a non-shallow shortest odd hole
$C$ of $G$, the number of $X$-complete edges of $C$ is odd.

We first reduce Lemma 2.8 to Lemma 2.9 and then prove Lemma 2.9.

###### Proof of Lemma 2.8.

Assume for contradiction a $G$ with minimum $|V(G)|$ violating the lemma. We
have $M_{G}^{*}(C)=V(G)\setminus V(C)$. Let $x_{0}\in M_{G}^{*}(C)$ with
$M_{G}^{*}(C)\not\subseteq N_{G}(e)\cup N_{G}(x_{0})$ for each $e\in E(C)$,
which has to be anticomplete to $M_{G}^{*}(C)\setminus\\{x_{0}\\}$ by
minimality of $|V(G)|$. Lemma 2.9 implies an edge $x_{1}x_{2}$ of
$G[M_{G}^{*}(C)]$. Minimality of $|V(G)|$ implies for each $i\in[2]$ an edge
$e_{i}\in E(C)$ that is adjacent to each vertex of
$M_{G}^{*}(C)\setminus\\{x_{3-i}\\}$. Since Lemma 2.9 implies an
$\\{x_{0},x_{i}\\}$-complete edge $f$ of $C$, $G[\\{x_{0},x_{i}\\}\cup e_{i}]$
is not an induced $x_{0}x_{i}$-path $P$ (with $\|P\|=3$) or else $G[P\cup f]$
contains a 5-hole of $G$. Thus, each $i\in[2]$ admits an
$\\{x_{0},x_{i}\\}$-complete end $v_{i}$ of $e_{i}$. By definition of $x_{0}$,
each $x_{i}$ with $i\in[2]$ is anticomplete to $e_{3-i}$. Hence, we have
$v_{1}\neq v_{2}$, implying $v_{1}v_{2}\in E(C)$ or else
$G[\\{x_{1},v_{1},x_{0},v_{2},x_{2}\\}]$ is a $5$-hole. However,
$e=v_{1}v_{2}$ is adjacent to each member of $M_{G}^{*}(C)$: if a $z\in
M_{G}^{*}(C)$ is anticomplete to $e$, then $z\notin\\{x_{0},x_{1},x_{2}\\}$
and $z$ is $\\{e_{1}-v_{1},e_{2}-v_{2}\\}$-complete. Thus, $G[e_{1}\cup
e_{2}\cup\\{z\\}]$ is a $5$-hole, contradiction. ∎

###### Proof of Lemma 2.9.

$C[N_{G}(x)]$ with $x\in X$ cannot be a $3$-path or else $C$ is a shallow hole
of $G$ with a spade $N_{G}(x,C)\cup\\{x\\}$. (This is why $C$ need be non-
shallow). A path $P$ of $C$ is an $xy$-gap with $\\{x,y\\}\subseteq X$ and
$x\neq y$ if

  * •

$P$ is an $\\{x,y\\}$-complete vertex (and thus $\|P\|=0$) or

  * •

$P$ is a $uv$-path with $N_{G}(x,P)=\\{u\\}$ and $N_{G}(y,P)=\\{v\\}$ (and
thus $\|P\|\geq 1$).

We first prove the observation that any odd and even $xy$-gaps $P$ and $Q$ are
disjoint and adjacent: $P$ and $Q$ are disjoint or else $P\cup Q$ contains an
odd $x$-gap. Thus,

$|N_{G}(x,P\cup Q)|=|N_{G}(y,P\cup Q)|=2.$

If $P$ were non-adjacent to $Q$, then $G[P\cup Q\cup\\{x,y\\}]$ is an odd
hole, whose length is $\|C\|$ by shortestness of $C$. By $\\{x,y\\}\subseteq
X$, the two vertices in $C-V(P\cup Q)$ are $\\{x,y\\}$-complete. We have
$\|Q\|\neq 0$ or else $C[N_{G}(x)]$ is a 3-path. Hence, $\|Q\|\geq 2$,
implying an odd $x$-gap in $C[N_{C}[Q]]$, contradiction.

$C$$x$$y$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$
Figure 2: An illustration for the proof of Lemma 2.9 with $X=\\{x,y\\}$. The
circle $C$ with vertex set $\\{v_{1},\dots,v_{9}\\}$ is a shortest odd hole of
the graph.

Assume for contradiction that an $X$ with minimum $|X|$ violates the lemma,
implying $|X|\geq 2$. For each $Y\subseteq X$, let $E_{Y}$ consist of the
$Y$-complete edges of $C$. By the minimality of $X$, $|E_{X}|$ is even and
$|E_{Y}|$ is odd for each $Y\subsetneq X$. Hence,

$\sum_{Y\subseteq X,Y\neq\varnothing}|E_{Y}|$

is even. For each $e\in E(C)$, let $X(e)$ consist of the $V(e)$-complete
vertices of $X$. We have $e\in E_{Y}$ if and only if $Y\subseteq X(e)$ for
each $e\in E(C)$ and $Y\subseteq X$. Therefore, each edge $e$ of

$Z=\bigcup_{Y\subseteq X,Y\neq\varnothing}E_{Y}$

belongs to exactly $2^{|X(e)|}-1$ sets $E_{Y}$ with nonempty $Y\subseteq X$.
Hence,

$\sum_{Y\subseteq X,Y\neq\varnothing}|E_{Y}|=\sum_{e\in Z}(2^{|X(e)|}-1)$

is even and thus $|Z|$ is even. Take Figure 2 for an example, abbreviating
each $E_{\\{v\\}}$ with $v\in V(G)$ as $E_{v}$. $|E_{x}|=|E_{y}|=3$.
$|E_{X}|=|\\{v_{6}v_{7},v_{7}v_{8}\\}|=2$.

$\sum_{Y\subseteq X,Y\neq\varnothing}|E_{Y}|=|E_{x}|+|E_{y}|+|E_{X}|=3+3+2=8.$

$X(v_{1}v_{2})=\\{x\\}$. $X(v_{3}v_{4})=\\{y\\}$.
$X(v_{6}v_{7})=X(v_{7}v_{8})=X$. To see that $e\in E_{Y}$ if and only if
$Y\subseteq X(e)$ for each $e\in E(C)$ and $Y\subseteq X$, observe for
instance that $v_{6}v_{7}\in E_{Y}$ for each $Y\subseteq X(v_{6}v_{7})=X$ and
$\\{x\\}\subseteq X(e)$ for each $e\in E_{x}$. To see that each $e\in
Z=\\{v_{1}v_{2},v_{3}v_{4},v_{6}v_{7},v_{7}v_{8}\\}$ belongs to exactly
$2^{|X(e)|}-1$ sets $E_{Y}$ with nonempty $Y\subseteq X$, observe for example
that $v_{6}v_{7}$ belongs to exactly $2^{|X(v_{6}v_{7})|}-1=3$ sets $E_{Y}$
with nonempty $Y\subseteq X$, that is, $E_{x}$, $E_{y}$, and $E_{X}$. Also,

$\sum_{Y\subseteq
X,Y\neq\varnothing}|E_{Y}|=8=1+1+3+3=2^{|X(v_{1}v_{2})|}-1+2^{|X(v_{3}v_{4})|}-1+2^{|X(v_{6}v_{7})|}-1+2^{|X(v_{7}v_{8})|}-1=\sum_{e\in
Z}(2^{|X(e)|}-1).$

There is an odd $xy$-gap $P$ for an $\\{x,y\\}\subseteq X$ with $x\neq y$: The
paths in $C\setminus Z$ that is not a vertex can be partitioned into pairwise
edge-disjoint $x$-gaps for an $x\in X$ and $xy$-gaps for an
$\\{x,y\\}\subseteq X$ with $x\neq y$ via the following process: for each
$u_{0}u_{1}\in E(C)\setminus Z$ that is not yet in any classified $x$-gap or
$xy$-gap, let $v_{i}$ be the vertex of $C-u_{1-i}$ minimizing
$d_{C-u_{1-i}}(u_{i},v_{i})$ such that $N_{G}(v_{i})\cap X\neq\varnothing$ for
each $i\in\\{0,1\\}$. Let $Q$ be the $v_{0}v_{1}$-path of $C$ containing
$u_{0}u_{1}$. If there is a vertex $x\in X$ with $\\{v_{0},v_{1}\\}\subseteq
N_{G}(x)$, then classify $Q$ as an $x$-gap. Otherwise, classify $Q$ as an
$xy$-gap for an $\\{x,y\\}\subseteq X$ with $x\neq y$. Therefore, since
$\|C\|-|Z|$ is odd and each $x$-gap is even for each $x\in X$, there is an odd
$xy$-gap $P$ for an $\\{x,y\\}\subseteq X$ with $x\neq y$.

There is an even $xy$-gap $Q$: Assume for contradiction that all $xy$-gaps are
odd. Thus, $C$ contains no $\\{x,y\\}$-complete edge, since an
$\\{x,y\\}$-complete vertex of $C$ is an even $xy$-gap. Hence, $C$ contains an
even number of $x$-complete or $y$-complete edges The number of edges of $C$
contained by $x$-gaps or $y$-gaps is also even. Since an edge of $C$ not
contained by any $xy$-gaps has to be an $x$-complete or $y$-complete edge or
contained by an $x$-gap or a $y$-gap, the number of edges in
$Q=C-\text{int}(P)$ that are contained by $xy$-gaps is even. Therefore, then
number of $xy$-gaps in $Q$ is even, implying an $\\{x,y\\}$-complete end of
$Q$, contradicting no even $xy$-gap in $C$.

By the above observation, $P$ and $Q$ are disjoint and adjacent. Thus,
$R=C-V(P\cup Q)$ is an odd $uv$-path of $C$ with
$\min(|N_{G}(x,R)|,|N_{G}(y,R)|)\geq 2$. If $\|R\|=1$, then $R$ is an
$\\{x,y\\}$-complete edge of $C$. $\|Q\|\neq 0$ or else $C[N_{G}(x)]$ is a
3-path. By $\|Q\|\geq 2$, $C[N_{C}[Q]]-V(P)$ is an odd $x$-gap or $y$-gap,
contradiction. If $\|R\|\geq 3$, then $S=R-\\{u,v\\}$ is a path of $C$
disjoint and nonadjacent to $P\cup Q$. By the above observation, $S$ contains
no $xy$-gap, implying $N_{G}(x,S)=\varnothing$ or $N_{G}(y,S)=\varnothing$. If
$N_{G}(x,S)=\varnothing$ (respectively, $N_{G}(y,S)=\varnothing$), then $R$ is
an odd $x$-gap (respectively, $y$-gap), contradiction. ∎

##  3 Finding a shortest odd hole

By Theorem 1, the section assumes without loss of generality that $G$ contains
odd holes and each odd hole of $G$ has length at $15$, since all odd holes
shorter than $15$ can be listed in $O(m^{3}n^{7})$ time.

######  Lemma 3.1.

It takes $O(m^{3}n^{7})$ time to obtain a $C\subseteq G$ such that (1) $C$ is
a shortest odd hole of $G$ or (2) $G$ contains a shallow hole or no deep hole.

Lemma 3.1 improves upon the $O(m^{3}n^{8})$-time algorithm of [22, Lemma 3.2].
We first reduce Theorem 2 to Lemma 3.1 via Lemmas 2.2, 2.3, and 2.4 and then
prove Lemma 3.1 in §3.1.

###### Proof of Theorem 2.

Assume for contradiction that none of the four $C\subseteq G$ ensured by
Lemmas 3.1, 2.2, 2.3, and 2.4 is a shortest odd hole of $G$. By Lemma 2.2, $G$
is non-shallow. By Lemma 3.1, $G$ is non-deep. By Lemma 2.3, $G$ is non-
medium, contradicting Lemma 2.4. Thus, it takes $O(m)$ time to obtain a
shortest odd hole of $G$ from the four $C$. ∎

###  3.1 Proving Lemma 3.1

We call $c=(c_{0},\dots,c_{4})$ with $\\{c_{0},\dots,c_{4}\\}\subseteq V(P)$
an _$\ell$ -marker_ of a $c_{0}c_{4}$-path $P$ if
$d_{P}(c_{0},c_{2})=\lceil\|P\|/2\rceil$,
$d_{P}(c_{0},c_{1})=\min(\ell,d_{P}(c_{0},c_{2}))$, and
$d_{P}(c_{3},c_{4})=\min(\ell,d_{P}(c_{2},c_{4}))$. A _$c$ -trail_ for a
$c=(c_{0},\dots,c_{k})$ with $\\{c_{0},\dots,c_{k}\\}\subseteq V(H)$ for a
graph $H$ is the union of one shortest $c_{i-1}c_{i}$-path of $H$ per
$i\in[k]$.

######  Lemma 3.2 (Chudnovsky, Scott, and Seymour [22, 7.1]).

If $|N_{G}(x)\cap B(T)|\leq 1$ with $x\in M_{G}^{*}(C(T))$ holds for a tripod
$T$ of $G$, then $G[N_{G}(x,T_{1}\cup T_{i})]$ is an edge for an
$\\{i,j\\}=\\{2,3\\}$ with $\|T_{j}\|\geq 3$.

######  Lemma 3.3 (Chudnovsky, Scott, and Seymour [22, 8.1]).

If $\\{u,v\\}\subseteq V(C)$ for a shortest odd hole $C$ of a non-shallow
graph $G$ and $P$ is a $uv$-path of $G$ with $V(P)\cap
M_{G}^{*}(C)=\varnothing$ and $\|P\|\leq\|T_{1}\|$ for a tripod $T$ of $G$,
then $d_{C}(u,v)\leq\|P\|$.

######  Lemma 3.4 (Chudnovsky, Scott, and Seymour [22, 4.2]).

For $\\{u,v\\}\subseteq V(C)$ with $C=C(T)$ for tripod $T$ of a non-shallow
graph $G$, if $P$ is a $uv$-path of $G$ with $V(P)\cap
M_{G}^{*}(C)=\varnothing$ and $\|P\|=d_{C}(u,v)\leq\|T_{1}\|$, then the graph
$C^{\prime}$ obtained from $C$ by replacing the shortest $uv$-path of $C$ with
$P$ remains a shortest odd hole of $G$.

######  Lemma 3.5 (Chudnovsky, Scott, and Seymour [22, 8.3, 8.4, and 8.5]).

Let $T$ be a tripod of a non-shallow graph $G$. Let
$(a,b_{i},b_{j})=(a(T),T_{i}[B(T)],T_{j}[B(T)])$. For any $\|T_{1}\|$-marker
$c=(a,c_{1},c_{2},c_{3},b_{i})$ of $T_{i}$ with $\\{i,j\\}=\\{2,3\\}$, the
triple obtained from $T$ by replacing $T_{i}$ with a $c$-trail of the graph

$G-((M_{G}^{*}(C(T))\cup N_{G}[T_{1}-a]\cup
N_{G}[b_{j}])\setminus\\{a,c_{1},c_{2},c_{3},b_{i}\\})$

remains a tripod of $G$.

We are ready to prove Lemma 3.1 by Lemmas 2.7, 2.8, 2.9, 3.2, 3.3, 3.4, and
3.5.

###### Proof of Lemma 3.1.

For any $c=(c_{0},\dots,c_{k})$ with $\\{c_{0},\dots,c_{k}\\}\subseteq V(H)$
for a graph $H$, let $P_{H}(c_{0},\dots,c_{k})$ be an arbitrary fixed
$c$-trail, if any, of $H$. For each of the $O(m^{2}n^{7})$ choice of
$\\{x,a,c_{1},c_{2},c_{3},d_{1},d_{2}\\}\subseteq V(G)$, $\\{b,e\\}\subseteq
E(G)$ with $b=b_{2}b_{3}$, and $\\{i,j\\}=\\{2,3\\}$, spend $O(m)$ time to
determine whether $G[P_{2}\cup P_{3}]$ is an odd hole of $G$, where

$\displaystyle Y$ $\displaystyle=(N_{G}(x)\cup
N_{G}(e))\setminus(V(e)\cup\\{d_{1},d_{2}\\})$ $\displaystyle G_{1}$
$\displaystyle=G-((Y\cup(N_{G}[b]\setminus(N_{G}(b_{2})\cap
N_{G}(b_{3}))))\setminus\\{a,b_{j}\\})$ $\displaystyle P_{1}$
$\displaystyle=P_{G_{1}}(a,b_{j})-b_{j}$ $\displaystyle G_{i}$
$\displaystyle=G-((Y\cup N_{G}[P_{1}-a]\cup
N_{G}[b_{j}])\setminus\\{a,c_{1},c_{2},c_{3},b_{i}\\})$ $\displaystyle P_{i}$
$\displaystyle=P_{G_{i}}(a,c_{1},c_{2},c_{3},b_{i})$ $\displaystyle G_{j}$
$\displaystyle=G-(N_{G}[(P_{1}\cup P_{i})-a]\setminus\\{a,b_{j}\\})$
$\displaystyle P_{j}$ $\displaystyle=P_{G_{j}}(a,b_{j}).$

If there are such odd holes of $G$, then let the $O(m^{3}n^{7})$-time
obtainable $C$ be a shortest of them. Otherwise, let $C=\varnothing$. We prove
that if $T$ is a tripod of a non-shallow $G$, then $C$ is a shortest odd hole
of $G$ by ensuring that $T^{\prime\prime\prime}=(P_{1},P_{2},P_{3})$ is a
tripod of $G$ for the following choice of
$\\{x,a,c_{1},c_{2},c_{3},d_{1},d_{2}\\}\subseteq V(G)$, $\\{b,e\\}\subseteq
E(C^{*})$ with $C^{*}=C(T)$, and $\\{i,j\\}=\\{2,3\\}$: For each
$i\in\\{2,3\\}$, let $b_{i}=T_{i}[B(T)]$ and $C_{i}=G[T_{1}\cup T_{i}]$. Let
$(a,b)=(a(T),b_{2}b_{3})$. Thus, $a\notin N_{G}(b)$. We first claim the
following statements:

_Claim 1_ : There are $\\{x,d_{1},d_{2}\\}\subseteq V(G)$,
$\\{i,j\\}=\\{2,3\\}$, and $e\in E(C^{*})$ with $M_{G}^{*}(C^{*})\subseteq Y$
and $Y\cap V(C_{i}-\\{a,b_{i}\\})=\varnothing$.

_Claim 2_ : $(P_{1},T_{2},T_{3})$ is a tripod of $G$.

By Claim 1, let $\\{c_{1},c_{2},c_{3}\\}\subseteq V(T_{i})$ so that
$c=(a,c_{1},c_{2},c_{3},b_{i})$ is a $\|T_{1}\|$-marker of $T_{i}$. By Claim
2, $\|P_{1}\|=\|T_{1}\|$ and $\text{int}(T_{i})\cap
N_{G}[P_{1}-a]=\varnothing$. By $M_{G}^{*}(C^{*})\subseteq Y$ and $Y\cap
V(C_{i}-\\{a,b_{i}\\})=\varnothing$, we have

$T_{i}\subseteq G_{i}\subseteq G-((M_{G}^{*}(C(T))\cup N_{G}[T_{1}-a]\cup
N_{G}[b_{j}])\setminus\\{a,c_{1},c_{2},c_{3},b_{i}\\}).$

Thus, $\|P_{i}\|\leq\|T_{i}\|$. By Lemma 3.5, the triple $T^{\prime\prime}$
obtained from $T^{\prime}$ by replacing $T_{i}$ with $P_{i}$ is a tripod of
$G$, implying $\text{int}(T_{j})\cap N_{G}[(P_{1}\cup P_{i})-a]=\varnothing$.
Hence, $T_{j}\subseteq G_{j}$, implying that $\|P_{j}\|\leq\|T_{j}\|$. By
definition of $G_{j}$, $\text{int}(P_{j})\cap N_{G}[(P_{1}\cup
P_{i})-a]=\varnothing$. By $a\notin N_{G}(b)$, $C^{\prime}=G[P_{i}\cup P_{j}]$
is a hole with $\|C^{\prime}\|\leq\|C^{*}\|$. If $\|C^{\prime}\|<\|C^{*}\|$,
then a $G[P_{1}\cup P_{2}\cup P_{3}]-V(P_{k}-a)$ with $k\in[3]$ is an odd hole
of $G$ shorter than $C^{*}$ by $1\leq\|P_{k}\|\leq\|T_{k}\|$ for each
$k\in[3]$, contradiction. Thus, $C^{\prime}$ is a shortest odd hole of $G$,
implying that $T^{\prime\prime\prime}$ is a tripod of $G$. The rest of the
proof shows Claims 1 and 2.

We first prove Claim 1. Assume an $x\in M_{G}^{*}(C)\setminus N_{G}(b)$ or
else the claim holds with $(x,e)=(b_{2},b)$, $d_{1}=T_{1}[B]$, and $d_{2}\in
N_{T_{2}}(b_{2})$. Lemma 2.8 implies an $e\in E(C)$ with minimum
$k=|V(e)\cap\\{a,b_{2},b_{3}\\}|$ such that $M_{G}^{*}(C)$ is contained by the
set

$N=(N_{G}(x)\cup N_{G}(e))\setminus V(e).$

Thus, $x\in N_{G}(e)$. Lemma 3.2 implies an $\\{i,j\\}=\\{2,3\\}$ with
$\|T_{j}\|\geq 3$ such that $G[N_{G}(x,C_{i})]$ for the hole
$C_{i}=G[T_{1}\cup T_{i}]$ is an edge $e_{i}$. Assume for contradiction at
least three vertices in the set

$I=N\cap(V(C_{i})\setminus\\{a,b_{i}\\})=(V(e_{i})\cup
N_{G}(e,C_{i}))\setminus\\{a,b_{i}\\}.$

We have $e\notin E(T_{i})$ or else $x\in N_{G}(e)$ implies $|I|\leq 2$. By
$x\in N_{G}(e)\setminus N_{G}(b)$, we have $e\neq b$, implying $e\in
E(T_{j})$. We have $V(e)\not\subseteq\text{int}(T_{j})$ or else
$N_{G}(e,C_{i})\subseteq\\{a\\}$ implies $|I|\leq 2$. Thus, $e=uv$ with
$u\in\text{int}(T_{j})$ and $v\in\\{a,b_{j}\\}$. If $v=a$, then $v\notin
N_{G}(x)$ or else $|I|=|N_{C_{i}}(a)|=2$. If $v=b_{j}$, then $v\notin
N_{G}(x)$ by $x\notin N_{G}(b)$. By $\|T_{j}\|\geq 3$, the neighbor $w$ of $u$
in $T_{j}-v$ is in $\text{int}(T_{j})$. By minimality of $k$, there is a
vertex

$y\in M_{G}^{*}(C)\setminus((N_{G}(x)\cup N_{G}(uw))\setminus\\{u,w\\}),$

implying that $P=xuvy$ is an induced 3-path of $G$. Lemma 2.9 implies an
$\\{x,y\\}$-complete edge $f$ of $C$. Thus $G[f\cup P]$ contains a 5-hole of
$G$, contradiction. Hence, Claim 1 holds with $\\{d_{1},d_{2}\\}=I$.

It remains to prove Claim 2. Let $b_{1}$ be the end of $P_{1}$ with
$b_{1}b_{j}\subseteq P_{G_{1}}(a,b_{j})$. $G[\\{b_{1},b_{2},b_{3}\\}]$ is a
triangle or else $b_{1}\in N_{G}[b]$ contradicts $b_{1}\in V(G_{1})$. By

$V(T_{1})\cap(N_{G}[b]\setminus(N_{G}(b_{2})\cap N_{G}(b_{3})))=Y\cap
V(C_{i}-\\{a,b_{i}\\})=\varnothing,$

we have $G[V(T_{1})\cup\\{b_{j}\\}]\subseteq G_{1}$, implying

$1\leq\|P_{1}\|\leq\|T_{1}\|$

via $a\notin N_{G}(b)$. Thus, Claim 2 follows from the next claim, which
implies ($V(P_{1}-a)\cap V(T_{k}-a)=\varnothing$ and) $\|P_{1}\|=\|T_{1}\|$ by
the minimality of $\|T_{1}\|$.

_Claim 3_ : Each $D_{k}=G[P_{1}\cup T_{k}]$ with $k\in\\{2,3\\}$ is a hole of
$G$.

To prove Claim 3, assume for contradiction an $e_{k}=u_{1}u_{k}\in
E(G)\setminus\\{b_{1}b_{k}\\}$ for a $k\in\\{2,3\\}$ with $u_{1}\in
V(P_{1}-a)$ and $u_{k}\in V(T_{k}-a)$ (without ruling out the possibility of
$e_{k}\in E(D_{k})$) that minimizes

$d(e_{k})=n\cdot d_{P_{1}}(u_{1},b_{1})+d_{T_{k}}(u_{k},b_{k}),$

as illustrated by Figure 3.

(1)$b_{1}$$u_{1}$$b_{2}$$b_{3}$$u_{3}$$a$

(2)$b_{1}$$u_{1}$$b_{2}$$b_{3}$$u_{3}$$a$

Figure 3: Illustrations for Claim 3 in the proof of Lemma 3.1 with $k=3$. The
circle is a deep hole $C^{*}$ of $G$. $Q$ is the concatenation of the red edge
$u_{1}u_{3}$ and the blue path. $R$ is the concatenation of $u_{1}u_{3}$ and
the orange path. (1) shows Equation (2), since $G[P_{1}\cup T_{k}]-a$ is an
odd hole of $G$ shorter than $C^{*}$. (2) reflects Claim 3, since
$G[P_{1}[u_{1},b_{1}]\cup T_{k}[u_{k},b_{k}]]$ is an odd hole of $G$ shorter
than $C^{*}$.

We deduce a contradiction via the following statements:

  1.     1. _S1:_

$e_{k}\notin E(D_{k})$.

    2. _S2:_

$u_{1}\neq b_{1}$.

    3. _S3:_

$d_{T_{k}}(a,u_{k})\neq d_{P_{1}}(a,u_{1})+1$.

    4. _S4:_

If $\\{u,v\\}\subseteq V(C^{*})$ and $P$ is a $uv$-path of $G$ with
$\text{int}(P)\subseteq V(P_{1})$ and $\|P\|\leq\|T_{1}\|$, then
$d_{C^{*}}(u,v)\leq\|P\|$.

By Statements SS1 and SS2, the (unnecessarily induced) $au_{k}$-path
$Q=P_{1}[a,u_{1}]\cup e_{k}$ of $G$ satisfies
$\|Q\|\leq\|P_{1}\|\leq\|T_{1}\|$. By Statement SS4,

$d_{C^{*}}(a,u_{k})\leq\|Q\|=d_{P_{1}}(a,u_{1})+1,$

implying $d_{C^{*}}(a,u_{k})=d_{T_{k}}(a,u_{k})$ by
$\|Q\|\leq\|P_{1}\|\leq\|T_{1}\|<\|T_{\ell}\|+\|T_{k}[u_{k},b_{k}]\|+1$ with
$\ell=5-k$. Thus, by Statement SS3,

$d_{C^{*}}(a,u_{k})=d_{T_{k}}(a,u_{k})\leq d_{P_{1}}(a,u_{1}).$ (1)

We next prove

$d_{P_{1}}(u_{1},b_{1})+2\leq\|T_{1}\|.$ (2)

Assume $\|T_{1}\|\leq d_{P_{1}}(u_{1},b_{1})+1$ for contradiction. By
$\|P_{1}\|\leq\|T_{1}\|$, we have $\|P_{1}\|=\|T_{1}\|$ and $au_{1}\in
E(P_{1})$. By Equation (1), $au_{k}\in E(P_{k})$. By the choice of
$(u_{1},u_{k})$ and Statement SS2, $G[P_{1}\cup T_{k}]-a$ is a hole of $G$
with length

$\|P_{1}\|+\|T_{k}\|=\|T_{1}\|+\|T_{k}\|<\|C^{*}\|.$

Thus, $\|T_{1}\|+\|T_{k}\|$ is even, implying that $C_{k}$ is an odd hole
shorter than $C^{*}$, contradiction. See Figure 3(1) as an illustration.

Consider the (unnecessarily induced) $u_{k}b_{\ell}$-path $R=e_{k}\cup
P_{1}[u_{1},b_{1}]\cup b_{1}b_{\ell}$ of $G$. By Equation (2) and Statement
SS4, we have $d_{C^{*}}(u_{k},b_{\ell})\leq\|R\|=d_{P_{1}}(u_{1},b_{1})+2$ and
$d_{C^{*}}(u_{k},b_{\ell})=d_{T_{k}}(u_{k},b_{k})+1$ by
$\|R\|\leq\|T_{1}\|<\|T_{\ell}\|+d_{T_{k}}(a,u_{k})$. Thus,

$d_{T_{k}}(u_{k},b_{k})-1\leq d_{P_{1}}(u_{1},b_{1}).$ (3)

Combining Equations (1) and (3), we have

$\|T_{k}\|-1\leq\|P_{1}\|\leq\|T_{1}\|\leq\|T_{k}\|-1$

and thus $d_{T_{k}}(u_{k},b_{k})-1=d_{P_{1}}(u_{1},b_{1})$. By the choice of
$(u_{1},u_{k})$ and Statement S2, $G[P_{1}[u_{1},b_{1}]\cup
T_{k}[u_{k},b_{k}]]$ is a hole of $G$ shorter than $C^{*}$ and it is odd by
$d_{T_{k}}(u_{k},b_{k})-1=d_{P_{1}}(u_{1},b_{1})$, contradiction. See Figure
3(2) as an illustration.

It remains to show Statement SS1, SS2, SS3, and SS4 via the following
equation:

$M_{G}^{*}(C^{*})\cap V(P_{1})=\varnothing,$ (4)

which is immediate from $M_{G}^{*}(C^{*})\subseteq Y$ and the definition of
$G_{1}$.

(1)$u_{1}=b_{1}$$b_{2}$$b_{3}$$u_{3}$$a$

(2)$u_{1}$$y$$b_{2}$$b_{3}$$u_{3}$$a$

Figure 4: The circle in each example is a deep hole $C^{*}$ of the graph. (1)
An illustration for Statement SS1 in the proof of Lemma 3.1. The orange path
is shorter than the green arc, violating Lemma 3.3. (2) An illustration for
Statement SS2 in the proof of Lemma 3.1. The green path is an odd $y$-gap.

Statement SS1: Assume $e_{k}\in E(D_{k})$ for contradiction. By $b_{1}\in
N_{G}[b]$ and $V(T_{k})\cup N_{G}[b]=\varnothing$, we have $b_{1}\notin
V(T_{k})$, implying $u_{1}\notin V(T_{k})$ and $u_{k}\in V(P_{1})$ by the
choice of $(u_{1},u_{k})$. By Equation (4) and Lemma 3.3, we have

$d_{C^{*}}(a,u_{k})\leq d_{P_{1}}(a,u_{k}),$

implying $d_{C^{*}}(a,u_{k})=d_{T_{k}}(a,u_{k})$ by
$d_{P_{1}}(a,u_{k})<\|T_{\ell}\|+1+d_{T_{k}}(b_{k},u_{k})$. Hence,
$d_{P_{1}}(a,u_{k})\geq d_{T_{k}}(a,u_{k})$, implying

$d_{P_{1}}(u_{k},b_{1})\leq d_{T_{k}}(u_{k},b_{k})-1$

by $\|P_{1}\|\leq\|T_{1}\|\leq\|T_{k}\|-1$. By Equation (4) and Lemma 3.3, we
have

$d_{C^{*}}(u_{k},b_{\ell})\leq\|P_{1}[u_{k},b_{1}]\cup
b_{1}b_{\ell}\|=d_{P_{1}}(u_{k},b_{1})+1,$

implying $d_{C^{*}}(u_{k},b_{\ell})=d_{T_{k}}(u_{k},b_{k})+1$ by
$\|P_{1}[u_{k},b_{1}]\cup b_{1}b_{\ell}\|<\|T_{\ell}\|+d_{T_{k}}(a,u_{k})$.
Hence, we have $d_{T_{k}}(u_{k},b_{k})\leq d_{P_{1}}(u_{k},b_{1})$,
contradicting $d_{P_{1}}(u_{k},b_{1})\leq d_{T_{k}}(u_{k},b_{k})-1$. See
Figure 4(1) as an illustration.

Statement SS2: Assume $u_{1}=b_{1}$ for contradiction, implying
$\\{u_{k},b_{2},b_{3}\\}\subseteq N_{G}(u_{1},C^{*})$. By Equation (4),
$|N_{G}(u_{1},C^{*})|\leq 3$, implying
$N_{G}(u_{1},C^{*})=\\{u_{k},b_{2},b_{3}\\}$. By $u_{1}=b_{1}\notin N_{G}(a)$,
$\|T_{1}\|\geq\|P_{1}\|\geq 2$ and thus

$M_{G}(C^{*})=M_{G}^{*}(C^{*})$ (5)

by Lemma 2.7. By Equations (4) and (5), $C^{*}[N_{G}(u_{1},C^{*})]$ is the
2-path $b_{\ell}b_{k}u_{k}$. Thus,

$C_{k}^{*}=G[V(C^{*}-b_{k})\cup\\{u_{1}\\}]$

is a shortest odd hole of $G$. There is a vertex $y\in
M_{G}^{*}(C_{k}^{*})\cap V(P_{1})$ or else Lemma 3.3 with
$\|P_{1}\|\leq\|T_{1}\|$ implies $d_{C_{k}^{*}}(a,u_{1})\leq\|P_{1}\|$,
contradicting $\|P_{1}\|<\|T_{k}\|$ and $\|P_{1}\|<\|T_{\ell}\|+1$. Equations
(4) and (5) imply $yu_{1}\in E(P_{1})$ and that

$G[N_{G}(y,C_{k}^{*}-u_{1})]=G[N_{G}(y,C^{*}-b_{k})]$

is a 2-path nonadjacent to $u_{1}$ or else $G[y\cup N_{G}(y,C_{k}^{*})]$ is a
spade for $C_{k}^{*}$, contradicting that $G$ is non-shallow. Thus,
$C_{k}^{*}$ contains an odd $y$-gap, contradiction. See Figure 4(2) as an
illustration.

Statement SS3: Assume for contradiction
$d_{T_{k}}(a,u_{k})=d_{P_{1}}(a,u_{1})+1$, implying
$d_{C^{*}}(a,u_{k})=d_{T_{k}}(a,u_{k})$ by
$d_{P_{1}}(a,u_{1})+1<\|T_{\ell}\|+\|T_{k}[u_{k},b_{k}]\|+1$. By Statements
SS1 and SS2, we have $\|P_{1}[a,u_{1}]\cup e_{k}\|\leq\|P_{1}\|\leq\|T_{1}\|$,
implying a $(Q_{1},Q_{2},Q_{3})$ with

$(Q_{1},\\{Q_{2},Q_{3}\\})=(P_{1}[u_{1},b_{1}],\\{P_{1}[a,u_{1}]\cup
T_{\ell},e_{k}\cup T_{k}[u_{k},b_{k}]\\})$

satisfying all Conditions Z by Equation (4) and Lemma 3.4, contradicting the
minimality of $\|T_{1}\|$.

Statements SS4 follows from Equation (4) and Lemma 3.3. ∎

##  4 Finding a shortest even hole

By Lai, Lu, and Thorup’s $O(m^{2}n^{5})$-time algorithm for detecting even
holes [57, Theorem 1.6] and the fact that all even holes shorter than $24$ can
be listed in $O(m^{6}n^{11})$ time, the section assumes without loss of
generality that $G$ contains even holes and the length of a shortest even hole
of $G$ is at least $24$. We first prove the following weaker version of
Theorem 3 in §4.1 and then prove Theorem 3 in §4.2.

######  Theorem 4.

It takes $O(mn^{23})$ time to obtain a shortest even hole of $G$.

###  4.1 Our first improved algorithm for finding a shortest even hole

Most of the definitions below are adopted or adjusted from [15, 18]. Let $C$
be a shortest even hole of $G$. Let $J_{G}(C)$ consist of the (major) vertices
$x\in V(G)$ such that $N_{G}(x,C)$ contains three or more vertices that are
pairwise non-adjacent in $G$. $C$ is _clear_ (see, e. g., [57, §6.3]) in $G$
if $J_{G}(C)=\varnothing$.

######  Lemma 4.1.

It takes $O(m^{1.5}n^{2})$ time to obtain $O(mn)$ sets $X_{i}\subseteq V(G)$
such that a shortest even hole of $G$ is clear in at least one $G-X_{i}$.

Let $P$ be a $uv$-path of $G$ for distinct and nonadjacent vertices $u$ and
$v$ of $C$. $P$ is _$C$ -bad_ (called $C$-bad $C$-shortcut in [15]) if (i) the
union of $P$ and any $uv$-path of $C$ is not a shortest even hole of $G$, (ii)
$2\leq\|P\|\leq d_{C}(u,v)$, and (iii) $\|P\|<\frac{\|C\|}{4}$. $P$ is _$C$
-worst_ if it is $C$-bad and either (i) $\|P\|=\|P^{\prime}\|$ and
$d_{C}(u,v)\geq d_{C}(u^{\prime},v^{\prime})$ or (ii) $\|P\|<\|P^{\prime}\|$
holds for each $C$-bad $u^{\prime}v^{\prime}$-path $P^{\prime}$ in $G$. $P$ is
_$C$ -flat_ (called $C$-shallow in [15]) if it is $C$-bad, $\|P\|\geq
d_{C}(u,v)-1$, and $G[P\cup C_{2}]$ for the $uv$-paths $C_{1}$ and $C_{2}$ of
$C$ with $\|C_{1}\|\leq\|C_{2}\|$ is a hole. Observe that $G$ contains a
$C$-worst path if and only if it contains a $C$-bad path.

######  Lemma 4.2 (Chudnovsky, Kawarabayashi, and Seymour [18, Proof of 4.5]).

It takes $O(n^{16})$ time to obtain $O(n^{14})$ sets $X_{i}\subseteq V(G)$
such that for each clear shortest even hole $C$ of $G$, there is an $X_{i}$
with (i) $C\subseteq G-X_{i}$ and (ii) every $C$-worst path in $G-X_{i}$ is
$C$-flat.

A graph $G$ is _flat_ if there is a shortest even hole $C$ of $G$ such that
$G$ contains (i) a $C$-flat $C$-worst path or (ii) no $C$-bad path.

######  Lemma 4.3 (Cheong and Lu [15, Lemmas 4 and 5]).

It takes $O(n^{8})$ time to obtain a $C\subseteq G$ such that (1) $C$ is a
shortest even hole of $G$ or (2) $G$ is not flat.

We comment that Lemma 4.2 is implicit in [18, Proof of 4.5]. Their algorithm
consists of three phases. If we view phases 2 and 3 as one piece, then it goes
like

  1. (1)

getting $O(n^{9})$ subsets $A_{1},\ldots,A_{a}$ of $V(G)$ and

  2. (2)

getting $b_{i}=O(n^{14})$ subsets $B_{i,1}\ldots B_{i,b_{i}}$ of $V(G-X_{i})$
for each $i\in[a]$.

They first show that a shortest even hole $C$ of $G$ is clear in $G-A_{r}$ for
at least one $r\in[a]$. The majority of the proof shows that every $C$-worst
path in $G-A_{r}-B_{r,i}$ is $C$-flat for at least one $i\in[b_{r}]$ based
upon the fact that $C$ is clear in $G-A_{r}$. Lemma 4.2 follows by
substituting its $(G,X_{i})$ with this $(G-A_{r},B_{r,i})$. We first reduce
Theorem 4 to Lemma 4.1 via Lemmas 4.2 and 4.3 and then prove Lemma 4.1 in
§4.1.1.

###### Proof of Theorem 4.

By Lemmas 4.1 and 4.2, it takes $O(mn^{17})$ time to obtain $O(mn^{15})$ sets
$X_{i}\subseteq V(G)$ such that a $G-X_{i}$ contains a shortest even hole $C$
of $G$ and each $C$-worst path in $G-X_{i}$ is $C$-flat. Thus, at least one
$G-X_{i}$ is flat and contains a shortest even hole of $G$. A shortest even
hole of $G$ can be obtained by applying Lemma 4.3 on all $G-X_{i}$ in
$O(mn^{23})$ time. ∎

####  4.1.1 Proving Lemma 4.1

######  Lemma 4.4 (da Silva and Vušković [36, §2]).

It takes $O(m^{1.5}n^{2})$ time to obtain all $O(n^{2})$ maximal cliques of a
$4$-hole-free graph $G$.

######  Lemma 4.5 (Chang and Lu [13, Lemma 3.4]).

If $C$ is a shortest even hole of a $4$-hole-free graph $G$, then either
$J_{G}(C)\subseteq N_{G}(v)$ holds for a vertex $v$ of $C$ or $G[J_{G}(C)]$ is
a clique.

###### Proof of Lemma 4.1.

Apply Lemma 4.4 to obtain all $O(n^{2})$ maximal cliques of $G$ in
$O(m^{1.5}n^{2})$ time. The $O(n^{3})$-time obtainable $O(mn)$ subsets of
$V(G)$ are

  1. (1)

the $O(mn)$ sets $N_{G}(v)\setminus\\{u,w\\}$ for all $2$-paths $uvw$ of $G$
and

  2. (2)

the $O(n^{2})$ sets $V(K)$ for all maximal cliques $K$ of $G$.

Let $C$ be a shortest even hole of $G$. If $J_{G}(C)\subseteq N_{G}(v,C)$ for
a $v\in V(C)$, then $C$ is clear in $G-(N_{G}(v)\setminus\\{u,w\\})$ for the
vertices $u$ and $w$ such that $uvw$ is a $2$-path of $C$. Otherwise,
$J_{G}(C)\subseteq K$ holds for a maximal clique $K$ of $G$ with $V(K)\cap
V(C)=\varnothing$ by Lemma 4.5, implying that $C$ is clear in $G-V(K)$. ∎

###  4.2 Our second improved algorithm for finding a shortest odd hole

######  Lemma 4.6 (Chudnovsky, Kawarabayashi, Seymour [18, §4]).

It takes $O(m^{8}n^{3})$ time to obtain $O(m^{7}n^{3})$ induced subgraphs
$G_{i}$ of $G$ such that at least one $G_{i}$ is flat and contains a shortest
even hole of $G$.

######  Lemma 4.7.

It takes $O(n^{6})$ time to obtain a $C\subseteq G$ such that $C$ is a
shortest even hole of $G$ or $G$ is not flat.

Lemma 4.6 improves upon the $O(n^{25})$-time algorithm of [18, 4.5] (see also
[15, Lemma 3]) that produces $O(n^{23})$ subgraphs. Lemma 4.7 improves upon
the $O(n^{8})$-time algorithm of Lemma 4.3.

###### Proof of Theorem 3.

Immediate by Lemmas 4.6 and 4.7. ∎

It remains to prove Lemmas 4.6 and 4.7 in §4.2.1 and §4.2.2, respectively.

####  4.2.1 Proving Lemma 4.6

We include a proof of Lemma 4.6 to ensure that it is implicit in [18, §4]. The
proof is adjusted from [18, 4.5] with the modification of replacing their
(2.5) by Lemma 4.1. Let $C$ be a shortest even hole of $G$. A $C$-bad
$P=up_{1}\cdots p_{k}v$ is _$C$ -clear_ if

  * •

there is no $C$-flat $P^{\prime}$ with $\text{int}(P)=\text{int}(P^{\prime})$,

  * •

$N_{G}(p_{i},C)=\varnothing$ for each $i$ with $1<i<k$, and

  * •

$C[N_{G}(p_{1},C)]$ and $C[N_{G}(p_{k},C)]$ are vertex disjoint $t$-paths for
a $t\in[2]$.

Let $P=up_{1}\ldots p_{k}v$ be $C$-clear. Let $P$ be of _type $t$_ with
$t\in[2]$ if $C[N_{G}(p_{1})]$ is a $t$-path.

######  Lemma 4.8 (Chudnovsky, Kawarabayashi, and Seymour [18, 4.4]).

It takes $O(m^{2}n^{3})$ time to obtain $O(m^{2}n^{2})$ subsets $Y_{j}$ such
that if $C$ is a clear shortest even hole of $G$ that contains a $C$-clear
$C$-worst path of type $1$, then at least one $G-Y_{j}$ contains $C$ and no
$C$-clear path of type $1$.

######  Lemma 4.9 (Chudnovsky, Kawarabayashi, and Seymour [18, 4.3]).

It takes $O(m^{4}n)$ time to obtain $O(m^{4})$ subsets $Y_{j}$ such that if
$C$ is a clear shortest even hole of $G$ that contains a $C$-clear $C$-worst
path of type $2$, then at least one of $G-Y_{j}$ contains $C$ and no $C$-clear
path of type $2$.

######  Lemma 4.10 (Chudnovsky, Kawarabayashi, and Seymour [18, 3.1]).

If a path $P$ is $C$-worst for a shortest even hole $C$ of $G$, then (i) $P$
is $C$-clear or $C$-flat or (ii) $\text{int}(P)$ consists of a single vertex
of $J_{G}(C)$.

###### Proof of Lemma 4.6.

The algorithm starts with applying Lemma 4.1 on $G$ to obtain $O(mn)$ sets
$X_{i}\subseteq V(G)$ in $O(m^{1.5}n^{2})$ time such that a shortest even hole
$C$ of $G$ is clear in at least one $G_{i}=G-X_{i}$. It then runs the
following symmetric steps.

  1. (1)

Apply Lemma 4.8 on each $G_{i}$ to obtain $O(m^{2}n^{2})$ sets $Y_{ij}$ in
$O(m^{2}n^{3})$ time such that if $C$ is clear in $G_{i}$ that contains a
$C$-clear $C$-worst path of type $1$, then at least one of
$G_{ij}=G_{i}-Y_{ij}$ contains $C$ and no $C$-clear path of type $1$. Apply
Lemma 4.9 on each $G_{ij}$ to obtain $O(m^{4})$ sets $Z_{ijk}$ in $O(m^{4}n)$
time such that if $C$ is clear in $G_{ij}$ that contains a $C$-clear $C$-worst
path of type $2$, then at least one of $G_{ijk}=G_{ij}-Z_{ijk}$ contains $C$
and no $C$-clear path of either type.

  2. (2)

Apply Lemma 4.9 on each $G_{i}$ to obtain $O(m^{4})$ sets $Y_{ij}$ in
$O(m^{4}n)$ time such that if $C$ is clear in $G_{i}$ that contains a
$C$-clear $C$-worst path of type $2$, then at least one of
$G_{ij}=G_{i}-Y_{ij}$ contains $C$ and no $C$-clear path of type $2$. Apply
Lemma 4.8 on each $G_{ij}$ to obtain $O(m^{2}n^{2})$ sets $Z_{ijk}$ in
$O(m^{2}n^{3})$ time such that if $C$ is clear in $G_{ij}$ that contains a
$C$-clear $C$-worst path of type $1$, then at least one of
$G_{ijk}=G_{ij}-Z_{ijk}$ contains $C$ and no $C$-clear path of either type.

The $O(m^{8}n^{3})$-time obtainable $O(m^{7}n^{3})$ graphs are the above
$G_{i}$, $G_{ij}$, and $G_{ijk}$. Assume for contradiction that each of the
above graphs that contains a shortest even hole of $G$ is not flat. Lemma 4.1
implies a $G_{i}$ that contains a shortest even hole $C$ of $G$ such that $C$
is clear in $G_{i}$. Thus, $G_{i}$ is not flat, implying that a $C$-worst
$uv$-path $P$ in $G_{i}$ is not $C$-flat. By Lemma 4.10 and
$J_{G_{i}}(C)=\varnothing$, $P$ is $C$-clear. Let $P$ be of type $t$ with
$t\in[2]$. Lemmas 4.8 and 4.9 imply a $G_{ij}$ that contains $C$ and no
$C$-clear path of type $i$ and thus a $G_{ijk}$ that contains $C$ and no
$C$-clear path of either type. By Lemma 4.10 and $J_{G_{ijk}}(C)=\varnothing$
and the fact that $G_{ijk}$ contains no $C$-clear path, each $C$-worst path of
$G_{ijk}$ is $C$-flat. Thus, $G_{ijk}$ is flat, contradicting the initial
assumption. ∎

####  4.2.2 Proving Lemma 4.7

Let $P(u,v)$ for each $\\{u,v\\}\subseteq V(G)$ be an arbitrary but fixed
shortest $uv$-path of $G$, if there is one. A $3$-tuple
$r=(r_{1},r_{2},r_{3})\in\\{0,1\\}^{3}$ is _nice_ if $r_{1}\geq r_{2}\geq
r_{3}$. Let $a\in S_{r}(a_{1},a_{2},a_{3},a_{4},a_{5})$ for a nice $r$ if
there is an integer $\ell\geq 2$ with

$\displaystyle d_{G}(a_{1},a_{2})\quad$ $\displaystyle=\quad
2\ell+r_{1}+r_{3}$ $\displaystyle d_{G}(a_{2},a_{3})\quad$
$\displaystyle=\quad 2\ell+r_{2}$ $\displaystyle d_{G}(a_{1},a_{3})\quad$
$\displaystyle\geq\quad 2\ell+r_{1}+r_{3}$ $\displaystyle d_{G}(a,a_{1})\quad$
$\displaystyle=\quad 2\ell+r_{1}$ $\displaystyle d_{G}(a,a_{2})\quad$
$\displaystyle\geq\quad 2\ell+r_{1}+r_{3}$ $\displaystyle d_{G}(a,a_{3})\quad$
$\displaystyle=\quad 2\ell+r_{2}+r_{3}$ $\displaystyle d_{G}(a,a_{4})\quad$
$\displaystyle=\quad\ell$ $\displaystyle d_{G}(a,a_{5})\quad$
$\displaystyle=\quad\ell+r_{2}$ $\displaystyle d_{G}(a_{1},a_{4})\quad$
$\displaystyle=\quad\ell+r_{1}$ $\displaystyle d_{G}(a_{3},a_{5})\quad$
$\displaystyle=\quad\ell+r_{3}.$

A $6$-tuple $(a_{1},a_{2},a_{3},b_{1},b_{2},b_{3})$ is _$r$ -valid_ for a nice
$r$ if there is an integer $\ell\geq 2$ such that the following statements
hold with $P_{1}=P(a_{2},b_{1})$, $P_{2}=P(b_{1},a_{1})$,
$P_{3}=P(a_{1},b_{2})$, and $P_{4}=P(a_{3},b_{3})$.

  * •

The length of $P_{1}$ (respectively, $P_{2}$, $P_{3}$ and $P_{4}$) is
$\ell+r_{1}$ (respectively, $\ell+r_{3}$, $\ell+r_{1}$, and $\ell+r_{3}$),

  * •

$G[P_{1}\cup P_{2}]$, $G[P_{2}\cup P_{3}]$ are both paths,

  * •

$P_{1}$ and $P_{3}$ are anticomplete, and

  * •

$P_{i}$ and $P_{4}$ are anticomplete for each $i\in[3]$.

A shortest even hole $C$ is _good_ in $G$ if $G$ contains no $C$-bad path. A
shortest even hole $C$ is _flat_ in $G$ if every $C$-worst path in $G$ is
$C$-flat.

######  Lemma 4.11.

Let $T=(a_{1},a_{2},a_{3},b_{1},b_{2},b_{3})$ be $r$-valid for a nice
$r=(r_{1},r_{2},r_{3})$. If sets $S_{r}(a_{1},a_{2},a_{3},b_{2},b_{3})$ and
$S_{r}(b_{1},b_{2},b_{3},a_{2},a_{3})$ are both nonempty, then $G$ contains an
even hole of length $8\ell+2(r_{1}+r_{2}+r_{3})$, where
$\ell=d_{G}(a_{1},b_{1})-r_{3}$.

######  Lemma 4.12.

If $G$ has a good shortest even hole, then there is an $r$-valid
$T=(a_{1},a_{2},a_{3},b_{1},b_{2},b_{3})$ for a nice $r$ such that both
$S_{r}(a_{1},a_{2},a_{3},b_{2},b_{3})$ and
$S_{r}(b_{1},b_{2},b_{3},a_{2},a_{3})$ are nonempty.

######  Lemma 4.13 (Cheong and Lu [15, Lemma 4]).

For any $n$-vertex graph G, it takes $O(n^{6})$ time to obtain a $C\subseteq
G$ such that (i) $C$ is a shortest even hole of $G$ or (ii) $G$ contains no
flat shortest even hole.

We first reduce Lemma 4.7 to Lemmas 4.11 and 4.12 via Lemma 4.13 and then
prove Lemmas 4.11 and 4.12.

$b$$b_{1}$$a$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$\ell+r_{2}$$\ell$$\ell+r_{1}$$\ell+r_{3}$$\ell+r_{1}$$\ell$$\ell+r_{2}$$\ell+r_{3}$
Figure 5: We guess the $6$ black vertices on $C$ that form a valid $6$-tuple.
Let $a_{2}=b_{4}$, $a_{3}=b_{5}$, $a_{4}=b_{2}$ and $a_{5}=b_{3}$. The
existence of $a$ and $b$ are ensured by $S_{r}$ on the $5$ circles and
rectangles respectively.

###### Proof of Lemma 4.7.

We first compute the following items in $O(n^{6})$ time.

  * •

For each $4$-tuple $(u_{1},u_{2},v_{1},v_{2})$, an indicator for whether
$G[P(u_{1},v_{1})\cup P(u_{2},v_{2})]$ is a path, and an indicator for whether
$P(u_{1},v_{1})$ and $P(u_{2},v_{2})$ are anticomplete.

  * •

For each nice $r$ and $5$-tuple $(a_{1},a_{2},a_{3},a_{4},a_{5})$, an
indicator whether $S_{r}(a_{1},a_{2},a_{3},a_{4},a_{5})$ is non-empty.

Phase $1$ checks for each nice $r=(r_{1},r_{2},r_{3})$ and each $6$-tuple
$T=(a_{1},a_{2},a_{3},b_{1},b_{2},b_{3})$ of vertices whether $T$ is
$r$-valid, $S_{r}(a_{1},a_{2},a_{3},b_{2},b_{3})\neq\varnothing$, and
$S_{r}(b_{1},b_{2},b_{3},a_{2},a_{3})\neq\varnothing$. If so, then record
$8\ell+2(r_{1}+r_{2}+r_{3})$ with $\ell=d_{G}(a_{1},b_{1})-r_{3}$. Maintain
the minimum $m$ of recorded value. Phase $2$ runs Lemma 4.13 and records
$\|C\|$.

We can assume $G$ to be flat, implying a shortest even hole $C$ that is good
or flat in $G$. By Lemma 4.11, $m\geq\|C\|$. If $C$ is good, then by Lemmas
4.11 and 4.12 , we get $m=\|C\|$ in phase $1$. If $C$ is flat, then we get
$\|C\|$ in phase $2$ by Lemma 4.13. ∎

##### Proving Lemma 4.11

###### Proof of Lemma 4.11.

Let $a\in S_{1}=S_{r}(a_{1},a_{2},a_{3},b_{2},b_{3})$ and $b\in
S_{2}=S_{r}(b_{1},b_{2},b_{3},a_{2},a_{3})$. With

$(v_{0},\ldots,v_{7})=(a_{2},b,a_{3},b_{3},a,b_{2},a_{1},b_{1}),$

let each $P_{i}$ with $i\in\\{0,\ldots,7\\}$ be a shortest
$v_{i}v_{i^{+}}$-path in $G$ with $i^{+}=i+1\mod 8$. Let
$d(a_{1},a_{2})=2\ell_{1}+r_{1}+r_{2}$ and
$d(b_{1},b_{2})=2\ell_{2}+r_{1}+r_{2}$. Since $T$ is $r$-valid,
$\ell_{1}=\ell_{2}=\ell$.

(1) $Q_{i}=G[P_{i}\cup P_{i^{+}}]$ is a path for each $i\in\\{0,\ldots,7\\}$.

By $a\in S_{1}$ (respectively, $b\in S_{2}$), we know that $Q_{2}$, $Q_{3}$,
and $Q_{4}$ (respectively, $Q_{0}$, $Q_{1}$ and $Q_{7}$) are paths. Since $T$
is $r$-valid, $Q_{5}$ and $Q_{6}$ are paths.

(2) $P_{i}$ and $P_{j}$ are anticomplete for each
$\\{i,j\\}\subseteq\\{0,\ldots,7\\}$ with $|i-j|>1$.

Since $T$ is $r$-valid, $P_{i}$ and $P_{j}$ are anticomplete for each
$(i,j)\in\\{(2,5),(2,6),(2,7),(5,7)\\}$.

Let $a=a_{0}$ and $b=b_{0}$ for convenience. Suppose that $P_{x}$ and $P_{y}$
are not anticomplete for an $x\in\\{3,4\\}$ and $y\in\\{0,\ldots,7\\}$ with
$|x-y|>1$. Let $P_{x}=P(a,b_{i})$ and $P_{y}=P(a_{j},b_{k})$ with
$i\in\\{2,3\\}$, $j\in\\{1,2,3\\}$ and $k\in\\{0,1,2,3\\}\setminus\\{i\\}$.
Let $\|P_{x}\|=\ell+r^{\prime}_{1}$ and $\|P_{y}\|=\ell+r^{\prime}_{2}$. Note
that $r^{\prime}_{1}\leq r_{2}$. We have (i)
$d_{G}(a,a_{j})+d_{G}(b_{i},b_{k})\leq\|P_{x}\|+\|P_{y}\|+2=2\ell+2+r^{\prime}_{1}+r^{\prime}_{2}\leq
2\ell+2+r_{2}+r^{\prime}_{2}$. By $a\in S_{1}$, and $j\in\\{1,2,3\\}$ we have
(ii) $d_{G}(a,a_{j})\geq 2\ell+\min(r_{1},r_{1}+r_{3},r_{2}+r_{3})\geq
2\ell+r_{2}$. By $\\{b_{i},b_{k}\\}\subseteq S_{2}$ and
$(i,k)\in\\{(2,0),(2,1),(2,3),(3,0),(3,1),(3,2)\\}$ , we have (iii)
$d_{G}(b_{i},b_{k})\geq 2\ell+\min(r_{1}+r_{3},r_{2},r_{2}+r_{3})\geq
2\ell+r_{2}$. Combining equations (i),(ii), and (iii), we get

$4\ell+2r_{2}\leq d_{G}(a,a_{j})+d_{G}(b_{i},b_{k})\leq
2\ell+2+r_{2}+r^{\prime}_{2},$

implying $4\leq 2\ell+r_{2}\leq 2+r^{\prime}_{2}\leq 3$, a contradiction. This
shows that $P_{x}$ and $P_{y}$ are anticomplete for each $x\in\\{3,4\\}$ and
$y\in\\{0,\ldots,7\\}$ with $|x-y|>1$. By symmetry between $a$ and $b$,
$P_{x}$ and $P_{y}$ are anticomplete for each $x\in\\{0,1\\}$ and
$y\in\\{0,\ldots,7\\}$ with $|x-y|>1$. This completes (2).

By (1) and (2), $G[P_{0}\cup\cdots\cup P_{7}]$ is a hole of length
$8\ell+2(r_{1}+r_{2}+r_{3})$ as required. ∎

##### Proving Lemma 4.12

###### Proof of Lemma 4.12.

Let $C$ be a good shortest even hole with $\|C\|=8\ell+2(r_{1}+r_{2}+r_{3})$
for a nice $r=(r_{1},r_{2},r_{3})$. Let
$(a_{2},b,a_{3},b_{3},a,b_{2},a_{1},b_{1})=(v_{0},\ldots,v_{7})$ be vertices
on $C$ in clockwise order with $d_{C}(v_{i},v_{i^{+}})=\ell+q_{i}$, where
$(q_{0},\ldots,q_{7})=(0,r_{2},r_{3},r_{2},0,r_{1},r_{3},r_{1})$. Let
$a_{4}=b_{2}$, $a_{5}=b_{3}$, $b_{4}=a_{2}$ and $b_{5}=a_{3}$.

(1) Let $u$ and $v$ be vertices of $C$. If $d_{C}(u,v)>2\ell+r_{1}+r_{3}$,
then $d_{G}(u,v)\geq 2\ell+r_{1}+r_{3}$.

Assume a $uv$-path $P$ with $\|P\|\leq 2\ell+r_{1}+r_{3}-1$ for contradiction,
implying $\|P\|<\|C\|/4$ and $2\leq\|P\|\leq d_{C}(u,v)$. Let $C_{1}$ and
$C_{2}$ be the $uv$-paths of $C$ with $\|C_{1}\|\leq\|C_{2}\|$. Since $P$ is
not $C$-bad, $G[P\cup C_{2}]$ is and even hole with length
$\|P\|+\|C_{2}\|<\|C_{1}\|+\|C_{2}\|=\|C\|$, contradiction.

(2) Let $u$ and $v$ be vertices of $C$. If $d_{C}(u,v)\leq 2\ell+r_{1}+r_{3}$,
then $d_{G}(u,v)=d_{C}(u,v)$.

Assume a $uv$-path $P$ with $\|P\|\leq d_{C}(u,v)-1$ for contradiction,
implying $\|P\|<\|C\|/4$ and $2\leq\|P\|\leq d_{C}(u,v)$. Let $C_{1}$ and
$C_{2}$ be the $uv$-paths of $C$ with $\|C_{1}\|\leq\|C_{2}\|$. Since $P$ is
not $C$-bad, $G[P\cup C_{2}]$ is and even hole with length
$\|P\|+\|C_{2}\|<\|C_{1}\|+\|C_{2}\|=\|C\|$, contradiction.

By (1), $d_{G}(a,a_{2}),d_{G}(a_{1},a_{3})\geq 2\ell+r_{1}+r_{3}$. By (2), all
the equations regarding $a$ are satisfied and $a\in
S_{r}(a_{1},a_{2},a_{3},a_{4},a_{5})$. By symmetry, $b\in
S_{r}(b_{1},b_{2},b_{3},b_{4},b_{5})$.

It remains to show that $T$ is $r$-valid. Let $P_{1}=P(a_{2},b_{1})$,
$P_{2}=P(b_{1},a_{1})$, $P_{3}=P(a_{1},b_{2})$ and $P_{4}=P(a_{3},b_{3})$. By
(2), $\|P_{1}\|=\ell+r_{1}$, $\|P_{2}\|=\ell+r_{3}$, $\|P_{3}\|=\ell+r_{1}$
and $\|P_{4}\|=\ell+r_{3}$. By (2), $G[P_{1}\cup P_{2}]$ and $G[P_{2}\cup
P_{3}]$ are both shortest paths. Assume for contradiction that $P_{1}$ and
$P_{3}$ are adjacent. We have (i)
$d_{G}(a_{1},a_{2})+d_{G}(b_{1},b_{2})\leq\|P_{1}\|+\|P_{3}\|+2=2\ell+2r_{1}$.
By (2) applied on $(a_{1},a_{2})$ and $(b_{1},b_{2})$ we have (ii)
$4\ell+2r_{1}+2r_{3}=d_{G}(a_{1},a_{2})+d_{G}(b_{1},b_{2})$. Since (i) and
(ii) are contradictory, $P_{1}$ and $P_{3}$ are anticomplete. Assume for
contradiction that $P_{4}$ and $P_{1}$ are adjacent. We have (iii)
$d_{G}(b_{1},b_{3})+d_{G}(a_{2},a_{3})\leq\|P_{4}\|+\|P_{1}\|+2=2\ell+r_{1}+r_{3}+2$.
By (1) and (2) we have (iv) $2\ell+r_{1}+r_{3}+2\ell+r_{2}\leq
d_{G}(b_{1},b_{3})+d_{G}(a_{2},a_{3})$. (iii) and (iv) together imply
$2\ell+r_{2}\leq 2$, a contradiction. Hence $P_{4}$ and $P_{1}$ are
anticomplete. By symmetry $P_{4}$ and $P_{3}$ are anticomplete. Assume for
contradiction that $P_{4}$ and $P_{2}$ are adjacent. We have (v)
$d_{G}(a_{1},a_{3})+d_{G}(b_{1},b_{3})\leq\|P_{4}\|+\|P_{2}\|+2=2\ell+2r_{3}+2$.
By (1) and (2) we have (vi) $4\ell+2r_{1}+2r_{3}\leq
d_{G}(b_{1},b_{3})+d_{G}(a_{2},a_{3})$. (v) and (vi) are contradictory. Hence
$P_{4}$ and $P_{3}$ are anticomplete. Therefore, $T$ is indeed $r$-valid. ∎

##  5 Concluding remarks

Algorithms for induced subgraphs are important and challenging. We give
improved algorithms for (1) recognizing perfect graphs via detecting odd holes
(2) finding a shortest odd hole, and (3) finding a shortest even hole. It is
of interest to further reduce the required time of these three problems. In
particular, the $O(n^{14})$ gap between Lai et al.’s $O(n^{9})$ time for
detecting even holes [57, §6] and our $O(n^{23})$ time for finding a shortest
even hole is still quite large. There are several obstacles in augmenting Lai
et al.’s algorithm, which is basically a faster implementation of Chang and
Lu’s $O(n^{11})$-time algorithm [13], into one for finding a shortest even
hole: (1) An even hole contained by a reported “beetle” need not be a shortest
even hole. (2) Their involved recursive process (based on [29, 30]) to
decompose a graph by “$2$-joins” and “star-cutsets” may change the length of a
shortest even hole. (3) It is unclear how to find a shortest even hole in a
$2$-join-free and star-cutset-free graph that is not an “extended clique
tree”. Techniques to resolve these issues should be interesting.

## References

  * [1] T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzazewski, and P. D. Seymour.  Induced subgraphs of bounded treewidth and the container method.  In D. Marx, editor, Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, pages 1948–1964, 2021.  doi:10.1137/1.9781611976465.116.
  * [2] J. Alman and V. Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In D. Marx, editor, Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, pages 522–539, 2021.  doi:10.1137/1.9781611976465.32.
  * [3] N. Alon, R. Yuster, and U. Zwick.  Color-coding.  Journal of the ACM, 42(4):844–856, 1995.  doi:10.1145/210332.210337.
  * [4] E. M. Arkin, C. H. Papadimitriou, and M. Yannakakis.  Modularity of cycles and paths in graphs.  Journal of the ACM, 38(2):255–274, 1991.  doi:10.1145/103516.103517.
  * [5] C. Berge.  Les problèmes de coloration en théorie des graphes.  Publications de l’Institut de statistique de l’Université de Paris, 9:123–160, 1960.
  * [6] C. Berge.  Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung).  Wissenschaftliche Zeitschrift, Martin Luther Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe, 10:114–115, 1961\.
  * [7] C. Berge.  Graphs.  North-Holland, Amsterdam, New York, 1985.
  * [8] E. Berger, P. D. Seymour, and S. Spirkl.  Finding an induced path that is not a shortest path.  Discrete Mathematics, 344(7):112398.1–112398.6, 2021.  doi:10.1016/j.disc.2021.112398.
  * [9] D. Bienstock.  On the complexity of testing for odd holes and induced odd paths.  Discrete Mathematics, 90(1):85–92, 1991.  doi:10.1016/0012-365X(91)90098-M, see [10] for corrigendum.
  * [10] D. Bienstock.  Corrigendum to: D. Bienstock, “On the complexity of testing for odd holes and induced odd paths” Discrete Mathematics 90 (1991) 85–92.  Discrete Mathematics, 102(1):109, 1992.  doi:10.1016/0012-365X(92)90357-L.
  * [11] A. Björklund, T. Husfeldt, and P. Kaski.  The shortest even cycle problem is tractable.  In S. Leonardi and A. Gupta, editors, Proceedings of the 54th Annual Symposium on Theory of Computing, pages 117–130, 2022.  doi:10.1145/3519935.3520030.
  * [12] H.-C. Chang and H.-I. Lu.  Computing the girth of a planar graph in linear time.  SIAM Journal on Computing, 42(3):1077–1094, 2013.  doi:10.1137/110832033.
  * [13] H.-C. Chang and H.-I. Lu.  A faster algorithm to recognize even-hole-free graphs.  Journal of Combinatorial Theory, Series B, 113:141–161, 2015.  doi:10.1016/j.jctb.2015.02.001.
  * [14] Y. Chen and J. Flum.  On parameterized path and chordless path problems.  In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, pages 250–263, 2007.  doi:10.1109/CCC.2007.21.
  * [15] H.-T. Cheong and H.-I. Lu.  Finding a shortest even hole in polynomial time.  Journal of Graph Theory, 99(3):425–434, 2022.  doi:10.1002/jgt.22748.
  * [16] Y.-C. Chiu and H.-I. Lu.  Blazing a trail via matrix multiplications: A faster algorithm for non-shortest induced paths.  In P. Berenbrink and B. Monmege, editors, Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, LIPIcs 219, pages 23:1–23:16, 2022.  doi:10.4230/LIPIcs.STACS.2022.23.
  * [17] M. Chudnovsky, G. Cornuéjols, X. Liu, P. D. Seymour, and K. Vušković.  Recognizing Berge graphs.  Combinatorica, 25(2):143–186, 2005.  doi:10.1007/s00493-005-0012-8.
  * [18] M. Chudnovsky, K.-i. Kawarabayashi, and P. Seymour.  Detecting even holes.  Journal of Graph Theory, 48(2):85–111, 2005.  doi:10.1002/jgt.20040.
  * [19] M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomassé.  On the maximum weight independent set problem in graphs without induced cycles of length at least five.  SIAM Journal on Discrete Mathematics, 34(2):1472–1483, 2020.  doi:10.1137/19M1249473.
  * [20] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas.  The strong perfect graph theorem.  Annals of Mathematics, 164(1):51–229, 2006.  doi:10.4007/annals.2006.164.51.
  * [21] M. Chudnovsky, A. Scott, and P. Seymour.  Detecting a long odd hole.  Combinatorica, 41(1):1–30, 2021.  doi:10.1007/s00493-020-4301-z.
  * [22] M. Chudnovsky, A. Scott, and P. Seymour.  Finding a shortest odd hole.  ACM Transactions on Algorithms, 17(2):13.1–13.21, 2021.  doi:10.1145/3447869.
  * [23] M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl.  Detecting an odd hole.  Journal of the ACM, 67(1):5.1–5.12, 2020.  doi:10.1145/3375720.
  * [24] M. Chudnovsky and P. Seymour.  The three-in-a-tree problem.  Combinatorica, 30(4):387–417, 2010.  doi:10.1007/s00493-010-2334-4.
  * [25] M. Chudnovsky and P. D. Seymour.  Even pairs in Berge graphs.  Journal of Combinatorial Theory, Series B, 99(2):370–377, 2009\.  doi:10.1016/j.jctb.2008.08.002.
  * [26] M. Chudnovsky and V. Sivaraman.  Odd holes in bull-free graphs.  SIAM Journal on Discrete Mathematics, 32(2):951–955, 2018.  doi:10.1137/17M1131301.
  * [27] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković.  Finding an even hole in a graph.  In Proceedings of the 38th Symposium on Foundations of Computer Science, pages 480–485, 1997.  doi:10.1109/SFCS.1997.646136.
  * [28] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković.  Even and odd holes in cap-free graphs.  Journal of Graph Theory, 30(4):289–308, 1999.  doi:10.1002/(SICI)1097-0118(199904)30:4<289::AID-JGT4>3.0.CO;2-3.
  * [29] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković.  Even-hole-free graphs Part I: Decomposition theorem.  Journal of Graph Theory, 39(1):6–49, 2002.  doi:10.1002/jgt.10006.
  * [30] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković.  Even-hole-free graphs Part II: Recognition algorithm.  Journal of Graph Theory, 40(4):238–266, 2002.  doi:10.1002/jgt.10045.
  * [31] M. Conforti, G. Cornuéjols, X. Liu, K. Vušković, and G. Zambelli.  Odd hole recognition in graphs of bounded clique size.  SIAM Journal on Discrete Mathematics, 20(1):42–48, 2006.  doi:10.1137/S089548010444540X.
  * [32] L. Cook, J. Horsfield, M. Preissmann, C. Robin, P. Seymour, N. L. D. Sintiari, N. Trotignon, and K. Vušković.  Graphs with all holes the same length.  arXiv, 2021.  doi:10.48550/arxiv.2110.09970.
  * [33] L. Cook and P. D. Seymour.  Detecting a long even hole.  European Journal of Combinatorics, 104:103537, 2022.  doi:10.1016/j.ejc.2022.103537.
  * [34] D. Coppersmith and S. Winograd.  Matrix multiplication via arithmetic progressions.  Journal of Symbolic Computation, 9(3):251–280, 1990.  doi:10.1016/S0747-7171(08)80013-2.
  * [35] G. Cornuéjols, X. Liu, and K. Vušković.  A polynomial algorithm for recognizing perfect graphs.  In Proceedings of the 44th Symposium on Foundations of Computer Science, pages 20–27, 2003.  doi:10.1109/SFCS.2003.1238177.
  * [36] M. V. da Silva and K. Vušković.  Triangulated neighborhoods in even-hole-free graphs.  Discrete Mathematics, 307(9):1065–1073, 2007.  doi:10.1016/j.disc.2006.07.027.
  * [37] M. V. G. da Silva and K. Vušković.  Decomposition of even-hole-free graphs with star cutsets and $2$-joins.  Journal of Combinatorial Theory, Series B, 103(1):144–183, 2013\.  doi:10.1016/j.jctb.2012.10.001.
  * [38] S. Dahlgaard, M. B. T. Knudsen, and M. Stöckel.  Finding even cycles faster via capped $k$-walks.  In H. Hatami, P. McKenzie, and V. King, editors, Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pages 112–120. ACM, 2017.  doi:10.1145/3055399.3055459.
  * [39] M. Dalirrooyfard, T. D. Vuong, and V. Vassilevska Williams.  Graph pattern detection: hardness for all induced patterns and faster non-induced cycles.  In Proceedings of the 51st Symposium on Theory of Computing, pages 1167–1178, 2019.  doi:10.1145/3313276.3316329.
  * [40] D. Eppstein.  Finding the $k$ shortest paths.  SIAM Journal on Computing, 28(2):652–673, 1998.  doi:10.1137/S0097539795290477.
  * [41] H. Everett, C. M. H. de Figueiredo, C. L. Sales, F. Maffray, O. Porto, and B. A. Reed.  Path parity and perfection.  Discrete Mathematics, 165-166:233–252, 1997.  doi:10.1016/S0012-365X(96)00174-4.
  * [42] J. Fonlupt and J. Uhry.  Transformations which preserve perfectness and $H$-perfectness of graphs.  In A. Bachem, M. Grötschel, and B. Korte, editors, Bonn Workshop on Combinatorial Optimization, volume 66 of North-Holland Mathematics Studies, pages 83–95. North-Holland, 1982.  doi:10.1016/S0304-0208(08)72445-9.
  * [43] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  Freeman, 1979.
  * [44] S. Gaspers, S. Huang, and D. Paulusma.  Colouring square-free graphs without long induced paths.  In R. Niedermeier and B. Vallée, editors, Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, LIPIcs 96, pages 35.1–35.15, 2018.  doi:10.4230/LIPIcs.STACS.2018.35.
  * [45] E. D. Giacomo, G. Liotta, and T. Mchedlidze.  Lower and upper bounds for long induced paths in 3-connected planar graphs.  Theoretical Computer Science, 636:47–55, 2016.  doi:10.1016/j.tcs.2016.04.034.
  * [46] P. A. Golovach, D. Paulusma, and E. J. van Leeuwen.  Induced disjoint paths in AT-free graphs.  In F. V. Fomin and P. Kaski, editors, Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, Lecture Notes in Computer Science 7357, pages 153–164, 2012.  doi:10.1007/978-3-642-31155-0_14.
  * [47] R. Haas and M. Hoffmann.  Chordless paths through three vertices.  Theoretical Computer Science, 351(3):360–371, 2006.  doi:10.1016/j.tcs.2005.10.021.
  * [48] C. T. Hoàng, M. Kaminski, J. Sawada, and R. Sritharan.  Finding and listing induced paths and cycles.  Discrete Applied Mathematics, 161(4-5):633–641, 2013.  doi:10.1016/j.dam.2012.01.024.
  * [49] J. Horsfield, M. Preissmann, C. Robin, N. L. D. Sintiari, N. Trotignon, and K. Vušković.  When all holes have the same length.  arXiv, 2022.  doi:10.48550/arxiv.2203.11571.
  * [50] W.-L. Hsu.  Recognizing planar perfect graphs.  Journal of the ACM, 34(2):255–288, 1987.  doi:10.1145/23005.31330.
  * [51] A. Itai and M. Rodeh.  Finding a minimum circuit in a graph.  SIAM Journal on Computing, 7(4):413–423, 1978.  doi:10.1137/0207033.
  * [52] L. Jaffke, O.-j. Kwon, and J. A. Telle.  Mim-width I. induced path problems.  Discrete Applied Mathematics, 278:153–168, 2020.  doi:10.1016/j.dam.2019.06.026.
  * [53] D. S. Johnson.  The NP-completeness column.  ACM Transactions on Algorithms, 1(1):160–176, 2005.  doi:10.1145/1077464.1077476.
  * [54] M. Kaminski and N. Nishimura.  Finding an induced path of given parity in planar graphs in polynomial time.  In Y. Rabani, editor, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 656–670, 2012.  doi:10.1137/1.9781611973099.55.
  * [55] K. Kawarabayashi, Y. Kobayashi, and B. A. Reed.  The disjoint paths problem in quadratic time.  Journal of Combinatorial Theory, Series B, 102(2):424–435, 2012\.  doi:10.1016/j.jctb.2011.07.004.
  * [56] M. Kriesell.  Induced paths in 5-connected graphs.  Journal of Graph Theory, 36(1):52–58, 2001.  doi:10.1002/1097-0118(200101)36:1<52::AID-JGT5>3.0.CO;2-N.
  * [57] K.-Y. Lai, H.-I. Lu, and M. Thorup.  Three-in-a-tree in near linear time.  In Proccedings of the 52nd Annual ACM Symposium on Theory of Computing, pages 1279–1292, 2020.  doi:10.1145/3357713.3384235.
  * [58] F. Le Gall.  Powers of tensors and fast matrix multiplication.  In K. Nabeshima, K. Nagasaka, F. Winkler, and Á. Szántó, editors, Proceedings of the International Symposium on Symbolic and Algebraic Computation, pages 296–303, 2014.  doi:10.1145/2608628.2608664.
  * [59] W. Liu and N. Trotignon.  The $k$-in-a-tree problem for graphs of girth at least $k$.  Discrete Applied Mathematics, 158(15):1644–1649, 2010.  doi:10.1016/j.dam.2010.06.005.
  * [60] W. McCuaig.  Pólya’s permanent problem.  Electronic Journal of Combinatorics, 11(1), 2004.  doi:10.37236/1832.
  * [61] H. Meyniel.  A new property of critical imperfect graphs and some consequences.  European Journal of Combinatorics, 8(3):313–316, 1987.  doi:10.1016/S0195-6698(87)80037-9.
  * [62] O. Porto.  Even induced cycles in planar graphs.  In Proceedings of the 1st Latin American Symposium on Theoretical Informatics, pages 417–429, 1992.  doi:10.1007/BFb0023845.
  * [63] M. Radovanovic, N. Trotignon, and K. Vušković.  The (theta, wheel)-free graphs part IV: induced paths and cycles.  Journal of Combinatorial Theory, Series B, 146:495–531, 2021.  doi:10.1016/j.jctb.2020.06.002.
  * [64] N. Robertson and P. D. Seymour.  Graph minors. XIII. The disjoint paths problem.  Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.  doi:10.1006/jctb.1995.1006.
  * [65] N. Robertson, P. D. Seymour, and R. Thomas.  Permanents, pfaffian orientations, and even directed circuits.  Annals of Mathematics, 150(3):929–975, 1999.  doi:10.2307/121059.
  * [66] D. Rose, R. Tarjan, and G. Lueker.  Algorithmic aspects of vertex elimination on graphs.  SIAM Journal on Computing, 5(2):266–283, 1976.  doi:10.1137/0205021.
  * [67] R. E. Tarjan and M. Yannakakis.  Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs.  SIAM Journal on Computing, 13(3):566–579, 1984.  doi:10.1137/0213035, see [68] for addendum.
  * [68] R. E. Tarjan and M. Yannakakis.  Addendum: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs.  SIAM Journal on Computing, 14(1):254–255, 1985.  doi:10.1137/0214020.
  * [69] V. Vassilevska Williams.  Multiplying matrices faster than Coppersmith–Winograd.  In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 887–898, 2012.  doi:10.1145/2213977.2214056.
  * [70] V. V. Williams and R. R. Williams.  Subcubic equivalences between path, matrix, and triangle problems.  Journal of the ACM, 65(5):27:1–27:38, 2018.  doi:10.1145/3186893.
  * [71] R. Yuster and U. Zwick.  Finding even cycles even faster.  SIAM Journal on Discrete Mathematics, 10(2):209–222, 1997.  doi:10.1137/S0895480194274133.