A Faster Algorithm to Recognize EvenHoleFree Graphs^{†}^{†}thanks: To appear in Journal of Combinatorial Theory, Series B. The current version slightly improves upon the preliminary version [4] appeared in SODA 2012: (a) The time complexity for recognizing evenholefree node edge graphs is reduced from to , which is an improvement if ; and (b) if contains even holes, then the current version shows how to output an even hole of also in time.
Abstract
We study the problem of determining whether an node graph contains an even hole, i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomialtime algorithm for the problem, which runs in time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to . The best previously known algorithm for the problem, due to da Silva and Vušković, runs in time. In this paper, we solve the problem in time via a decompositionbased algorithm that relies on the decomposition theorem of da Silva and Vušković. Moreover, if contains even holes, then our algorithm also outputs an even hole of in time.
Keywords
even hole, decompositionbased detection algorithm, extended clique tree, join, starcutset, diamond, beetle, tracker,
1 Introduction
For any graphs and , we say that contains if is isomorphic to an induced subgraph of . If does not contain , then is free. For any family of graphs, is free if is free for each graph in . A hole is an induced simple cycle consisting of at least four nodes. A hole is even (respectively, odd) if it consists of an even (respectively, odd) number of nodes. Evenholefree graphs have been extensively studied in the literature (see, e.g., [13, 14, 15, 20, 1, 38, 21, 30]). See Vušković [43] for a recent survey. This paper studies the problem of determining whether a graph contains even holes. Let be the number of nodes of the input graph. Conforti, Cornuéjols, Kapoor, and Vušković [12, 16] gave the first polynomialtime algorithm for the problem, which runs in time [7]. Later, Chudnovsky, Kawarabayashi, and Seymour [7] reduced the running time to . Chudnovsky et al. [7] also observed that the running time can be further reduced to as long as prisms can be detected efficiently, but Maffray and Trotignon [31] showed that detecting prisms is NPhard. The best previously known algorithm for the problem, due to da Silva and Vušković [21], runs in time. We solve the problem in time, as stated in the following theorem.
Theorem 1.1.
It takes time to determine whether an node edge connected graph contains even holes.
Technical overview
The time algorithm of Conforti et al. [16] is based on their decomposition theorem [15] stating that a connected evenholefree graph either (i) is an extended clique tree or (ii) contains nonpath joins or starcutsets with . The main body of their algorithm recursively decomposes the input graph into a list of a polynomial number of smaller or simpler graphs using nonpath joins or starcutsets with until each graph in does not contain any of the mentioned cutsets. Since even holes in extended clique trees can be detected in polynomial time, it suffices for their algorithm to ensure the evenholepreserving condition of : is evenholefree if and only if all graphs in are evenholefree. To ensure the condition of , their algorithm requires a cleaning process to either detect an even hole in or remove bad structures from before obtaining from . The time algorithm Chudnovsky et al. [7], which is not based upon any decomposition theorem but still requires the cleaning process, looks for even holes directly. (The algorithms of Chudnovsky et al. [6] for recognizing perfect graphs are also of this type of nondecompositionbased algorithms.) The time algorithm of da Silva and Vušković [21], adopting the decompositionbased approach, relies on a stronger decomposition theorem stating that if a connected evenholefree graph has no starcutsets and nonpath joins, then it is an extended clique tree. Since starcutsets with need not be taken into account, the decomposition process is significantly simplified, leading to a much lower time complexity. Our time algorithm is also based on the brilliant decomposition theorem of da Silva and Vušković [21]. Our improvement is obtained via the new idea of trackers, which allow for fewer graphs to be generated in the process of decomposition using starcutsets. The cleaning process is also sped up by an algorithm for recognizing beetlefree graphs, based upon the threeinatree algorithm of Chudnovsky and Seymour [10].
Specifically, our recognition algorithm for evenholefree graphs consists of two phases. Throughout the paper, a hole (respectively, cycle and path) is a node hole (respectively, cycle and path). The first phase (see Lemma 2.3) either (1) ensures that the input graph contains even holes via the existence of a “beetle” (see §2 and Figure 2(a)) or a hole in or (2) produces a set of “trackers” of , where is a beetlefree and holefree induced subgraph of and is a path of . satisfies the following evenholepreserving condition (see Condition L1): If contains even holes, then at least one element of is “lucky” such that a shortest even hole of is a subgraph of and the following holds: (a) is a path of and (b) the neighborhood of in is “super clean” (i.e., using notation defined in §2). The second phase applies an algorithm (see Lemma 2.4) on each tracker to either ensure that contains even holes or ensure that is not lucky. If all trackers in are not lucky, then the evenholepreserving condition of implies that is evenholefree. Otherwise, an induced subgraph of contains an even hole, implying that contains even holes.
The recognition algorithm for beetlefree graphs (see the proof of Lemma 2.3) in the first phase is based on Chudnovsky and Seymour’s threeinatree algorithm [10] (see Theorem 3.1). If contains beetles or holes, then contains even holes. Otherwise, if contains even holes, then the neighborhood of each shortest even hole of is “clean” (i.e., , see the proof of Lemma 2.2). To further ensure that the neighborhood of is super clean, we generate a set of “super cleaners” , where is a node subset of and is a path of , such that at least one super cleaner satisfies and for some shortest even hole of (see the proof of Lemma 2.3). The set consisting of the trackers with satisfies the required evenholepreserving condition. The underlying technique of guessing “bad nodes” of (using Lemmas 3.4, 3.5, and 3.6) to be removed by super cleaners is called “cleaning” in the literature (see, e.g., Vušković [43, §4]).
The algorithm applied on each tracker in the second phase relies on the decomposition theorem of da Silva and Vušković [21] (see Theorem 4.9). Since even holes can be efficiently detected in an extended clique tree (see Lemma 4.6, which is a slightly faster implementation of the algorithm of da Silva and Vušković [21]), our algorithm performs two stages of evenholepreserving decompositions on , first via starcutsets and then via nonpath joins, until each of the resulting graphs either is an extended clique tree or has nodes. If all of the resulting graphs are evenholefree, then is not lucky; otherwise, contains even holes. As noted by Chvátal [11] (see Lemma 4.3), if has no dominated nodes, then a starcutset of has to be a full starcutset of , which can be efficiently detected. Thus, at the beginning of each decomposition in the first stage, we preprocess by deleting all dominated nodes of and carefully updating nodes , , and such that the luckiness of is preserved (see Lemma 4.4). The correctness of this preprocessing step relies on the fact that is beetlefree and the requirement for to be lucky that the neighborhood of some shortest even hole in with is super clean. Path is crucial in the stage of decompositions via starcutsets for the graph having no dominated nodes. Specifically, if is a starcutset of , then by merely examining the neighborhood of path in , we can efficiently identify a connected component of such that preserves the luckiness of (see Step 3 in the proof of Lemma 4.1). We then let and repeat the above procedure for iterations until has no starcutsets. The second stage, i.e., decompositions via nonpath joins for graphs having no starcutsets, is based upon the detection algorithm for nonpath joins of Charbit et al. [5] (see Lemma 4.8). This stage decomposes an edge graph having no starcutsets into a set of smaller graphs, each of which either consists of nodes or is an extended clique tree (see the proof of Lemma 4.2).
Related work
Evenholefree planar graphs [34] can be recognized in time. It is NPcomplete to determine whether a graph contains an even (respectively, odd) hole that passes a given node [2, 3]. The Strong Perfect Graph Theorem of Chudnovsky, Robertson, Seymour, and Thomas [8] states that a graph is perfect if and only if both and the complement of are oddholefree. Although perfect graphs can be recognized in time [6], the tractability of recognizing oddholefree graphs remains open (see, e.g., [26]). Polynomialtime algorithms for detecting odd holes are known for planar graphs [25], clawfree graphs [37, 29], and graphs with bounded clique numbers [17]. Graphs containing no holes (i.e., chordal graphs) can be recognized in time [39, 40, 35, 36]. Graphs containing no holes consisting of five or more nodes (i.e., weakly chordal graphs) can be recognized in time [32, 33]. It takes time to detect a hole that passes any given nodes in an genus graph [27, 28]. See [9, 44, 22, 18] for more results on oddholefree graphs.
Road map
The rest of the paper is organized as follows. Section 2 gives the preliminaries and proves Theorem 1.1 by Lemmas 2.3 and 2.4. Section 3 proves Lemma 2.3. Section 4 proves Lemma 2.4. Section 5 concludes the paper by explaining how to augment our proof of Theorem 1.1 into an time algorithm that outputs an even hole of an node edge graph containing even holes.
2 Preliminaries and the topmost structure of our proof
Unless clearly specified otherwise, all graphs throughout the paper are simple and undirected. Let denote the cardinality of set . Let be a graph. Let consist of the nodes in . For any subgraph of , let denote the subgraph of induced by . Subgraphs and of graph are adjacent in if some node of and some node of are adjacent in . For any subset of , let . For any subgraph of , let consist of the nodes of that are adjacent to in and let .
Let be a hole of . Let be a node in . Let . We say that is a major node [7] of in if at least three distinct nodes of are pairwise nonadjacent in . Let consist of the major nodes of in . For instance, in Figure 1, and .
Lemma 2.1 (Chudnovsky et al. [7, Lemma 2.2]).
If is a shortest even hole of graph and , then is even.
If , then and has at most two connected components. Moreover, if is not connected, then each connected component of has at most two nodes. Let with consist of the nodes such that and is connected. Let with consist of the nodes such that is not connected and the two connected components of has and nodes, respectively. We have
(1) 
We say that is a clean hole of if . We say that is a hole of if is a path of and is a clean shortest even hole of . For instance, if is as shown in Figure 1, then is a hole of . If is an induced subgraph of and is a path of , then we call a tracker of . A tracker of is lucky if there is a hole of . If there are lucky trackers of , then contains even holes. Therefore, a set of trackers of satisfying the following evenholepreserving condition reduces the problem of determining whether is evenholefree to the problem of determining whether all trackers in are not lucky:

