Recognizing which Cographs are Set Graphs - Bandeira, Bruno; Cerioli, Márcia R.; Viana, Petrucio (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.223265, 2022)
A set graph is a graph admitting an extensional acyclic orientation. The set graph recognition problem was first considered and proved to be NP-complete by A. Tomescu in 2012. In this work, we introduce two concepts that can be used for the efficient recognition of set graphs in some classes of graphs. We define layered extensional acyclic orientations and a graph parameter, called set-deficiency, that measures how far a graph is from being a set graph. Then, we describe how these concepts can be applied to recognize set graphs in the class of cographs in polynomial time.