Linear recognition of almost interval graphs

DOI10.1137/1.9781611974331.CH77MaRDI QIDQ4575657zbMATH OpenOpenAlexFDO

Authors Yixin Cao

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.1515

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Let $mboxinterval+kv$, $mboxinterval+ke$, and $mboxinterval-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 $mboxinterval+ke$, first asked by Bodlaender et al. [Bioinformatics, 11:49--57, 1995]. Moreover, our algorithms for recognizing $mboxinterval+kv$ and $mboxinterval-ke$ run in times $O(6^{k}cdot(n+m))$ and $O(8^{k}cdot(n+m))$, (where $n$ and $m$ stand for the numbers of vertices and edges respectively in the input graph,) significantly improving the $O(k^{2k}cdot{n}^{3}m)$-time algorithm of Heggernes et al. [STOC 2007] and the $O(10^{k}cdot{n}^9)$-time algorithm of Cao and Marx [SODA 2014] respectively.

Recommendations

• scientific article; zbMATH DE number 4049085
• A linear-time algorithm for proper interval graph recognition
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Interval Completion Is Fixed Parameter Tractable

Cited in

(40)

• The recognition problem for line bigraphs
• On the classes of interval graphs of limited nesting and count of lengths
• Vertex deletion problems on chordal graphs
• Paths to trees and cacti
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Vertex deletion into bipartite permutation graphs
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
• Line-Polar Graphs: Characterization and Recognition
• Erdös-Pósa Property of Obstructions to Interval Graphs
• Approximation and kernelization for chordal vertex deletion
• scientific article; zbMATH DE number 6810347 (Why is no real title available?)
• Vertex deletion problems on chordal graphs
• Paths to trees and cacti
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• Slightly superexponential parameterized problems
• scientific article; zbMATH DE number 7651188 (Why is no real title available?)
• Conflict free version of covering problems on graphs: classical and parameterized
• Parameterized complexity of diameter
• scientific article; zbMATH DE number 7765420 (Why is no real title available?)
• Vertex deletion into bipartite permutation graphs
• Polynomial Kernel for Interval Vertex Deletion
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Erdős–Pósa property of obstructions to interval graphs
• Assistance and interdiction problems on interval graphs
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• A survey of parameterized algorithms and the complexity of edge modification
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Graphs with at most two moplexes
• Modification problems toward proper (Helly) circular-arc graphs
• A constant-factor approximation for weighted bond cover
• Simple linear time recognition of unit interval graphs
• When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices
• Parameterized complexity of biclique contraction and balanced biclique contraction
• Domination and cut problems on chordal graphs with bounded leafage
• Tight bounds for chordal/interval vertex deletion parameterized by treewidth
• Rank reduction of oriented graphs by vertex and edge deletions
• Parameterized dynamic data structure for split completion

This page was built for publication: Linear recognition of almost interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575657)