Linear recognition of almost interval graphs

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

23 Citations (Scopus)

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.
Original languageEnglish
Title of host publication[Missing Source Name from PIRA]
Pages1096-1115
Number of pages20
ISBN (Electronic)9781611974331
Publication statusPublished - 2016
EventACM-SIAM Symposium on Discrete Algorithms [SODA] -
Duration: 1 Jan 2016 → …

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms [SODA]
Period1/01/16 → …

Cite this