A complexidade do reconhecimento de grafos k-fino próprio de precedência

• Flavia Bonomo-Braberman UBA
• Fabiano Oliveira UERJ
• Moysés Sampaio Jr. UFRJ
• Jayme Szwarcfiter UERJ, UFRJ

DOI: https://doi.org/10.5753/etc.2020.11076

Resumo

The class of precedence proper k-thin graphs is a subclass of proper k-thin graphs. The complexity status of recognizing proper k-thin graphs is unknown for any fixed k ≥ 2. In this work, we prove that, when k is part of the input, the problem of recognizing precedence proper k-thin graphs is NP-complete, and we present a characterization for them based on threshold graphs.

Palavras-chave: grafos de intervalo próprio, grafos k-fino próprio, grafos k-fino próprio de precedência, grafos de limiar, complexidade computacional, caracterização

Referências

Bonomo, F. and de Estrada, D. (2019). On the thinness and proper thinness of a graph. Discrete Applied Mathematics, 261:78–92.

Oliveira, F. S., Sampaio Jr., M. S., and Szwarcfiter, J. L. (2018). Sobre finura própria de grafos. In Anais do III Encontro de Teoria da Computação. SBC.

Roberts, F. (1969). Indifference graphs. In Harary, F., editor, Proof Techniques in Graph Theory, pages 139–146. Academic Press, New York.

Schaefer, T. J. (1978). The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC’78, pages 216–226.