The Recognition of Tolerance and Bounded Tolerance Graphs is NP-complete
George B. Mertzios, Ignasi Sau, Shmuel Zaks
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.