If contains even holes, then at least one element of is a lucky tracker of .
An induced subgraph of is a beetle of if consists of (1) a cycle with exactly one chord (i.e., a diamond [30, 16] of ) and (2) a tree of having exactly three leaves , , and with the property that is an induced tree of not adjacent to . See Figure 2(a) for an illustration. Node (respectively, and ) is the neighbor of (respectively, and ) in . Node is the only degree node of . Note that at least one of the three cycles in , , and is an even hole of . Nodes , , , and need not be distinct. For instance, as illustrated by Figure 2(b), if is a hole of and is a node of , then is a beetle of .
Lemma 2.2.
If is a beetlefree graph, then holds for any clean shortest even hole of .
Proof.
By and Equation (1), it suffices to show . If as illustrated by Figure 2(b), then is a beetle of , a contradiction. If , then let , , and be the nodes of such that and are adjacent in , as illustrated by Figure 2(c). Let be the path of between and . Let be the path of between and . Either or is an even hole of shorter than , a contradiction. ∎
2.1 Proving Theorem 1.1
Lemma 2.3.
It takes time to complete either one of the following tasks for any node edge graph . Task 1: Ensuring that contains even holes. Task 2: (a) Ensuring that is beetlefree and (b) obtaining a set of trackers of that satisfies Condition L1.
Lemma 2.4.
Given a tracker of an node edge beetlefree graph , it takes time to either ensure that contains even holes or ensure that is not lucky.
Proof of Theorem 1.1.
3 Proving Lemma 2.3
A clique of is a complete subgraph of . A clique of is maximal if it is not contained by other cliques of . We need the following theorem and three lemmas to prove Lemma 2.3.
Theorem 3.1 (Chudnovsky and Seymour [10]).
Let , , and be three nodes of an node graph. It takes time to determine whether the graph contains an induced tree with .
Lemma 3.2 (Farber [23, Proposition 2] and da Silva and Vušković [20]).
Let be an node edge holefree graph. It takes time to either ensure that contains even holes or obtain all maximal cliques of .
Lemma 3.3 (da Silva and Vušković [20]).
The number of maximal cliques in an node edge evenholefree graph is at most .
Lemma 3.4 (Chudnovsky, Kawarabayashi, and Seymour [7, Lemma 4.2]).
For any shortest even hole of a holefree graph , there is an edge of with .
Lemma 3.5.
For any shortest even hole of a holefree graph , if is not a clique of , then there is a node of with .
Before working on the proof of Lemma 3.5, we first prove Lemma 2.3 using Theorem 3.1 and Lemmas 3.2, 3.3, 3.4, and 3.5.
Proof of Lemma 2.3.
We claim that contains beetles if and only if at least one of the choices of node and three distinct edges , , and of satisfies all of the following four conditions:

