Linear Recognition of Almost (Unit) Interval Graphs

Give a graph class G and a nonnegative integer k, we use G+kv, G+ke, and G−ke to denote the classes of graphs that can be obtained from some graph in G by adding k vertices, adding k edges, and deleting k edges, respectively. They are called almost (unit) interval graphs if G is the class of (unit) interval graphs. Almost (unit) interval graphs are well motivated from computational biology, where the data ought to be represented by a (unit) interval graph while we can only expect an almost (unit) 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 (unit) interval graph as evidence. When k is part of the input, all the recognition problems are NP-complete. Our results imply that all of them are fixed-parameter tractable parameterized by k, thereby resolving the long-standing open problem on the parameterized complexity of recognizing (unit) interval+ke, first asked by Bodlaender et al. [Comput. Appl. Biosci., 11(1):49–57, 1995]. Moreover, our algorithms for recognizing (unit-)interval+kv and (unit-)interval−ke have single-exponential dependence on k and linear dependence on the graph size, which significantly improve all previous algorithms for recognizing the same classes. In particular, we show that: (n and m stand for the numbers of vertices and edges respectively in the input graph) • interval−ke can be recognized in time O(6k · (n +m)), improved from O(k2k · n3m) [Heggernes et al., STOC 2007]; • unit-interval−ke can be recognized in time O(4k · (n+m)), improved from O(16k · (m+n)) [Kaplan et al., FOCS 1994]; • interval+kv can be recognized in time O(8k · (n +m)), improved from O(10k · n9) [Cao and Marx