Please use this identifier to cite or link to this item:
Title: Linear recognition of almost interval graphs
Authors: Cao, YX 
Issue Date: 2016
Source: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), Arlington, Virginia, January 10-12, 2016, p. 1096-1115 How to cite?
Abstract: Let interval + kv, interval + ke, and interval -- ke denote the classes of graphs that can be obtained from some interval graph by adding k vertices, adding k edges, and deleting k edges, respectively. When k is small, these graph classes are called almost interval graphs. They are well motivated from computational biology, where the data ought to be represented by an interval graph while we can only expect an almost interval graph for the best. For any fixed k, we give linear-time algorithms for recognizing all these classes, and in the case of membership, our algorithms provide also a specific interval graph as evidence. When k is part of the input, these problems are also known as graph modification problems, all NP-complete. Our results imply that they are fixed-parameter tractable parameterized by k, thereby resolving the long-standing open problem on the parameterized complexity of recognizing interval + ke, first asked by Bodlaender et al. [Bioinformatics, 11:49--57, 1995]. Moreover, our algorithms for recognizing interval + kv and interval -- ke run in times O(6k · (n + m)) and O(8k · (n + m)), (where n and m stand for the numbers of vertices and edges respectively in the input graph,) significantly improving the O(k2k · n3m)-time algorithm of Heggernes et al. [STOC 2007; SICOMP 2009] and the O(10k · n9)-time algorithm of Cao and Marx [SODA 2014; TALG 2015] respectively.
ISBN: 978-1-61197-433-1 (electronic)
Appears in Collections:Conference Paper

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Citations as of Aug 19, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.