is the cycle with exactly one chord .

The edges between and are exactly , , and .

, but nodes , , and need not be distinct.

There is an induced tree of with .
The claim can be verified by seeing that if is the minimal subtree of satisfying , then is a tree of with leaf set having the property that is an induced tree of not adjacent to . By the claim above and Theorem 3.1, it takes time to determine whether contains beetles. It takes time to determine whether contains holes. If contains holes or beetles, then contains even holes. The lemma is proved by completing Task 1 in time. The rest of the proof assumes that is holefree and beetlefree.
By Lemma 3.2, it takes time to either ensure that contains even holes or obtain the maximal cliques of . If contains even holes, then the lemma is proved by completing Task 1 in time. Otherwise, we have all the maximal cliques of . If the number of maximal cliques in is larger than , then Lemma 3.3 implies that contains even holes, also proving the lemma by completing Task 1. If the number of maximal cliques in is or fewer, then let consist of the trackers of that are in the form of or with
where and are edges of and is a maximal clique of . We have . Since all maximal cliques of are available, can be computed in time time. To ensure the completion of Task 2, it remains to prove that satisfies Condition L1. Suppose that contains even holes. Let be an arbitrary shortest even hole of . The following case analysis shows that there are lucky trackers of in .
Case 1: holds for a node of . Let and be the neighbors of in . By and Lemma 3.4, there is an edge of with . By the choices of and , we have . Since is an edge of hole , we have . Thus, , implying that is a clean hole of and is a path of . Since is a shortest even hole of , is also a shortest even hole of . Therefore, is a hole of .
Case 2: holds for all nodes of . By Lemma 3.5, is a clique of . Let be a maximal clique of with . Combining with Lemma 3.4, there is an edge of with . We have or else implies for any node , a contradiction. Since is an edge of , we have . Thus, , implying that is a clean hole of . Letting be the neighbor of in other than , is a path of . Since is a shortest even hole of , is also a shortest even hole of . Therefore, is a hole of . ∎
The rest of the section proves Lemma 3.5. An edge of hole is a gate [7] of with respect to major nodes and of if both of the following conditions hold:

