Co-Bipartite Neighborhood Edge Elimination Orderings

Wanchote Jiamjitrak, E.J. van Leeuwen

    Research output: Contribution to journalArticleAcademicpeer-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 - Aug 2017

    Keywords

    • maximum clique
    • polynomial-time algorithm
    • robust algorithm
    • graphclasses
    • edge ordering

    Fingerprint

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

    Cite this