Hole and Antihole Detection in Graphs
Stavros D. Nikolop oulos
Abstract
In this paper, we study the problems of detecting holes and antiholes in general undirected graphs and present algorithms for them, which, for a graph on n vertices and m edges, run in O(n + m2 ) time and require O(nm) space; we thus provide a solution to the open problem posed by Hayward, Spinrad, and Sritharan in [12] asking for an O(n4 )time algorithm for finding holes in arbitrary graphs. The key element of the algorithms is a special type of depthfirst search traversal which proceeds along P4 s (i.e., chordless paths on four vertices) of the input graph. We also describe a different approach which allows us to detect antiholes in graphs that do not contain chordless cycles on 5 vertices in O(n + m2 ) time requiring O(n + m) space. Our algorithms are simple and can be easily used in practice. Additionally, we show how our detection algorithms can be augmented so that they return a hole or an antihole whenever such a structure is detected in the input graph; the augmentation takes O(n + m) time and space. Keywords: connectivity. hole, antihole, weakly chordal graph, co-

Leonidas Palios
graph-theoretic problem, both on its own and as a step in many recognition algorithms. Several algorithms for detecting holes and antiholes in graphs have been proposed in the literature. The definition of holes and antiholes implies that such algorithms can be applied without error on the biconnected components of the input graph and of its complement, respectively, instead of the entire graph. Although this approach may lead to the fast detection of holes and antiholes in graphs with small biconnected components, it does not yield any gain in the asymptotic sense. The problem of determining whether a graph contains a chordless cycle on k or more vertices, for some fixed value of k  4, is solved in O(nk ) time (Hayward [11]); Spinrad [16] provided an improved solution taking O(nk-3 M ) time, where M n2.376 is the time required to multiply two n × n matrices. Note that the problem of determining whether a graph contains a chordless cycle on four or more vertices can be solved in O(n + m) time [9, 15, 18] (it is the well-known chordal graph recognition problem). The algorithms of [11] and [16] can be used for the recognition of weakly chordal graphs in O(n5 ) and O(n4.376 ) time respectively. Further progress on the weakly chordal graph recognition problem includes the O(n4 )-time and O(nm)-space algorithm of Spinrad and Sritharan [17], and the O(m2 )-time and O(n + m)-space algorithm of Hayward, Spinrad, and Sritharan [12] and of Berry, Bordat, and Heggernes [2]. It is interesting to note that the algorithm of [12] produces a hole or an antihole certificate whenever the input graph is not weakly chordal. In the same paper, the authors posed as an open problem the designing of an O(n4 )-time algorithm to find a hole in an arbitrary graph. In this paper, we study the above mentioned open problem and we present two algorithms, one for the detection of holes and another for the detection of antiholes in arbitrary graphs. Both algorithms run in O(n + m2 ) time and require O(nm) space, and rely on the detection of a cycle satisfying certain conditions in the input graph or on its complement respectively. The existence of such a cycle is checked by means of a special depth-first search traversal, which we call P4 -DFS. We also describe another algorithm for the detection of antiholes in graphs that do not contain chordless cycles

1 Intro duction We consider finite undirected graphs with no loops or multiple edges. Let G be such a graph and let v0 , v1 , . . . , vk-1 be a sequence of k distinct vertices such that there is an edge from vi to v(i+1) mod k (for all i = 0, . . . , k - 1), and no other edge between any two of these vertices; we say that this is a chord less cycle on k vertices. A hole is a chordless cycle on five or more vertices; an antihole is the complement of a hole. Holes and antiholes have been extensively studied in many different contexts in algorithmic graph theory. Most notable examples are the weakly chordal graphs (also known as weakly triangulated graphs) [9, 10], which contain neither holes nor antiholes, and the strong perfect graph conjecture (Berge [1]), which states that a graph is perfect if and only if it contains no holes and no antiholes on an odd number of vertices (the recent proof of the conjecture by Chudnovsky et al. [4] has renewed the interest in the problem). Thus, finding a hole or an antihole in a graph efficiently is an important
 Research partially funded by the Europ ean Union and the Hellenic Ministry of Education through EPEAEK I I.  Department of Computer Science, University of Ioannina, GR-45110 Ioannina, Greece; stavros@cs.uoi.gr  Department of Computer Science, University of Ioannina, GR-45110 Ioannina, Greece; palios@cs.uoi.gr

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

850


on five vertices: the algorithm processes each edge of the input graph in order to determine whether the endpoints of the edge participate in an antihole, and relies on the computation of the co-connected components of subgraphs of the input graph; it runs in O(n + m2 ) time and takes O(n + m) space. The same approach yields an O(n2 m)-time and O(n2 )-space algorithm for detecting holes in graphs that do not contain chordless cycles on five vertices. Additionally, we describe how to augment our three detection algorithms so that they return a hole or an antihole in the case where such a structure exists in the input graph; the augmented hole (antihole, respectively) detection algorithm produces a hole (an antihole, respectively) in O(n + m) additional time and O(n + m) space. Finally, we note that, as a byproduct, our hole and antihole detection algorithms can be used for recognizing weakly chordal graphs leading to a solution that matches the best currently known time complexity for this problem.

edge e = xy , the neighborhood (closed neighborhood ) of e is the vertex set N ({x, y }) (resp. N [{x, y }]) and is denoted by N (e) (resp. N [e]). For an edge e = xy , we define the following three sets: A(e; x) = N (x) - N [y ],

A(e; y ) = N (y ) - N [x], A(e) = N (x)  N (y ); clearly, these sets form a partition of the neighborhood N (e) of the edge e. We close this section by describing the coconnectivity problem which plays a crucial role in the antihole detection algorithm for graphs that do not contain a C5 , which we propose in this paper. The coconnectivity problem on a graph G is that of finding the connected components of the complement G; the connected components of G are called co-connected components (or co-components ) of G. The co-components of a graph G on n vertices and m edges can be computed in O(n + m) time and space [8, 13, 3].

