Recognizing which Cographs are Set Graphs

  • Bruno Bandeira UFRJ
  • Márcia R. Cerioli UFRJ
  • Petrucio Viana UFF
DOI: https://doi.org/10.5753/etc.2022.223265

Abstract


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.

Keywords: Algorithms, Computational Complexity, Set Graphs, Extensional Acyclic Orientation, Set-Deficiency

References

Corneil, D. G., Lerchs, H., and Burlingham, L. S. (1981). Complement reducible graphs. Discrete Applied Mathematics, 3(3):163–174.

Omodeo, E. G., Policriti, A., and Tomescu, A. I. (2017). On sets and graphs: Perspectives on logic and combinatorics. Springer.

Tomescu, A. I. (2012). Sets as graphs. PhD thesis, Università degli Studi di Udine.
Published
2022-07-31
How to Cite

Select a Format
BANDEIRA, Bruno; CERIOLI, Márcia R.; VIANA, Petrucio. Recognizing which Cographs are Set Graphs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 129-132. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.223265.