MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEThe Recognition of Tolerance and Bounded Tolerance Graphs is NP-complete
par George B. Mertzios
| Date : | 29/09/09 | | Time : | 10h30 | | Location : | Lagrange Gris |
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: http://sunsite.informatik.rwth-aachen.de/Publications/AIB/2009/2009-06.pdf
Page des séminaires
| 