2

Preliminaries 3 Detecting Holes The hole detection algorithm relies on the result stated in the following lemma. Lemma 3.1. An undirected graph G contains a hole if and only if G contains a cycle u0 u1 . . . uk , where k  4, such that ui ui+1 ui+2 ui+3 for each i = 0, 1, . . . , k - 3, and uk-2 uk-1 uk u0 are P4 s of G. Proof. (=) Suppose that G contains a hole; then the vertices of the hole induce a cycle meeting the conditions of the lemma. (=) Suppose now that G contains a cycle as described in the lemma; let v0 v1 . . . vh be the shortest such cycle. Then, this cycle is a hole: a) since the cycle meets the conditions of the lemma, then h  4, which implies that the cycle is of length at least equal to 5; b) the cycle is chordless. Suppose for contradiction that there existed chords. With each chord vi vj , we associate its "length," which is defined as leng th(vi vj ) = |j - i|; let v vr , where < r, be the chord of minimum length. Note that r  + 4; this follows from the fact that r  4 (because v0 v1 v2 v3 is a P4 ) and the fact that vr-3 vr-2 vr-1 vr is a P4 . Then, vr-2 vr-1 vr v is a P4 in G because it is a path in G, vr-2 vr  E (G) (recall that / vr-3 vr-2 vr-1 vr is a P4 ), and v vr-2  E (G) and / v vr-1  E (G) for otherwise these would be chords /

Let G be a finite undirected graph with no loops or multiple edges. We denote by V (G) and E (G) the vertex set and edge set of G. The subgraph of a graph G induced by a subset S of vertices of G is denoted by G[S ]. A path in G is a sequence of vertices v0 v1 . . . vk such that vi vi+1  E (G) for i = 0, 1, . . . , k - 1; we say that this is a path from v0 to vk and that its length is k . A path is called simple if none of its vertices occurs more than once; it is called trivial if its length is equal to 0. A simple path v0 v1 . . . vk is chord less if vi vj  E (G) for any two non-consecutive vertices vi , / vj in the path. Throughout the paper, the chordless path on k vertices is denoted by Pk . In particular, a chordless path on 3 vertices is denoted by P3 and a chordless path on 4 vertices is denoted by P4 . A sequence of vertices v0 v1 . . . vk-1 forms a cycle (resp. simple cycle) iff v0 vk-1  E (G) and v0 v1 . . . vk-1 is a path (resp. simple path) in G; its length is equal to k . A simple cycle v0 v1 . . . vk-1 is said to be chord less if no edge vi vj exists in E (G) such that |i - j | = 1 mod k . The chordless cycle on k vertices is denoted by Ck ; in particular, C5 is the chordless cycle on 5 vertices. The neighborhood N (x) of a vertex x  V (G) is the set of all the vertices of G which are adjacent to x. The closed neighborhood of x is defined as N [x] := N (x)  {x}. The neighborx ood of a s-bset S of vertices h u is defined as N (S ) := N (x) S and its closed S neighborhood as N [S ] := N (S )  S . The notion of the neighborhood can be extended to edges: for an

851


whose leng th-value would be smaller than that of the chord v vr , in contradiction to the minimality of leng th(v vr ). Additionally, vi vi+1 vi+2 vi+3 is a P4 for all i = , + 1, . . . , r - 3. Thus, the cycle v v +1 . . . vr would meet the conditions of the lemma; as it would be shorter than the cycle v0 v1 . . . vh , this would contradict the fact that the latter cycle is the shortest such cycle. Hence, the cycle v0 v1 . . . vh is chordless. Therefore, G contains a hole.

to 1 if v belongs to the current P4 -DFS path, and is 0 otherwise. Below, we give a detailed description of the algorithm when applied on a connected input graph G; the case of a disconnected input graph is discussed after the analysis of the algorithm. The algorithm assumes that G is given in adjacency list representation, from which it computes the adjacency matrix of G so that adjacency tests can be answered in constant time. Hole-Detection Algorithm Input: a connected undirected graph G. Output: yes, if G contains a hole; otherwise, no.

