Recognizing which Cographs are Set Graphs
Resumo
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.
Palavras-chave:
Algorithms, Computational Complexity, Set Graphs, Extensional Acyclic Orientation, Set-Deficiency
Referências
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.
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.
Publicado
31/07/2022
Como Citar
BANDEIRA, Bruno; CERIOLI, Márcia R.; VIANA, Petrucio.
Recognizing which Cographs are Set Graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (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.
