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, I.e., graphs that 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 O(n m)-time and O(n+m)-space algorithm for determining whether a given graph G on n vertices and m edges is HHD-free. 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; the certificate computation requires O(n + m) additional time and O(n) space.