Our algorithm for the detection of holes applies 1. Initialize the entries of the arrays not in hole[ ] Lemma 3.1. In particular, it uses a special type of and in path[ ] to 0; depth-first search traversal, which we will call P4 -DFS: compute the adjacency matrix A[ ] of G; the P4 -DFS traversal works similarly to the standard 2. For each vertex u of G do depth-first search [6], except that, in its general step, 2.1 in path[u]  1; it tries to extend a P3 abc into P4 s of the form abcd, 2.2 for each edge v w of G do then, for each such P4 , it proceeds extending the P3 bcd if u is adjacent to v and non-adjacent to w into P4 s of the form bcde, and so on. Unlike the and not in hole[(u, v ), w] = 0 standard depth-first search, the P4 -DFS traversal may then in path[v ]  1; proceed to a vertex that has been encountered before; process(u, v , w); however, it does not need to proceed to a P3 that has in path[v ]  0; been encountered before. If the P4 -DFS has at a given 2.3 in path[u]  0; moment proceeded to traverse a sequence of P3 s abc, 3. Print that G does not contain a hole. bcd, . . ., wxy , xy z , then we call the sequence of vertices a, b, . . . , y , z the current P4 -DFS path. Then, it is not where the procedure process( ) is as follows: difficult to see that the following holds: process(a, b, c) 1. in path[c]  1; 2. for each vertex d adjacent to c in G do 2.1 if d is adjacent to neither a nor b in G then {abcd is a P4 of G} 2.2 if in path[d] = 1 Note that the cycle mentioned in Lemma 3.2 contains then print that G has a hole; Stop. at least one P4 and thus is of length at least equal to 5. else if not in hole[(b, c), d] = 0 In order to exhaustively search the input graph G, then process(b, c, d); the P4 -DFS traversal starts from each P3 of G. On the 3. in path[c]  0; other hand, in order to prevent processing a P3 which 4. not in hole[(a, b), c]  1; has been encountered before, it uses an auxiliary array not in hole[(c, b), a]  1; not in hole[(u, v ), w], where u, v , w  V (G) and u, v are adjacent in G; for each pair of adjacent vertices u, v , It is important to observe that the description of the the array has entries not in hole[(u, v ), w] as well as procedure process( ) guarantees that from a P3 abc not in hole[(v , u), w] for every w  V (G), and hence we proceed to a P3 bcd only if abcd is a P4 of the its size is 2m · n. The entry not in hole[(u, v ), w] input graph G. Before returning, the procedure sets is equal to 1 iff the vertices u, v , w induce a P3 uv w the corresponding entries of the array not in hole[ ], of G which has been processed and found not to thus preventing a second call to the procedure on participate in a hole, otherwise it is equal to 0 the same P3 . Additionally, a call process(a, b, c) (note that two entries of the array correspond to does not cause, for any depth of recursion, another each P3 uv w, namely, not in hole[(u, v ), w] and call process(a, b, c) or process(c, b, a), because, for not in hole[(w, v ), u]). Additionally, in order to be this to happen, the vertex a (respectively, c) would able to test whether a vertex belongs to the current P4 - be encountered again; then, the condition of the if DFS path, the algorithm uses another auxiliary array statement in Step 2.2 of process( ) would be found true in path[ ] of size n; for a vertex v , in path[v ] is equal and the algorithm would instantly terminate. Thus, the Lemma 3.2. Suppose that the P4 -DFS traversal is applied on the input graph G. Then, if the current P4 -DFS path  is extended to a vertex which belongs to , then G contains a cycle meeting the conditions of Lemma 3.1.

852


procedure process( ) is called exactly once for each P3 of G. The correctness of the algorithm follows from Lemmas 3.1 and 3.2 and the following result. Lemma 3.3. If for a P3 abc of the input graph G, the entry not in hole[(a, b), c] is set to 1, then the P3 abc does not participate in a hole of G. Proof. For the entry not in hole[(a, b), c] to be set to 1, a call process(a, b, c) or process(c, b, a) needs to have been made; suppose without loss of generality that this is process(a, b, c). The proof applies induction on the number of calls to the procedure process( ) that have returned before the assignment "not in hole[(a, b), c]  1" in Step 4 of the call process(a, b, c). For the basis step, let us suppose that no calls to process( ) have returned. Then, no entry of the array not in hole[ ] has been set to 1. Hence, no P4 of the form abcd exists in G; if it existed, either the algorithm would have terminated (if d belonged to the P4 -DFS path) or a call process(b, c, d) would have been made, which should have returned for the control to proceed to Step 4. Therefore, since no P4 abcd exists in G, the P3 abc does not participate in a hole of G. For the inductive hypothesis, we assume that the statement of the lemma is true for P3 s for which the corresponding entries of the array not in hole[ ] have been set equal to 1 after fewer than i0 > 0 calls to the procedure process( ) have returned. For the inductive step, we assume that the entry not in hole[(a, b), c] corresponding to the P3 abc has been set equal to 1 after i0 calls to the procedure process( ) have returned, and we show that the lemma holds for the P3 abc. Suppose, for contradiction, that this is not the case; then, abc participates in a hole of G, which implies that there exists a vertex x such that abcx is a P4 of the hole. Clearly, this vertex x has been considered in Step 2.2 of the execution of process(a, b, c). It must be the case that in path[x] is not equal to 1, for otherwise the algorithm would have terminated. Thus, if not in hole[(b, c), x] is equal to 0, a call process(b, c, x) is made; if not in hole[(b, c), x] is not equal to 0, then it must have been set to 1 by a preceding call process(b, c, x) or process(x, c, b). In either case, this call to process( ) was completed before the execution of Step 4 of process(a, b, c). Thus, the assignment "not in hole[(b, c), x]  1" has been made after fewer than i0 calls to process( ) have terminated; by the inductive hypothesis, we conclude that the P3 bcx does not participate in any hole of G. This comes into contradiction with the fact that the P4 abcx is a P4 of a hole of G. Therefore, the P3 abc

