Co-Bipartite Neighborhood Edge Elimination Orderings

Wanchote Jiamjitrak, Erik Jan van Leeuwen

Research output: Contribution to journalArticleScientificpeer-review

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 languageEnglish
Pages (from-to)655-661
Number of pages7
JournalELECTRONIC NOTES IN DISCRETE MATHEMATICS
Volume61
DOIs
Publication statusPublished - 1 Aug 2017
MoE publication typeA1 Journal article-refereed

Keywords

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

Fingerprint

Dive into the research topics of 'Co-Bipartite Neighborhood Edge Elimination Orderings'. Together they form a unique fingerprint.

Cite this