Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
The Recognition of Tolerance and Bounded Tolerance Graphs
Mertzios, G.B.; Sau, I.; Zaks, S.
Authors
I. Sau
S. Zaks
Contributors
Jean-Yves Marion
Editor
Thomas Schwentick
Editor
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. Several efficient algorithms for optimization problems that are NP-hard on 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 article 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) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs~\cite{MC-Trapezoid}.
Citation
Mertzios, G., Sau, I., & Zaks, S. (2010). The Recognition of Tolerance and Bounded Tolerance Graphs. In J. Marion, & T. Schwentick (Eds.), . https://doi.org/10.4230/lipics.stacs.2010.2487
Conference Name | 27th International Symposium on Theoretical Aspects of Computer Science (STACS) |
---|---|
Conference Location | Nancy, France |
Start Date | Mar 4, 2010 |
End Date | Mar 6, 2010 |
Publication Date | Jan 1, 2010 |
Deposit Date | Sep 5, 2014 |
Publicly Available Date | Mar 28, 2024 |
Volume | 5 |
Pages | 585-596 |
Series Title | Leibniz International Proceedings in Informatics (LIPIcs) |
Series ISSN | 1868-8969 |
DOI | https://doi.org/10.4230/lipics.stacs.2010.2487 |
Keywords | Tolerance graphs, Bounded tolerance graphs, Recognition, Vertex splitting, NP-complete, Rrapezoid graphs, Permutation graphs |
Public URL | https://durham-repository.worktribe.com/output/1155122 |
Publisher URL | http://drops.dagstuhl.de/opus/volltexte/2010/2487/ |
Files
Published Conference Proceeding
(324 Kb)
PDF
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search