does not participate in a hole of G. Our inductive proof is complete; the lemma follows. Time and Space Complexity. Let n and m be the number of vertices and edges of the input graph G respectively. Since G is connected, then n = O(m). Before analyzing the time complexity of each step of the algorithm, we turn to the procedure process( ). We note that the procedure is called exactly once for each P3 of G, i.e., O(nm) times, and that, if we ignore the time taken by the recursive calls, a call process(a, b, c) takes O(|N (c)| + 1) time by using the adjacency list of the vertex c to retrieve c's neighbors, and by using the adjacency matrix A[ ] to answer adjacency tests in constant time. Therefore, the time taken by all the calls to the procedure process( ) is O(m2 ), since each quadruple of vertices a, b, c, d where abc is a P3 and d is adjacent to c is uniquely characterized by the ordered pair ((a, b), (c, d)) where (a, b) and (c, d) are ordered pairs of adjacent vertices in G. Step 1 of the main body of the algorithm clearly takes O(nm) time. If the time taken by the calls to the procedure process( ) is ignored, Step 2 takes O(nm) time; again, the adjacencies are checked in constant time by means of the adjacency matrix A[ ] of G. Step 3 takes constant time. Thus, the time complexity of the algorithm for a connected graph on n vertices and m edges is O(m2 ). The space needed is O(nm): O(n) and O(nm) for the arrays in path[ ] and not in hole[ ] respectively, and O(n2 ) for the matrix A[ ] and the adjacency list representation of the input graph. Summarizing, we have the following result. Lemma 3.4. Let G be a connected undirected graph on n vertices and m edges. Then, it can be determined whether G contains a hole in O(m2 ) time and O(nm) space. The case of a disconnected input graph. If the input graph G is disconnected, we work on each of its connected components; let ni and mi denote the number of vertices and edges of the i-th connected component respectively. The computation of the connected components takes O(n + m) time [6], whiile processing mi = m, we each of them takes O(m2 ) time. Since i have that O(n + m2 ) time suffices for detecting holes in any graph on n vertices and m edges. In this case, the i = space needed is O (ni mi ) O(nm). Therefore, we obtain the following theorem. Theorem 3.1. Let G be an undirected graph on n vertices and m edges. Then, it can be determined whether G contains a hole in O(n+m2 ) time and O(nm) space.

853


3.1 Providing a Certificate The hole detection algorithm can be easily augmented so that it provides a certificate whenever it decides that the input graph G contains a hole. In particular, we need the following: (i) The updating of the entries of the array in path[ ] is done so that they reflect the position of the corresponding vertex in the current P4 -DFS path. More specifically, in path[v ] is set equal to i, if v is the i-th vertex in the P4 -DFS path; this may necessitate replacing the call process(a, b, c) by process(a, b, c, i), if c is the i-th vertex in the path. (ii) The vertices in the current P4 -DFS path are stored in an array pathvertex[ ] in the order they appear along the path. (iii) If the algorithm concludes that G contains a hole, then the condition in Step 2.2 of the procedure process( ) during the execution of a call, say, process(a, b, c, k ), is found true for some vertex d; suppose that d is located in the j -th position of the current P4 -DFS path. Then, the vertices located in positions j , j + 1, . . . , k of the path form a cycle satisfying the conditions in the statement of Lemma 3.1. To isolate a hole, we call the following procedure get hole(j, k ) before terminating in Step 2.2 of process(a, b, c, k ). The procedure computes the range [imin , imax ] of indices of the entries in the array pathvertex[ ] which store the vertices inducing a hole in G. get hole(j, k ) imin  j ; imax  k ; i  imin ; repeat u  pathvertex[i]; h  imax + 1; for each vertex x adjacent to u in G do if in path[x]  i + 4 and in path[x] < h then h  in path[x]; if h  imax then imin  i; imax  h; i  i + 1; until i > imax - 4; print the vertices in the entries imin , imin + 1, . . . , imax of the array pathvertex[ ]; The vertices printed induce a hole in G.

of pathvertex[i] in G, whenever such an entry exists, and is equal to imax + 1 otherwise. The correctness of the computation follows from Lemma 3.5. Lemma 3.5. The vertices printed by procedure get hole( ) induce a hole in the input graph G. Proof. Let imin (t) and imax (t) denote the values of imin and imax at the beginning of the iteration of the repeatuntil loop for i = t, and let ^min and ^max be their final i i values. Clearly, the vertices printed by get hole( ) induce a cycle. Moreover, its length is at least equal to 5, since imax (i)  imin (i) + 4 for every i; note that k  j + 4 and that h  i + 4. Finally, we show that the cycle is chordless. Suppose for contradiction that there existed a chord and suppose that it were incident on the vertices pathvertex[ ] and pathvertex[r], where ^min  < r  ^max and = ^min or r = ^max or both; i i i i then, r - < ^max - ^min . The definition of the P4 -DFS i i traversal implies that every four consecutive vertices in the array pathvertex[ ] form a P4 , and thus r -  4. Hence,  r - 4  ^max - 4, which, along with the i fact that the value of imax never increases, implies that the repeat-until loop of the procedure get hole( ) has been executed for i = . At the end of the execution of the for loop when i = , the variable h would not exceed r, because the vertex pathvertex[r] is adjacent to pathvertex[ ] in G, and +4  r  ^max  imax ( ); i then, the condition "h  imax " would have been found true, and the variables imin and imax would have been set to and to an integer not exceeding r respectively. This, however, comes into contradiction with the fact that r - < ^max - ^min , since the value of imin never i i decreases and the value of imax never increases. The certificate computation takes O(n + m) time: note that the vertices in the array pathvertex[ ] are distinct, and that their neighbors can be accessed in constant time per neighbor using the adjacency list representation of the input graph. The space required is linear in the size of the input graph. Therefore, we have: Theorem 3.2. Let G be an undirected graph on n vertices and m edges. The hole detection algorithm presented in this section can be augmented so that it provides a certificate that G contains a hole, whenever it decides so of G. The certificate computation takes O(n + m) time and O(n + m) space.

Note that, in each iteration of the repeat-until loop, at the end of the execution of the for loop, the variable h 4 Detecting Antiholes is equal to the minimum index of any entry in the Since an antihole is the complement of a hole, one subarray pathvertex[i + 4...imax ] storing a neighbor can use the algorithm of the previous section on the

854


