Certifying algorithms for recognizing interval graphs and permutation graphs

ABSTRACT

A certifying algorithm for a decision problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs. Previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. We show that our certificates of non-membership can be authenticated in O(|V|) time.

REFERENCES

• 1: K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, JCSS, 13 (1976), pp. 335--379.
• 2: Andreas Brandstädt , Van Bang Le , Jeremy P. Spinrad, Graph classes: a survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 3: Derek G. Corneil , Stephan Olariu , Lorna Stewart, The ultimate interval graph recognition algorithm?, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.175-180, January 25-27, 1998, San Francisco, California, United States
• 4: G. A Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25 (1961) pp. 71--76.
• 5: T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., 18 (1967), pp. 25--66.
• 6: M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.
• 7: Michel Habib , Ross McConnell , Christophe Paul , Laurent Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, v.234 n.1-2, p.59-84, March 6, 2000 [doi>10.1016/S0304-3975(97)00241-7]
• 8: Wen-Lian Hsu, A Simple Test for Interval Graphs, Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, p.11-16, June 19-20, 1992
• 9: Wen-Lian Hsu , Ross M. McConnell, PC trees and circular-ones arrangements, Theoretical Computer Science, v.296 n.1, p.99-116, 4 March 2003 [doi>10.1016/S0304-3975(02)00435-8]
• 10: Norbert Korte , Rolf H. Möhring, An incremental linear-time algorithm for recognizing interval graphs, SIAM Journal on Computing, v.18 n.1, p.68-81, Feb. 1989 [doi>10.1137/0218005]
• 11: C. Lekkerkerker and D. Boland, Representation of finite graphs by a set of intervals on the real line, Fund. Math. 51 (1962), 45--64.
• 12: Ross M. McConnell , Jeremy P. Spinrad, Modular decomposition and transitive orientation, Discrete Mathematics, v.201 n.1-3, p.189-241, April 28, 1999 [doi>10.1016/S0012-365X(98)00319-7]
• 13: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 14: A. Pnueli, A. Lempel, and S. Even, Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math., 23 (1971), pp. 160--175.
• 15: D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5 (1976), pp. 266--283.
• 16: 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 J. Comput., 14 (1985), pp. 254--255.
• 17: Hal Wasserman , Manuel Blum, Software reliability via run-time result-checking, Journal of the ACM (JACM), v.44 n.6, p.826-849, Nov. 1997 [doi>10.1145/268999.269003]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

General Terms:
Algorithms, Theory