Hole and antihole detection in graphs

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 + m²) 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(n⁴)-time algorithm for finding holes in arbitrary graphs. The key element of the algorithms is a special type of depth-first search traversal which proceeds along P4s (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 + m²) 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.

REFERENCES

• 1: C. Berge, Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss. Zeitschrift, Mathematisch-Naturwissenschaftliche Reihe, Martin-Luther-Univ. Halle-Wittenberg, 114--115, 1961.
• 2: Anne Berry , Jean-Paul Bordat , Pinar Heggernes, Recognizing weakly triangulated graphs by edge separability, Nordic Journal of Computing, v.7 n.3, p.164-177, Fall 2000
• 3: K. W. Chong, S. D. Nikolopoulos, and L. Palios, An optimal parallel co-connectivity algorithm, Theory of Computing Systems (to appear); Technical Report 27-02, Dept of Computer Science, Univ. of Ioannina, 2002.
• 4: M. Chudnovsky, N. Robertson, P. D. Seymour, and R. Thomas, The strong perfect graph theorem, preprint, 2002.
• 5: M. Chudnovsky and P. D. Seymour, Recognition algorithm for Berge graphs, preprint, 2003.
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: G. Cornuéjols, X. Liu, and K. Vušković, Perfect graph recognition, Proc. 44th IEEE Symp. on Foundations of Computer Science (FOCS 2003), 2003.
• 8: Elias Dahlhaus , Jens Gustedt , Ross M. McConnell, Efficient and practical algorithms for sequential modular decomposition, Journal of Algorithms, v.41 n.2, p.360-378, November 2001 [doi>10.1006/jagm.2001.1185]
• 9: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland, 2004
• 10: R. B. Hayward, Weakly triangulated graphs, J. Comb. Theory Ser. B39, 200--208, 1985.
• 11: R. B. Hayward, Two classes of perfect graphs, PhD Thesis, School of Computer Science, McGill Univ., 1987.
• 12: Ryan B. Hayward , Jeremy Spinrad , R. Sritharan, Weakly chordal graph algorithms via handles, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.42-49, January 09-11, 2000, San Francisco, California, United States
• 13: Hiro Ito , Mitsou Yokoyama, Linear time algorithms for graph search and connectivity determination on complement graphs, Information Processing Letters, v.66 n.4, p.209-213, May 29, 1998 [doi>10.1016/S0020-0190(98)00071-4]
• 14: Stavros D. Nikolopoulos , Leonidas Palios, On the Recognition of P4-Comparability Graphs, Revised Papers from the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, p.355-366, June 13-15, 2002
• 15: D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Computing5, 266--283, 1976.
• 16: Jeremy P. Spinrad, Finding large holes, Information Processing Letters, v.39 n.4, p.227-229, Aug. 30, 1991 [doi>10.1016/0020-0190(91)90184-J]
• 17: Jeremy Spinrad , R. Sritharan, Algorithms for weakly triangulated graphs, Discrete Applied Mathematics, v.59 n.2, p.181-191, May 12, 1995 [doi>10.1016/0166-218X(93)E0161-Q]
• 18: Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]

INDEX TERMS

Keywords:
antihole, co-connectivity, hole, weakly chordal graph