AIB 2009-06: The Recognition of Tolerance and Bounded Tolerance Graphs is NP-complete

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.

.

Relevant Pages
Loading