Speaker: George Mertzios, Department of Computer Science, RWTH Aachen

Title: The Recognition of Tolerance and Bounded Tolerance Graphs is NP-complete

Abstract: 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, 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, have
been the most fundamental open problems on this class of graphs
(cf.~the book on tolerance graphs~\cite{GolTol04}) since their
introduction in 1982~\cite{GoMo82}. In this talk 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. For our reduction we extend the notion of an
acyclic orientation of permutation and trapezoid graphs. Our main tool
is a new algorithm that transforms a given trapezoid graph into a
permutation graph, while preserving this new acyclic orientation
property.

Link