A New Intersection Model for Multitolerance Graphs, Hierarchy, and
Efficient Algorithms
George B. Mertzios
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 attracted many research efforts, mainly due to its
interesting structure and its numerous applications, while a number of
variations of this model has appeared. In particular, one of the most
natural generalizations of tolerance graphs, namely \emph{multitolerance}
graphs, has been introduced in 1998 \cite{Parra98}, where two tolerances
are allowed for each interval. These two tolerances - one from the left
and one from the right side of the interval - define an infinite number of
the so called \emph{tolerance-intervals}, which make the multitolerance
model inconvenient to cope with. The main subclass of multitolerance
graphs, namely bounded multitolerance graphs, coincide with the widely
known class of trapezoid graphs that has been extensively studied. In
this article we introduce the first non-trivial intersection model for
general multitolerance graphs, given by objects in the three-dimensional
space called \emph{trapezoepipeds}, which unifies in a simple and
intuitive way the trapezoid representation for bounded multitolerance
graphs and the recently introduced parallelepiped representation for
tolerance graphs \cite{MSZ-Model-SIDMA-09}. Apart from being important
on its own, this new intersection model proves to be a powerful tool for
designing efficient algorithms. Given a multitolerance graph with $n$
vertices and $m$ edges, we present three new algorithms that compute
a minimum coloring and a maximum clique in optimal $O(n\log n)$ time,
and a maximum weight independent set in $O(m + n\log n)$ time - this
algorithm also improves the best known running time of $O(n^{2})$ for the
same problem on tolerance graphs \cite{MSZ-Model-SIDMA-09}. Moreover,
we prove several structural results on the class of multitolerance
graphs, complementing thus the hierarchy of perfect graphs given in
\cite{GolTol04}. The resulting hierarchy of classes of perfect graphs
is \emph{complete}, i.e. all inclusions are strict.