There are two edges and and at least one of edges and .

There is a node of such that (respectively, ) is not adjacent to (respectively, ), where (respectively, ) is the path of between (respectively, ) and that passes (respectively, ).
See Figure 3(a) for an illustration.
Lemma 3.6 (Chudnovsky et al. [7, Lemmas 2.3 and 2.4]).
The following statements hold for any shortest even hole of a holefree graph .

If and are nonadjacent nodes of , then there is a gate of with respect to and in .

If is a subset of with such that has at most one edge, then holds for some node of .
Proof of Lemma 3.5.
Let and be two nonadjacent nodes of . Let consist of the nodes of that are adjacent to both of and . By Lemma 3.6(1), there is a gate of with respect to and . We have , where is a node of ensured by Condition G2. Assume . By Condition G1, is adjacent to or in or else one of and would be a hole of . If is adjacent to as illustrated by Figure 3(b), then Condition G2 implies , which contradicts with . If is adjacent to as illustrated by Figure 3(c), then Condition G2 implies , which contradicts with . Therefore, , and thus . The lemma holds trivially if . To prove the lemma for , we first show the claim: “Each node is adjacent to .” If one of and is not adjacent to , then the claim follows from Lemma 3.6(2). If both of and are adjacent to , then each node is adjacent to in or else is a hole, a contradiction. The claim is proved.
By the claim above, the lemma holds if or . It remains to consider the cases with and (thus, there are edges and ) by showing that either or is adjacent to each node . Assume and for contradiction. By the claim above, and are edges of . We know or else is a hole. See Figure 4(a). Observe that cannot be adjacent to both of and or else is a hole. Case 1: is not adjacent to . By Lemma 3.6(2), a node of is adjacent to all of , , and . Since is adjacent to both of and , we have . See Figure 4(b). If is an edge of , then is a hole; otherwise, is a hole, a contradiction. Case 2: is not adjacent to . By Lemma 3.6(2), a node of is adjacent to all of , , and . Since is adjacent to both of and , we have . See Figure 4(c). If is an edge of , then is a hole; otherwise, is a hole, a contradiction. ∎
4 Proving Lemma 2.4
Subset of is a starcutset [11] of graph if holds for some node of and the number of connected components of is larger than that of .
Lemma 4.1.
For any tracker of an node edge beetlefree connected graph , it takes time to complete one of the following three tasks. Task 1: Ensuring that contains even holes. Task 2: Ensuring that is not lucky. Task 3: Obtaining an induced subgraph of having no starcutsets such that if is lucky, then contains even holes.
Lemma 4.2.
It takes time to determine if an node edge graph having no starcutsets contains even holes.
Proof of Lemma 2.4.
We apply Lemma 4.1 on the input tracker of in time. If Task 1 or 2 is completed, then the lemma is proved. If Task 3 is completed, then since has no starcutsets, Lemma 4.2 implies that it takes time to determine whether contains even holes. Since is an induced subgraph of , if contains even holes, then so does ; otherwise, is not lucky. ∎
4.1 Proving Lemma 4.1
A starcutset of graph is full if holds for some node of . Full starcutsets in an node edge graph can be detected in time. Node dominates node in graph if and . Node is dominated in if some node of dominates in . We need the following three lemmas to prove Lemma 4.1.
Lemma 4.3 (Chvátal [11, Theorem 1]).
A graph having no dominated nodes and full starcutsets has no starcutsets.
Lemma 4.4.
If is a tracker of an node edge beetlefree connected graph , then it takes time to obtain a tracker of , where is an induced subgraph of having no dominated nodes, such that if is lucky, then so is .
Proof.
We first prove the following claim for any beetlefree graph : “If a node of dominates a node of a clean shortest even hole of , then is a clean shortest even hole of .” Let and be the neighbors of on . Since is a hole and , we know , implying . Since dominates and , there is a connected component of having at least nodes. By Lemma 2.2, we have , implying . Thus, is a shortest even hole of . Assume for contradiction. By , . By , exactly one of and is adjacent to in or else , contradicting the fact that is clean. Case 1: . If , then we have , contradicting the assumption that is a clean hole of . If , then , contradicting Lemma 2.2. Case 2: . By and Lemma 2.1, . By