complement of a graph in order to determine whether it contains an antihole. Such an approach may however require (n4 ) time, where n is the number of vertices of the graph, since the complement may have as many as (n2 ) edges. Below, we present an algorithm for the detection of antiholes which applies the P4 -DFS traversal on the complement of the input graph G without however computing the complement explicitly and which takes O(n + m2 ) time when G has n vertices and m edges. The algorithm uses an array not in antihole[(a, b), c], where a, b, c  V (G) and ab  E (G), and thus is of size 2m · n; not in antihole[(a, b), c] is equal to 1 iff acb is a P3 of G which has been found not to participate in an antihole of G, and is 0 otherwise. The input graph G is assumed to be connected; if G is disconnected, then we apply the algorithm on each of G's connected components. Antihole-Detection Algorithm Input: a connected undirected graph G. Output: yes, if G contains an antihole; otherwise, no. 1. Initialize the entries of arrays not in antihole[ ] and in path[ ] to 0; compute the adjacency matrix of G; 2. For each vertex u of G do 2.1 in path[u]  1; 2.2 for each edge v w of G do if u is adjacent to neither v nor w and not in antihole[(v , w), u] = 0 then in path[v ]  1; process(v , u, w); in path[v ]  0; 2.3 in path[u]  0; 3. Print that G does not contain an antihole. where the procedure process( ) is as follows: process(a, b, c) 1. in path[c]  1; 2. for each vertex d adjacent to b in G do 2.1 if d is adjacent to a and non-adjacent to c then {abcd is a P4 of G} 2.2 if in path[d] = 1 then print that G has an antihole; Stop. else if not in antihole[(b, d), c] = 0 then process(b, c, d); 3. in path[c]  0; 4. not in antihole[(a, c), b]  1; not in antihole[(c, a), b]  1;

The correctness of the algorithm is established as in the case of the hole detection algorithm of the previous section. Time and Space Complexity. Similarly to the case of the hole detection algorithm, we obtain the result stated in Theorem 4.1; observe that if we ignore the time taken by the recursive calls, the execution of the call process(a, b, c) takes O(|N (b)| + 1) time, and that each quadruple of vertices a, b, c, d where abc is a P3 of G and d is adjacent to b in G is uniquely characterized by the ordered pair ((a, c), (b, d)), where (a, c) and (b, d) are ordered pairs of adjacent vertices in G. Theorem 4.1. Let G be an undirected graph on n vertices and m edges. Then, it can be determined whether G contains an antihole in O(n + m2 ) time and O(nm) space. 4.1 Providing a Certificate Similarly to the hole detection algorithm, the above algorithm can be easily augmented so that it provides a certificate whenever it decides that the input graph G contains an antihole. In particular, (i) we use arrays in path[ ] and pathvertex[ ] as described in Section 3.1; (ii) if the algorithm concludes that G contains an antihole, then the condition in Step 2.2 of the procedure process( ) during the execution of a call, say, process(a, b, c, k ), is found true for some vertex d; suppose that d is located in the j -th position of the current P4 -DFS path. Then, the vertices located in positions j , j + 1, . . . , k of the path form a cycle in G satisfying the conditions in the statement of Lemma 3.1. To isolate an antihole, we call the following procedure get antihole(j, k ) before terminating in Step 2.2 of process(a, b, c, k ); the procedure computes the range [imin , imax ] of indices of the entries in the array pathvertex[ ] which store the vertices inducing an antihole in G. get antihole(j, k ) imin  j ; imax  k ; i  imin ; repeat u  pathvertex[i]; h  i + 4; while h  imax and pathvertex[h] is adjacent to u do h  h + 1; if h  imax {a non-neighbor was found} then imin  i; imax  h;

Note that for a call process(a, b, c), a and c are adjacent in G, while b is adjacent to neither a nor c. So, if there exists a vertex d such that d is adjacent to a and b and not adjacent to c, then the vertices a, b, c, d induce the P4 abcd in G.

855


G; let e be the edge of G connecting them. Then, v0  V (G) - N [e], v2  A(e; vk ), vk-1  A(e; v1 ), and {v2 , . . . , vk-1 }  N (e)  N (v0 ); these and the fact that the sequence vk-1 , . . . , v2 induces a path in G imply that the conditions of the lemma hold for the edge v1 vk of G The vertices printed induce an antihole in G. and the vertex v0 . It is not difficult to see that, for each value of i, when the (=) Suppose now that there exists an edge e = xy condition of the while loop is found false, the variable h of G and a vertex u  V (G) - N [e] such that in the is equal to the minimum index of any entry in the sub- complement of the subgraph G[N (e)  N (u)] there exists array pathvertex[i + 4...imax ] storing a non-neighbor a path from a vertex in A(e; x) to a vertex in A(e; y ). of pathvertex[i] in G, whenever such an entry exists, Let p0 p1 . . . pk be a shortest such path; that is, p0  and is equal to imax + 1 otherwise. The correctness of A(e; x)  N (u), pk  A(e; y )  N (u), pi  A(e)  N (u) for the procedure get antihole( ) follows from an argu- all i = 1, . . . , k - 1, and pi pj  E (G) for 0  i < j - 1  ment similar to that used to prove Lemma 3.5; as in the k - 1. Then, the subgraph G[{x, u, y , p0 , p1 , . . . , pk }] of case of holes, the value of imin never decreases, whereas G is the complement of a chordless cycle of length at least 5; in other words, G contains an antihole. the value of imax never increases. The procedure requires O(n + m) time: the initialLemma 5.1 readily implies an antihole detection ization assignments take O(1) time; during the execualgorithm which for a graph G on n vertices and m tion of the repeat-until loop for the vertex u stored 2 in pathvertex[i], the condition of the while loop is edges runs in (nm ) time in the worst case: for the checked at most |N (u)| times (it is found false at appropriate pairs of an edge e = xy and a vertex u, we the first-encountered non-neighbor of u) and thus the compute the co-components of the subgraph G[N (e)  while loop takes O(N (u)) time (thanks to the adja- N (u)] and check whether any of them contains vertices cency matrix of G), while O(1) time suffices for the from both A(e; x) and A(e; y ); as there may be as many remaining assignments. Since the vertices in the array as (nm) such pairs, and for each one of them (n + m) e pathvertex[ ] are distinct, it follows that the proce- time may be needed and suffices for the above mention2 d computations, the overall time complexity is (nm ). dure get antihole( ) takes O(n + m) time. The space required is linear in the size of the input graph. There- An improved algorithm can be obtained for graphs not containing C5 s, for which the following fact holds. fore, the following theorem holds: Theorem 4.2. Let G be an undirected graph on n vertices and m edges. The antihole detection algorithm presented in this section can be augmented so that it provides a certificate that G contains an antihole, whenever it decides so of G. The certificate computation takes O(n + m) time and O(n + m) space. Fact 5.1. Let G be an undirected graph which does not contain a C5 , and let e = xy be an edge of G. Then, for every pair of vertices a and b such that a  A(e; x), b  A(e; y ), and (N (a)  N (b)) - N [e] = , it holds that a and b are adjacent in G. Proof. Let w be any vertex in (N (a)  N (b)) - N [e]; clearly, wa, wb  E (G), and wx, wy  E (G). If the vertices a and b were not adjacent in G, then the subgraph of G induced by a, x, y , b, and w would be a C5 , a contradiction. In light of Fact 5.1, for any edge e = xy and any vertex u  V (G) - N [e] of a graph G that does not contain a C5 , any path from a vertex in A(e; x) to a vertex in A(e; y ) in the complement of the subgraph of G induced by N (e)  N (u) is of length at least 2 and contains a vertex in A(e). Then, instead of computing such a path we need only determine if there exist vertices a  A(e; x)  N (u), b  A(e; y )  N (u), and v  A(e)  N (u) such that v , a belong to the same co-component of the subgraph G[N (x)  N (u)], and v , b belong to the same co-component of the subgraph G[N (y )  N (u)]; see Figure 1: C and D denote the

