Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs

Abstract

A certifying algorithm for a problem is an algorithm that provides a \ncertificate with each answer that it produces. The certificate is a piece of \nevidence that proves that the answer has not been compromised by a bug in the \nimplementation. We give linear-time certifying algorithms for recognition of \ninterval graphs and permutation graphs, and for a few other related problems. \nPrevious algorithms fail to provide supporting evidence when they claim that \nthe input graph is not a member of the class. We show that our certificates of \nnonmembership can be authenticated in O(|V|) time.