## 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.

Original language | English |
---|---|

Pages (from-to) | 655-661 |

Number of pages | 7 |

Journal | ELECTRONIC NOTES IN DISCRETE MATHEMATICS |

Volume | 61 |

DOIs | |

Publication status | Published - 1 Aug 2017 |

MoE publication type | A1 Journal article-refereed |

## Keywords

- edge ordering
- graph classes
- maximum clique
- polynomial-time algorithm
- robust algorithm