i  i + 1; until i > imax - 4; print the vertices in the entries imin , imin + 1, . . . , imax of the array pathvertex[ ];

5

Detecting Antiholes in Graphs that do not Contain a C5

Antiholes in general graphs can be detected by taking advantage of the following property: Lemma 5.1. Let G be an undirected graph. Then, G contains an antihole if and only if there exists an edge e = xy of G and a vertex u  V (G) - N [e] such that in the complement of the subgraph of G induced by N (e)  N (u) there exists a path from a vertex in A(e; x) to a vertex in A(e; y ). Proof. (=) Suppose that G contains an antihole and let this be the complement of the hole v0 v1 . . . vk , where k  4. Then, the vertices v1 and vk are adjacent in

856


Sfrag replacements

u

V (G) - N [e]

Output: yes, if G contains an antihole; otherwise, no. 1. For each vertex u of G do

A(e; x)  N (u) a

A(e)  N (u) v C x e Figure 1 D y b

A(e; y )  N (u)

1.1 for each vertex w not adjacent to u in G do 1.1.1 compute the set Nu,w = N (u)  N (w); 1.1.2 compute the co-components of G[Nu,w ]; 1.1.3 store the set Nu,w as a list of vertex records, ordered by vertex index, where each vertex z  Nu,w is associated with the representative cc(Nu,w ; z ) of the co-component to which it belongs; 1.2 for each edge e = xy of G s.t. x, y  N [u] do / {x, y  N [u] is equivalent to u  V (G) - N [e]} / 1.2.1 {mark the co-components of G[Nu,x ]} {containing a vertex in A(e; x)} for each vertex w  Nu,x do mark1[w]  0; for each vertex w  Nu,x - Nu,y do {mark the representative} mark1[cc(Nu,x; w)]  1; 1.2.2 {mark the co-components of G[Nu,y ]} {containing a vertex in A(e; y )} for each vertex w  Nu,y do mark2[w]  0; for each vertex w  Nu,y - Nu,x do {mark the representative} mark2[cc(Nu,y; w)]  1; 1.2.3 for each vertex v  Nu,x  Nu,y do if mark1[cc(Nu,x; v )] = 1 and mark2[cc(Nu,y; v )] = 1 then print that G contains an antihole; Stop; 2. Print that G does not contain an antihole. The correctness of the algorithm follows from Lemma 5.2: for a vertex u of G and an edge e = xy such that x, y  N [u], then A(e; x)  N (u) = Nu,x - Nu,y , A(e; y )  N (u) = Nu,y - Nu,x , and A(e)  N (u) = Nu,x  Nu,y ; moreover, the condition "if mark1[cc(Nu,x; v )] = 1 and mark2[cc(Nu,y; v )] = 1" and the fact that the vertex v belongs to Nu,x  Nu,y imply that in the complement of G[Nu,x ] there exists a path from v to a vertex in A(e; x) and that in the complement of G[Nu,y ] there exists a path from v to a vertex in A(e; y ). Time and Space Complexity. Let n and m be the number of vertices and edges of the input graph G; since G is connected, n = O(m). Step 1.1.1 can be completed in O(n) time, while the construction of G[Nu,w ] and the computation of its co-components can be done in O(|Nu,w |2 ) time [8, 13, 3]. Since |Nu,w |  min{|N (u)|, |N (w)|}, we have that |Nu,w |2 

