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

(35)

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

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)