An O(nm)-time certifying algorithm for recognizing HHD-free graphs

In this paper, we consider the recognition problem on a class of perfectly orderable graphs, namely, the HHD-free graphs; such graphs do not contain any induced subgraph isomorphic to a house, a hole, or a domino. We prove properties of the HHD-free graphs which enable us to present an -time and O(n+m)-space algorithm for determining whether a graph on n vertices and m edges is HHD-free; currently, this is the fastest algorithm for this problem. We also describe how the algorithm can be augmented to provide a certificate (an induced house, hole, or domino) whenever it decides that the input graph is not HHD-free, thus answering an open question posed by Hoàng and Sritharan (Theoretical Computer Science 259 (2001) 233–244). The certificate computation requires O(n+m) additional time and O(n) space.