co-components of the subgraphs G[N (x)  N (u)] and G[N (y )  N (u)] containing v and a, and v and b respectively, and the dotted paths indicate chordless paths in the complements of these subgraphs. We show next that the existence of such vertices v , a, and b is equivalent to the existence of an antihole in G. Lemma 5.2. Let G be an undirected graph which does not contain a C5 . Then, G contains an antihole if and only if there exists an edge e = xy of G and vertices u  V (G) - N [e], a  A(e; x)  N (u), b  A(e; y )  N (u), and v  A(e)  N (u) such that a, v belong to the same co-component of the subgraph G[N (x)  N (u)], and b, v belong to the same co-component of the subgraph G[N (y )  N (u)]. Proof. (=) Suppose that G contains an antihole. Since G does not contain a C5 , the antihole is of length at least 6; let it be the complement of the hole v0 v1 . . . vk (k  5). The vertices v1 and vk are adjacent in G; if e is the edge of G connecting them, then, v0  V (G) - N [e], v2  A(e; vk )  N (v0 ), vk-1  A(e; v1 )  N (v0 ), and {v3 , . . . , vk-2 }  A(e)  N (v0 ). Since k  5, it is easy to see that the conditions of the lemma hold for v1 , vk , v0 , vk-1 , v2 , v3 in place of x, y , u, a, b, v respectively. (=) Suppose now that there exists an edge e = xy of G and vertices u, a, b, v as described in the statement of the lemma. Then, in the complement of the subgraph of G induced by N (e)  N (u) there exists a path from vertex a  A(e; x) to vertex b  A(e; y ). Then, by Lemma 5.1, G contains an antihole. We give below a detailed description of the antihole detection algorithm for a connected input graph G; for disconnected input graphs, we apply the algorithm on each of their connected components. Antihole-Detection Algorithm for Graphs that do not contain a C5 Input: a connected undirected graph G that does not contain a C5 .

857


|N (u)| · |N (w)|; whus,| for a vertex u o=G, Step 1.1.2 t f takes O(n) + O N (u)| · |N (w)| O(m |N (u)|) time1 . The construction of the list storing Nu,w in Step 1.1.3 can be done in O(|N (u)|) time by traversing the adjacency list of u, by collecting those vertices that belong to Nu,w , and by updating the co-component representative information; the ordering by vertex index comes for free, had we sorted the adjacency lists of the vertices in G by vertex index, something which can be achieved in O(n + m) time using radix sorting during a preprocessing phase. The sorting of the lists representing the sets Nu,w implies that determining which vertices belong to Nu,x - Nu,y , Nu,y - Nu,x , and Nu,x  Nu,y can be achieved by simply traversing the lists for Nu,x and Nu,y in lockstep fashion. Then, each execution of Step 1.2 takes O(|N (u)|) time, since Nu,x , Nu,y  N (u). Thus, e for a vertex u of G, Step 1.2 takes O(|N (u)|) = O(m |N (u)|) time. Step 2 takes constant time. In total,uthe entire execution of the algorithm on G takes = O(n + m + m |N (u)|) O(m2 ) time. O Let us now turn to the space complexity of the algorithm. The adjacency list representation of the input graph requires O(n + m) space. For an iteration of the for loop in Step 1, we need: O(n) space to store Nu,w and the re-indexing arrays, and O(n + m) space to store G[Nu,w ], both weusable in each iteration of the for r O(1 + |Nu,w |) = O(n + m) space loop in Step 1.1; to store the list representations of the sets Nu,w for all w  V (G) - N [u]; O(n) space for the arrays mark1[ ] and mark2[ ], reusable in each iteration of the for loop in Step 1.2. This space can be reused from iteration to iteration of the for loop in Step 1, so that the space complexity of the algorithm is O(n + m). In summary, our antihole detection algorithm runs in O(m2 ) time using O(n + m) space when applied on a connected undirected graph on n vertices and m edges. If the input graph is disconnected, then we apply the algorithm on each of its connected components. Since the connected components of a graph can be computed in time and space linear in the size of the graph [6] and since these components are pairwise vertex- and edgedisjoint, we obtain the following result. Theorem 5.1. Let G be an undirected graph on n vertices and m edges which does not contain a C5 . Then, it can be determined whether G contains an antihole in O(n + m2 ) time and O(n + m) space.
Note that working on the subgraph G[Nu,w ] requires reindexing of vertices, i.e., mapping the indices 1, . . . , n of vertices in G to the indices 1, . . . , |Nu,w | of vertices in G[Nu,w ] and vice versa; this can b e done by using two arrays of O (n) total space which take O (n) time to initialize and constant time to answer each re-indexing request.
1

5.1 Providing a Certificate Like the previous algorithms, this algorithm too can be augmented so that it provides a certificate whenever it decides that the input graph G contains an antihole. In particular, if G contains an antihole, then whenever the algorithm finds that, for a vertex u and an edge e = xy / of G such that x, y  N [u], there exists a vertex v  Nu,x  Nu,y for which mark1[cc(Nu,x; v )] = 1 and mark2[cc(Nu,y; v )] = 1, it executes the following in Step 1.2.3 before terminating: (i) computes the subgraph G[N (e)  N (u)]; (ii) uses a dummy vertex s and makes it adjacent to all the vertices of the subgraph except for those in Nu,x - Nu,y ; (iii) runs BFS on the complement of the resulting graph starting at s until a vertex, say, b, in Nu,y - Nu,x is encountered; It is not difficult to see that if the path on tree edges from s to b in the BFS-tree of Step (iii) is sv1 v2 . . . vk b, then the vertices x, u, y , v1 , . . . , vk , b induce an antihole in G of length at least 6 (since G does not contain a C5 , then k  2 in accordance with Fact 5.1). The computation of the adjacency list representation of the subgraph G[N (e)  N (u)] can be done in O(n + m) time and space by using a copy of the adjacency list representation of G and by removing from it all unnecessary lists and vertex records. The addition of the dummy vertex s can be done in O(n) time and space. Executing BFS on the complement of the resulting graph can be done in time and space linear in the size of the graph, i.e., in O(n + m) time and space (see [8, 13, 14]). Finally, the path on tree edges needed to complete the antihole can be easily obtained in time linear in its length if the BFS-tree is represented by means of parent pointers. Therefore, we have: Theorem 5.2. Let G be an undirected graph on n vertices and m edges which does not contain a C5 . The antihole detection algorithm presented in this section can be augmented so that it provides a certificate that G contains an antihole, whenever it decides so of G. The certificate computation takes O(n + m) time and space. Remark. Since an antihole is the complement of a hole and the complement of a C5 is also a C5 , one can detect whether a graph G, which does not contain a C5 , contains a hole by applying the above algorithm on its complement G; this results into an O(n4 )-time and O(n2 )-space algorithm. If however the operation of the algorithm on G is interpreted in terms of G so that

