We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

New geometric representations and domination problems on tolerance and multitolerance graphs.

Giannopoulou, A.C. and Mertzios, G.B. (2016) 'New geometric representations and domination problems on tolerance and multitolerance graphs.', SIAM journal on discrete mathematics., 30 (3). pp. 1685-1725.


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 on the left side and the other on the right side. Several efficient algorithms for optimization problems that are NP-hard 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 paper 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, thus solving a longstanding open problem. This problem is the first one that has been discovered with a different complexity status in these two graph classes.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© 2016 SIAM. Published by SIAM under the terms of the Creative Commons 4.0 license
Date accepted:13 May 2016
Date deposited:16 May 2016
Date of first online publication:30 August 2016
Date first made open access:08 September 2016

Save or Share this output

Look up in GoogleScholar