The following technical report is available from http://aib.informatik.rwth-aachen.de:
The Recognition of Tolerance and Bounded Tolerance Graphs is NP-complete George B. Mertzios, Ignasi Sau, Shmuel Zaks AIB 2009-06
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has been extensively studied, due to both its interesting structure and its numerous applications (in bioinformatics, constrained-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, are probably the most fundamental open problems in this context (cf.~the book on tolerance graphs~\cite{GolTol04}) since their introduction almost three decades ago~\cite{GoMo82}. In this article we resolve this problem, by proving that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. For our reduction we extend the notion of an acyclic orientation of permutation and trapezoid graphs. Our main tool is a new algorithm (which uses an approach similar to~\cite{Cheah96}) that transforms a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property.