A.C. Giannopoulou
New geometric representations and domination problems on tolerance and multitolerance graphs
Giannopoulou, A.C.; Mertzios, G.B.
Authors
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Contributors
Ernst W. Mayr
Editor
Nicolas Ollinger
Editor
Abstract
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalizations of tolerance graphs with direct applications in the comparison of DNA sequences from different organisms, namely multitolerance graphs, two tolerances are allowed for each interval – one from the left and one from the right side. Several efficient algorithms for optimization problems that are NPhard in general graphs have been designed for tolerance and multitolerance graphs. In spite of this progress, the complexity status of some fundamental algorithmic problems on tolerance and multitolerance graphs, such as the dominating set problem, remained unresolved until now, three decades after the introduction of tolerance graphs. In this article we introduce two new geometric representations for tolerance and multitolerance graphs, given by points and line segments in the plane. Apart from being important on their own, these new representations prove to be a powerful tool for deriving both hardness results and polynomial time algorithms. Using them, we surprisingly prove that the dominating set problem can be solved in polynomial time on tolerance graphs and that it is APX-hard on multitolerance graphs, solving thus a longstanding open problem. This problem is the first one that has been discovered with a different complexity status in these two graph classes. Furthermore we present an algorithm that solves the independent dominating set problem on multitolerance graphs in polynomial time, thus demonstrating the potential of this new representation for further exploitation via sweep line algorithms.
Citation
Giannopoulou, A., & Mertzios, G. (2015, December). New geometric representations and domination problems on tolerance and multitolerance graphs. Presented at 32nd Symposium on Theoretical Aspects of Computer Science (STACS), Munich, Germany
Presentation Conference Type | Conference Paper (published) |
---|---|
Conference Name | 32nd Symposium on Theoretical Aspects of Computer Science (STACS) |
Acceptance Date | Dec 6, 2014 |
Publication Date | Mar 7, 2015 |
Deposit Date | Jan 14, 2015 |
Publicly Available Date | Feb 11, 2015 |
Pages | 354-366 |
Series Title | Leibniz International Proceedings in Informatics (LIPIcs) |
Series ISSN | 1868-8969 |
Book Title | 32nd international symposium on theoretical aspects of computer science (STACS 2015). |
DOI | https://doi.org/10.4230/lipics.stacs.2015.354 |
Keywords | Tolerance graphs, Multitolerance graphs, Geometric representation, Dominating set problem, Polynomial time algorithm, APX-hard. |
Public URL | https://durham-repository.worktribe.com/output/1152824 |
Publisher URL | http://drops.dagstuhl.de/opus/volltexte/2015/4926/ |
Files
Published Conference Proceeding
(675 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
Interference-free walks in time: Temporally disjoint paths
(2022)
Journal Article
Equitable scheduling on a single machine
(2022)
Journal Article
The Power of Linear-Time Data Reduction for Maximum Matching
(2020)
Journal Article
When can graph hyperbolicity be computed in linear time?
(2018)
Journal Article
A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
(2018)
Journal Article