Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications (in bioinformatics, constraint-based temporal reasoning, resource allocation, and scheduling problems, among others). Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs—namely, the problem of deciding whether a given graph is a tolerance graph—as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf. the book on tolerance graphs [M. C. Golumbic and A. N. Trenk, Tolerance Graphs, Cambridge Stud. Adv. Math. 89, Cambridge University Press, Cambridge, UK, 2004]) since their introduction in 1982 [M. C. Golumbic and C. L. Monma, Proceedings of the 13th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 35 (1982), pp. 321–331]. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an acyclic orientation of permutation and trapezoid graphs. Our main tool is a new algorithm that uses vertex splitting to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it was also proved a powerful tool in the design of efficient recognition algorithms for other classes of graphs [G. B. Mertzios and D. G. Corneil, Discrete Appl. Math., 159 (2011), pp. 1131–1147].
Mertzios, G., Sau, I., & Zaks, S. (2011). The recognition of tolerance and bounded tolerance graphs. SIAM Journal on Computing, 40(5), 1234-1257. https://doi.org/10.1137/090780328
Journal Article Type | Article |
---|---|
Publication Date | Sep 1, 2011 |
Deposit Date | Dec 8, 2011 |
Publicly Available Date | Dec 16, 2011 |
Journal | SIAM Journal on Computing |
Print ISSN | 0097-5397 |
Electronic ISSN | 1095-7111 |
Publisher | Society for Industrial and Applied Mathematics |
Peer Reviewed | Peer Reviewed |
Volume | 40 |
Issue | 5 |
Pages | 1234-1257 |
DOI | https://doi.org/10.1137/090780328 |
Keywords | Tolerance graphs, Bounded tolerance graphs, Recognition, Vertex splitting, NP-complete, Trapezoid graphs, Permutation graphs. |
Public URL | https://durham-repository.worktribe.com/output/1524704 |
Published Journal Article
(387 Kb)
PDF
Copyright Statement
© 2011 Society for Industrial and Applied Mathematics. Unauthorized reproduction of this article is prohibited.
The complexity of computing optimum labelings for temporal connectivity
(2022)
Presentation / Conference Contribution
The complexity of temporal vertex cover in small-degree graphs
(2022)
Presentation / Conference Contribution
The complexity of transitively orienting temporal graphs
(2021)
Presentation / Conference Contribution
Equitable scheduling on a single machine
(2021)
Presentation / Conference Contribution
Exact and approximate algorithms for computing a second Hamiltonian cycle
(2020)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search