Co-Bipartite Neighborhood Edge Elimination Orderings

Abstract

In SODA 2001, Raghavan and Spinrad introduced robust algorithms as a way to solve hard combinatorial graph problems in polynomial time even when the input graph falls slightly outside a graph class for which a polynomial-time algorithm exists. As a leading example, the Maximum Clique problem on unit disk graphs (intersection graphs of unit disks in the plane) was shown to have a robust, polynomial-time algorithm by proving that such graphs admit a co-bipartite neighborhood edge elimination ordering (CNEEO). This begs the question whether other graph classes also admit a CNEEO. In this paper, we answer this question positively, and identify many graph classes that admit a CNEEO, including several graph classes for which no polynomial-time recognition algorithm exists (unless P=NP). As a consequence, we obtain robust, polynomial-time algorithms for Maximum Clique on all identified graph classes. We also prove some negative results, and identify graph classes that do not admit a CNEEO. This implies an almost-perfect dichotomy for subclasses of perfect graphs.