858


G is not constructed explicitly, then it can be shown References that the algorithm runs in O(n2 m) time and requires O(n2 ) space. This result indicates that the same [1] C. Berge, Farbung von Graphen deren samtliche bzw. ¨ ¨ deren ungerade Kreise starr sind, Wiss. Zeitschrift, approach results in a hole detection algorithm which Mathematisch-Naturwissenschaftliche Reihe, Martinin the worst case proves asymptotically more timeLuther-Univ. Halle-Wittenberg, 114­115, 1961. and space-consuming than the corresponding antihole [2] A. Berry, J.-P. Bordat, and P. Heggernes, Recognizing detection algorithm. This seems to be due to the fact weakly triangulated graphs by edge separability, Nordic that checking whether a graph contains an antihole of J. Computing 7, 164­177, 2000. 2 length k requires that certain (k ) edges exist and that [3] K.W. Chong, S.D. Nikolopoulos, and L. Palios, An certain k edges are missing, whereas in the case of a hole optimal parallel co-connectivity algorithm, Theory of of length k , one needs to verify that k edges exist and Computing Systems (to appear); Technical Report 27(k 2 ) edges are missing; in the former case, the cost of 02, Dept of Computer Science, Univ. of Ioannina, 2002. checking the non-existence of the k edges can be paid [4] M. Chudnovsky, N. Robertson, P.D. Seymour, and for by the (k 2 ) existing edges, something which does R. Thomas, The strong perfect graph theorem, preprint, 2002. not hold in the latter case.
[5] M. Chudnovsky and P.D. Seymour, Recognition algorithm for Berge graphs, preprint, 2003. [6] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms (2nd edition), MIT Press, Inc., 2001. [7] G. Cornu´jols, X. Liu, and K. Vukovi´, Perfect graph e s c recognition, Proc. 44th IEEE Symp. on Foundations of Computer Science (FOCS 2003), 2003. [8] E. Dahlhaus, J. Gustedt, and R.M. McConnell, Efficient and practical algorithms for sequential modular decomposition, J. Algorithms 41, 360­387, 2001. [9] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. [10] R.B. Hayward, Weakly triangulated graphs, J. Comb. Theory Ser. B 39, 200­208, 1985. [11] R.B. Hayward, Two classes of perfect graphs, PhD Thesis, School of Computer Science, McGill Univ., 1987. [12] R.B. Hayward, J. Spinrad, and R. Sritharan, Weakly chordal graph algorithms via handles, Proc. 11th ACMSIAM Symp. on Discrete Algorithms (SODA 2000), 42­49, 2000. [13] H. Ito and M. Yokoyama, Linear time algorithms for graph search and connectivity determination on complement graphs, Inform. Process. Letters 66, 209­ 213, 1998. [14] S.D. Nikolopoulos and L. Palios, Recognizing P4 -comparability graphs, Proc. 28th Int. Workshop on Graph Theoretic Aspects of Computer Science (WG 2002), 355­366, 2002. [15] D.J. Rose, R.E. Tarjan, and G.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Computing 5, 266­283, 1976. [16] J.P. Spinrad, Finding large holes, Inform. Process. Letters 39, 227­229, 1991. [17] J.P. Spinrad and R. Sritharan, Algorithms for weakly triangulated graphs, Discrete Applied Math. 59, 181­ 191, 1995. [18] 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 J. Computing 13, 566­579, 1984.

6

Concluding Remarks

We have presented algorithms for detecting holes and antiholes in general undirected graphs. For an input graph on n vertices and m edges, both algorithms run in O(n + m2 ) time and require O(nm) space. The algorithms can be augmented so that they return a hole or an antihole (whenever such a structure exists in the graph) in O(n + m) additional time and space. We have also described an antihole detection algorithm for graphs not containing a C5 which runs in O(n + m2 ) time and requires only O(n + m) space. The obvious open problem is to design algorithms for finding a hole and/or an antihole in general graphs with improved time and/or space complexity; note that all the P3 s participating in P4 s of a graph on n vertices and m edges can be computed in O(nm) time [14]. It is worth mentioning that o(n + m2 )-time algorithms for both problems would imply an improvement on the currently best algorithms for recognizing weakly chordal graphs [12, 2]. We also pose as an open problem the construction of O(n + m2 )-time algorithms for detecting whether a graph contains a C5 . None of our algorithms seems to be modifiable to handle this special case while maintaining the O(n + m2 ) time complexity. We note that, due to our antihole detection algorithm for graphs that do not contain a C5 , an O(n + m2 )-time and O(n + m)-space algorithm for detecting a C5 would imply an antihole detection algorithm for general graphs of the same time and space complexity. Finally, in light of the "strong perfect graph theorem" [4], it would be very interesting to come up with efficient algorithms for the detection of odd-length holes and/or odd-length antiholes in general graphs. For a graph on n vertices, the currently fastest algorithms for these problems run in O(n9 ) time [5, 7].

859