The computational complexity of recognizing precedence proper k-thin graphs

• 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

Abstract

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.

Keywords: proper interval graphs, proper k-thin graphs, precedence proper k-thin graphs, threshold graphs, computational complexity, characterization

References

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.